A. Халява

Ограничение времени: 2 с
Ограничение памяти: 256 M


Работать надо так, чтобы не было мучительно больно за бесплатно потраченное время.
Фольклор

Ни для кого не секрет, что студенты ОНУ обожают выполнять лабораторные работы. Они денно и нощно в поте чела и не щадя живота своего корпят над бесчисленными задачками, штудируют сотни методичек и производят тонны отчётной макулатуры с превеликим удовольствием. И, разумеется, вложив столько усилий в лабораторную работу, любой студент хочет быть оценённым по заслугам. Как порой бывает обидно, когда твоя блестяще сделанная лабораторная работа попадается на глаза преподавателю, находящемуся в скверном расположении духа, а буквально на следующий день, твой нерадивый однокурсник сдаёт работу, выполненную на тяп-ляп, довольному сенсею. Вот бы знать заранее, какое настроение у преподавателя! К счастью, не все процессы во Вселенной случайны.

Например, по результатам многолетних наблюдений студентов кафедры Конкретной Математики, у профессора Варфоломея Гаврииловича Крикушина настроение изменяется в диапазоне от 0 до p-1 халявоединиц. При чём, если сегодня этот показатель равен R, то завтра он будет равен R - D. В случае, если результат вычитания меньше 0, к нему прибавляется по p халявоединиц до тех пор, пока он не станет неотрицательным (вероятно, в этот день Варфоломею Гаврииловичу выдают зарплату). Вы знаете, какое настроение у профессора Крикушина сегодня, а ещё вы знаете, за сколько дней вы выполните свою лабораторную работу. Вам очень интересно, каковы ваши шансы получить хорошую оценку.

Ввод. Единственная строка ввода содержит 4 целых числа: R, D, p, n (R от 0 до p-1, остальные числа – от 1 до 10^9) – текущее настроение профессора, разность настроений между двумя соседними днями, верхняя (недостижимая) граница настроения профессора, количество дней до сдачи работы.

Вывод. Выведите единственное число – настроение профессора n дней спустя.

Идея – Артур Леонидович Максимов

Примеры

Входные данные Результат работы
3 1 4 2
1
3 2 4 2
3

 

Решение

Ниже Вы найдете несколько подсказок и текст решения задачи. Подсказки будут постепенно детализировать процесс решения. После чтения каждой подсказки желательно попытаться самому обдумать задача заново с учетом новой информации. Последовательность подсказок отражает последовательность "догадок" в процессе решения задачи. Конечно, это индивидуально. Т.е. я описываю как я размышлял над задачей, но не могу сказать, что это единственный путь.

Подсказка 1: Не нужно циклов и рекурсий Select

Для тех, кто сомневается.  Чтобы не быть голословным я все же написал код, соответствующий такому решению "в лоб". Его еще называют "моделирующим", поскольку происходит буквальное повторение всей последовательности действий из условия задачи. Вот что у меня получилось на Java:
Плохое решение: Превышено максимальное время работы Select

Подсказка 2: Умножение и модульная арифметика Select

После чтения этой подсказки все должно получиться.
Тем не менее, советую попробовать решить задачу и отправить ее для проверки на сервер соревнования. Он продолжает работать в режиме "дорешивания".
Окончательное решение на Java Вы можете найти под спойлером ниже:

Хорошее решение: OK Select

Все получилось? Переходим к другим задачам. Я бы посоветовал для разминки задачу G - ее решили почти все участники.

Анализ

Каждая задача может повлечь цепочку полезных размышлений. В нашем случае может возникнуть вопрос о периодичности значений функции по параметру n. Ясно, что если в какой-либо из дней значение R повторится, то мы войдем в цикл. В тоже время различных значений R может быть не более p. Т.е. цикл возникнет наверняка. Но от чего зависит размер этого цикла? Т.е. с каким периодом будут повторяться значения функции R(n)? В идеале было бы построить функцию T(R,D,p), которая вычисляла бы величину периода в зависимости от начальных условий задачи. Попробуем?

About the post author Igor Mazurok (5 Posts)

PhD in Computer Science, Associate professor of Department Applied Mathematics of Odessa I.I.Mechnikov National University, Ukraine KBIS Software Developer

Author Info

Igor Mazurok

PhD in Computer Science, Associate professor of Department Applied Mathematics of Odessa I.I.Mechnikov National University, Ukraine
KBIS Software Developer

Добавить комментарий