Xvii републиканска студентска олимпиада по програмиране
Изтегляне 14.8 Kb.
|
- Навигация на страницата:
- Пример Вход Изход
Задача E: РАЗБЪРКВАНЕС  танчо обича да сортира. Той има много сортирани последователности. Един ден Панчо решил да му направи номер. Взел сортираните последователности на Станчо и всяка от тях написал по окръжност. За всяка окръжност избрал един произволен начален елемент и подходяща стъпка, така че когато започнал да се движи от избрания елемент с избраната стъпка той обходил всички елементи, преди да достигне отново до началния. След това получените при обхождането елементи записал на местата на началните последователности...
Това разбира се било голям удар за Станчо. Преди той имал най-много сортирани последовател-ности от всички в катедрата, а сега нямал нито една. Сорти-рането на ново на последовател-ностите би отнело много време (особено ако става за време O(n.log n)). Вместо това Станчо измислил начин линейно да преподреди последователността ако знае стъпката с която е обхождал Панчо. Напишете програма която по дадена разбъркана от Панчо последова-телност определя с каква стъпка е разбърквал . Няколко тестови примера ще бъдат дадени на стандартния вход. Всеки от тях се състои от два реда. На първия се намира числото N (2 ≤ N ≤ 1000000) – броят на елементите в последователността. На втория ред има точно N цели числа, разделени с интервали – елементите на последователността разбъркана от Панчо. За всеки тестов пример изведете по едно число на отделен ред на стандартния изход – стъпката с която е разбъркал Панчо. От всички възможни стъпки изберете тази, която е положителна и най-малка. Пример
Изтегляне 14.8 Kb. Сподели с приятели:
|
