Skaitļu svītrošana

4
Latvijas Informātikas olimpiādes logo

Uzdevums no 2026. g. LIO skolas kārtas; abām grupām.

Stāsts

Dota NN veselu skaitļu virkne, kurā elementu indeksācija sākas no 0. Tiek aprēķināts visu virknes skaitļu summas atlikums, dalot to ar virknes elementu skaitu, un tad no virknes tiek izsvītrots skaitlis, kura indekss sakrīt ar iegūto atlikumu. Šī darbība tiek atkārtota ar līdz šim neizsvītrotajiem virknes elementiem, tos pa vienam izsvītrojot. Ņemiet vērā, ka neizsvītroto elementu indeksācija var mainīties. Jānosaka, kādā secībā tiks izsvītroti skaitļi, ja dots to sākotnējais izkārtojums virknē.

Skaitļa aa atlikumu, dalot ar bb, definē kā tādu veselu skatli rr, kur 0≤r<b0 \leq r < b un a−ra - r dalās ar bb.

Piemēram, no virknes −17,13,10,−17,−11-17, 13, 10, -17, -11 elementi tiks izsvītroti šādā secībā: −17-17, kas atrodas pozīcijā ar indeksu 33 (atlikums, −22-22 dalot ar 55, ir 33, virknē paliek −17,13,10,−11-17, 13, 10, -11), −11-11 (atlikums, −5-5 dalot ar 44, ir 33, virknē paliek −17,13,10-17, 13, 10), −17-17 (atlikums, 66 dalot ar 33, ir 00, virknē paliek 13,1013, 10), 1010 (atlikums, 2323 dalot ar 22, ir 11, virknē paliek 1313) un 1313.

Ievaddati

Pirmajā rindā dots naturāls skaitlis NN - virknes elementu skaits (N≤5⋅105)(N \leq 5 \cdot 10^5).

Otrajā rindā doti NN veseli skaitļi - virknes elementi. Neviena skaitļa vērtība virknē pēc moduļa nepārsniedz 10910^9. Blakus skaitļi ir atdalīti ar tukšumzīmi.

Izvaddati

Vienīgajā rindā jāizvada NN skaitļi - secība, kādā tiks izvītroti skaitļi dotajā virknē.

Apakšuzdevumi un to vērtēšana

#Apakšuzdevuma aprakstsPunkti
1.

Uzdevuma tekstā dotie trīs testi

2
2.

n≥2,a0≠a1,a1=a2=...=an−1n \geq 2, a_0 \neq a_1, a_1 = a_2 = ... = a_{n-1}

12
3.

n≤5000,ai≥0n \leq 5000, a_i \geq 0

17
4.

n≤5000n \leq 5000

14
5.

0≤ai≤10 \leq a_i \leq 1

23
6.

Bez papildu ierobežojumiem

32
Apakšuzdevumu punktu summa = 100.

Piemēri

Ievaddati

5 -17 13 10 -17 -11 Kopēt kodu

Izvaddati

-17 -11 -17 10 13 Kopēt kodu

Ievaddati

7 -1 -2 -3 -4 -5 -6 7 Kopēt kodu

Izvaddati

-1 7 -2 -5 -6 -4 -3 Kopēt kodu

1. apakšuzdevuma ievaddati

10 13 8 64 22 19 20 7 31 56 3 Kopēt kodu
13 1 -2 3 -4 5 -6 7 -8 9 -10 11 -12 13 Kopēt kodu
13 1 10 100 1000 10000 100000 1000000 10000000 100000000 1000000000 -11 -101 -1001 Kopēt kodu