stabini Monētu stabiņi 1 sek.  Uzdevums Aplī ir izvietoti N monētu stabiņi. Katrā stabiņā ir vismaz viena monēta. Vairāku monētu gadījumā tās ir uzliktas viena virs otras. Stabiņi ir sanumurēti ar naturāliem skaitļiem no 1 līdz N pulksteņrādītāja virzienā pēc kārtas. Pēc N-tā stabiņa pulksteņrādītāja virzienā seko pirmais stabiņš. Monētu skaits pa visiem stabiņiem kopā ir N*K. Ar stabiņiem atļauts veikt tikai viena veida darbību - “līdzināšanu”. Tas nozīmē, ka tiek izvēlēts kāds stabiņš un, ja tajā ir vairāk par K monētām, tad šajā stabiņā tiek atstātas tieši K monētas un atlikušās tiek pārceltas uz blakusesošu stabiņu pulksteņrādītāja virzienā. Ja monētu skaits stabiņā nepārsniedz K, tad neko darīt nevar (bet šis tomēr tiek ieskaitīts kā izdarīts gājiens). Tālāk šāda pat operācija tiek atkārtota ar nākamo stabiņu pulksteņrādītāja virzienā, pēc tam ar vēl nākamo utt. Pēc kāda laika monētu skaits visos stabiņos kļūs vienāds ar K, un tikko tas ir noticis, tā process apstājas. Sākot līdzināšanu no dažādiem stabiņiem, kopējais darbību skaits var būt atšķirīgs. Piemēram, ja N=5, K=4 un sākumā monētu skaits stabiņos ir 3, 1, 6, 4, 6, tad, sākot līdzināšanu ar ceturto stabiņu, monētu skaits stabiņos mainīsies šādi: Gājiena numurs Monētu skaits stabiņos Piezīmes pirms gājiena pēc gājiena 1 3 1 6 4 6 3 1 6 4 6 4=4, nekas nemainās 2 3 1 6 4 6 5 1 6 4 4 6>4, divas monētas ir pārceltas uz pirmo stabiņu 3 5 1 6 4 4 4 2 6 4 4 5>4, viena monēta ir pārcelta uz otro stabiņu 4 4 2 6 4 4 4 2 6 4 4 2<4, nekas nemainās 5 4 2 6 4 4 4 2 4 6 4 6>4, divas monētas ir pārceltas uz ceturto stabiņu 6 4 2 4 6 4 4 2 4 4 6 6>4, divas monētas ir pārceltas uz piekto stabiņu 7 4 2 4 4 6 6 2 4 4 4 6>4, divas monētas ir pārceltas uz pirmo stabiņu 8 6 2 4 4 4 4 4 4 4 4 6>4, divas monētas ir pārceltas uz otro stabiņu Šajā gadījumā bija nepieciešami astoņi gājieni, bet, ja līdzināšana būtu sākta ar trešo stabiņu, būtu pieticis ar četriem gājieniem. Uzrakstiet programmu, kas dotām N un K vērtībām un monētu skaitam katrā stabiņā, atrod to stabiņu, no kura jāsāk līdzināšana, lai visu stabiņu nolīdzināšanai nepieciešamais gājienu skaits būtu mazākais iespējamais!    Ievaddati Teksta datnes stabini.dat pirmajā rindā doti divi naturāli skaitļi N (1 < N ≤ 100 000) un K (1 < K < 20 000), kas atdalīti ar tukšumzīmi. Datnes otrajā rindā doti N naturāli skaitļi, kur katri divi blakusesoši skaitļi atdalīti ar tukšumzīmi, - monētu skaits stabiņos. Katram i (1 ≤ i ≤ N) i-tais skaitlis rindā norāda monētu skaitu i-tajā stabiņā. Zināms, ka katrā stabiņā sākumā ir vismaz viena monēta un ir iespējams atrast divus stabiņus, kuros monētu skaits ir atšķirīgs.    Izvaddati Teksta datnes stabini.rez vienīgajā rindā jāizvada naturāls skaitlis - tā stabiņa numurs, no kura sākot līdzināšanu, būs nepieciešams mazākais gājienu skaits. Ja mazāko gājienu skaitu iespējams sasniegt, sākot līdzināšanu no dažādiem stabiņiem, jāizvada mazākais no šo stabiņu numuriem.    Piemērs stabini.dat stabini.rez 10 8 7 9 7 9 7 9 7 9 7 9 2     stabini.dat stabini.rez 5 4 3 1 6 4 6 3 Atbilst uzdevuma formulējumā dotajam piemēram.    Atsauces Uzdevums izmantots Latvijas 22. informātikas olimpiādē 2009. gadā. Drukāšanai