Задача B. Мытьё посуды 2

Автор:А. Усманов, Н. Гребенюк   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  
Максимальный балл:100  

Условие

Во время Войны Бесконечности Доктор Стрэндж стал просматривать варианты возможного будущего. Из четырнадцати миллионов победными оказались лишь Q вариантов, и во всех после победы Мстители устроили большую вечеринку.

В i-м варианте будущего на вечеринку придёт Ni Мстителей. Не волнуйтесь, остальные герои не погибли (это же Марвел), они уже успели отправиться на своё сольное спасение мира. Но новая напасть оказалась не за горами, и, возможно, она пострашнее Таноса — героям необходимо решить, кто пойдёт мыть посуду. К сожалению, перчатка бесконечности была уничтожена, поэтому помыть всю (или хотя бы половину) посуды щелчком пальцев не получится. Сложно только представить, к какой гражданской войне могла привести эта ситуация, если бы только один из героев не вспомнил про народный метод решения подобных проблем — считалочку.

Все герои встали в круг, они пронумерованы от 1 до Ni, 1 и Ni герой стоят рядом. После они начали отсчитывать Mi человек (енотов, деревьев и т.д.) от первого героя. Герой, на котором закончился счет, покидал круг, и счет начинался по новой, от следующего героя в круге. И так до тех пор, пока в круге не остался бы один герой — ему-то и придётся спасать этот мир (или по крайней мере эту вечеринку) от грязной посуды.

Требуется написать программу, которая для каждого варианта будущего определит, кому придётся мыть посуду, по количеству Мстителей на вечеринке и числу Mi.

Формат входного файла

Первая строка содержит одно целое число Q — количество вариантов будущего.

Далее следует Q строк, i-я из которых содержит по два целых числа Ni и Mi — количество героев, которые пришли на вечеринку в i-м варианте будущего, и количество Мстителей, которое будет отсчитываться по кругу.

Данная задача будет проверяться на ОДНОМ входном файле, содержащем все тесты. Этот файл можно скачать ЗДЕСЬ.

Второй пример соответствует тестам, которые будут оцениваться.

Формат выходного файла

Для каждого варианта будущего в отдельной строке выведите ответ на задачу.

Ограничения

1 ≤ Q ≤ 15

1 ≤ N ≤ 102

1 ≤ M ≤ 102

Описание системы оценивания

В качестве решения принимается как программа, так и текстовый файл, содержащий ответы к задаче в требуемом формате (при его отправке следует выбрать в тестирующей системе среду разработки "Answer text").

На каждый тест должен быть дан ответ (иначе есть риск неверной проверки). Если вы не знаете ответ на какой-то тест, то следует написать в выходном файле "0" (без кавычек).

Баллы начисляются пропорционально количеству правильных ответов в выходном файле.

По запросу сообщается количество набранных баллов.

Тесты Баллы Способ проверки
1-5По 6 баллов за тестПроверка осуществляется сразу после отправки решения
6-10По 6 баллов за тестПроверка осуществляется только после окончания олимпиады
11-15По 8 баллов за тестПроверка осуществляется только после окончания олимпиады

Пояснения к примерам

В первом примере в первом варианте будущего герои будут покидать круг в следующем порядке: 3, 1, 5, 2.

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
3
5 3
6 3
100 33
4
1
48
2
15
5 9
8 8
21 15
25 2
75 25
1 99
4 94
9 6
20 11
98 1
75 25
88 88
90 45
100 11
100 100
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0

Разбор

Создадим массив целых чисел, поместим в него N чисел от 1 до N. Перебираем M элементов и удаляем M-й по счёту (сдвигая весь массив влево). После N − 1-го удаления выведем оставшееся в массиве число — это и будет индекс оставшегося персонажа.

Асимптотика для одного персонажа: O(M) на поиск; O(N) на удаление.

Итоговая асимптотика: O(N ⋅ (M + N)).

Так как все тесты в этой задаче были доступны для просмотра, можно было промоделировать этот алгоритм на бумаге для небольших входных данных и набрать некоторые баллы.


0.081s 0.011s 15