Решение задачи Спортивная мафия с Codeforces
Без пояснения   Просмотров: 195
Каждый вечер после ужина ЛКШата собираются в лодочной станции, чтобы насладиться игрой в спортивную мафию.
Для турнира Аля набирает в банку конфеты — это будет призовой фонд. Она делает это за n ходов. На первом ходу она кладёт в банку одну конфету. Каждый следующий ход у неё есть выбор:
первый вариант хода — если в банке есть хотя бы одна конфета, то она может за ход вытащить ровно одну конфету из банки и съесть её (таким образом, за один ход количество конфет в банке уменьшается на 1);
второй вариант хода — положить в банку конфеты, в этом случае она кладёт на 1 конфету больше, чем клала в последний раз перед этим.
Таким образом, если банка пуста, то она может осуществить только второй вариант хода.
Например, возможная последовательность действий Али такая:
положить в банку одну конфету;
положить в банку две конфеты;
съесть одну конфету из банки;
съесть одну конфету из банки;
положить в банку три конфеты;
съесть одну конфету из банки;
положить в банку четыре конфеты;
съесть одну конфету из банки;
положить в банку пять конфет.
В этом случае будет совершено 9 ходов, количество конфет в банке в итоге будет равно 11, а Аля съест суммарно 4 конфеты.
Известно общее количество ходов n и количество конфет k после всех ходов Али. Найдите суммарное количество съеденных Алей конфет (то есть количество ходов первого варианта). Гарантируется, что для заданных n и k ответ существует.
Обратите внимание, что за один ход первого варианта Аля вытаскивает и съедает ровно одну конфету.
Для турнира Аля набирает в банку конфеты — это будет призовой фонд. Она делает это за n ходов. На первом ходу она кладёт в банку одну конфету. Каждый следующий ход у неё есть выбор:
первый вариант хода — если в банке есть хотя бы одна конфета, то она может за ход вытащить ровно одну конфету из банки и съесть её (таким образом, за один ход количество конфет в банке уменьшается на 1);
второй вариант хода — положить в банку конфеты, в этом случае она кладёт на 1 конфету больше, чем клала в последний раз перед этим.
Таким образом, если банка пуста, то она может осуществить только второй вариант хода.
Например, возможная последовательность действий Али такая:
положить в банку одну конфету;
положить в банку две конфеты;
съесть одну конфету из банки;
съесть одну конфету из банки;
положить в банку три конфеты;
съесть одну конфету из банки;
положить в банку четыре конфеты;
съесть одну конфету из банки;
положить в банку пять конфет.
В этом случае будет совершено 9 ходов, количество конфет в банке в итоге будет равно 11, а Аля съест суммарно 4 конфеты.
Известно общее количество ходов n и количество конфет k после всех ходов Али. Найдите суммарное количество съеденных Алей конфет (то есть количество ходов первого варианта). Гарантируется, что для заданных n и k ответ существует.
Обратите внимание, что за один ход первого варианта Аля вытаскивает и съедает ровно одну конфету.