Годинник | |
|
SUMRMQ
|
| Задача СумRMQтор (SUMRMQ)
Заповітною мрією винахідника Ніколя Барузова було створення машини (еремк’ютера), основною функцією якої буде генерування послідовності випадкових чисел. Послідовність генерується наступним чином: перше число послідовності дорівнює X1, а кожне наступне обчислюється за формулою , де X1, A, B и q – задані цілі числа.Далі Ніколя задався такою метою: розширити застосування еремк’ютера ввівши виконання ним додаткової функції – пошук мінімального значення у згенерованій послідовності. В процесі тестування виявилося, що еремк’ютер-мінімізатор знаходить мінімум з K послідовно розташованих елементів. Тепер Ніколя удосконалює свою машину таким чином, що для заданої послідовності з N елементів знаходяться мінімуми для всіх можливих числових відрізків довжиною K (відрізок складають елементи, розміщені підряд), а потім обчислюється їх сума. Ваша задача написати програму, яка перевіряє правильність роботи машини шляхом підрахунку вказаної суми.
Формат введення/виведення:Програма SUMRMQ зчитує з клавіатури шість цілих чисел, розділених пробілом N, K, X1, A, B та q (3≤K≤N≤107, K≤106, 0≤A,B,X1≤109, 0≤q≤30). Програма повинна вивести одне число – суму мінімумів на всіх відрізках довжини K.Приклад:
| Введення |
Виведення |
| 6 2 2 5 9 5 |
65 |
Пояснення до тесту: Згенерована послідовність 2 19 8 17 30 31Отримана сума 65=2+8+8+17+30
|
|
|
