Rain Again 1D
Есенен Турнир по Информатика 2015
Time Limit: 1s, Memory Limit: 128MiB
От външната страна на прозореца си Ели има продълговата, но тясна саксия с красиви цветя. Всеки път когато завали, момичето почва с интерес да следи къде падат дъждовните капки. Ако по някое време на дъжда не остане подинтервал на саксията с дължина по-голяма от D, в който да не е попаднала капка, момичето счита цветята си за напоени и спира да следи капките. За целите на тази задача ще считаме саксията за отсечка с дължина L, а капките дъжд – като точки върху тази отсечка.

Не веднъж, когато сте били на гости на Ели, се е случвало да завали и тя тотално да спре да ви слуша, концентрирайки се върху падащите капки. Затова вие решавате да напишете програма, която, ако знае къде ще паднат всички капки (в реда на тяхното падане), ви казва след коя от тях Ели ще спре да следи дъжда и отново ще ви обърне внимание.
Вход
На първия ред на стандартния вход ще бъдат зададени целите числа N, L, и D – съответно броя капки, паднали по време на дъжда (в реда на тяхното падане), дължината на саксията, и максималната дължина на подинтервал, в който не е паднала нито една капка. На втория ред ще бъдат зададени целите числа X1, A, и B. Първата капка пада в позиция X1. Всяка следваща пада на позиция Xi = (Xi-1 * A + B) % (L + 1).
Изход
На единствен ред на стандартния изход изведете едно цяло число – броя капки, които трябва да паднат, преди Ели да спре да следи дъжда (тоест да счете цветята за напоени). Ако дори след падането на всички N капки остане под-интервал с дължина по-голяма или равна на D, вместо това изпечатайте -1.
Ограничения
  • 1 ≤ N ≤ 10,000,000
  • 1 ≤ D < L ≤ 1,000,000,000
  • 0 ≤ X1, A, BL
Примерен Вход Примерен Изход
12 23 7 14 13 5 9
1 6 3 3 2 1 1
1 6 3 4 2 1 -1
123456 288391724 42666 42 6408706 91620547 26379
В първия пример са паднали 12 капки, чиито координати са съответно (14, 19, 12, 17, 10, 15, 8, 13, 6, 11, 4, 9). До падането на 9-тата капка интервалът [0, 8) е бил без паднала капка. След като тя падне в позиция 6, обаче, всички "сухи" подинтервали стават с дължина ≤ 7.
Във втория пример пада точно една капка дъжд, но тя успява да напои кактусите на Ели.
Мрън!