programme.lv

Dažādie skaitļi

viegls

Uzdevums no Latvijas 37. (2023./2024. m. g.) informātikas olimpiādes (LIO) novada kārtas.

Stāsts

Naturālu skaitļu virknē nepieciešams atrast garāko fragmentu (secīgu elementu virkni), kur visi skaitļi būtu atšķirīgi.

Piemēram, virknē $1, 3, 6, 3, 1, 4, 5, 3, 1$ garākais fragments, kur visi skaitļi ir atšķirīgi, ir garumā $5$ un sākas ar trešo elementu: $6, 3, 1, 4, 5$ .

Uzrakstiet datorprogrammu, kas dotai skaitļu virknei atrod garākā fragmenta, kurā visi skaitļi ir atšķirīgi, garumu un visas šādu fragmentu atrašanās vietas!

Ievaddati

Ievaddatu pirmajā rindā dots naturāls skaitlis – virknes elementu skaits $N$ $(N \leq 2 \cdot 10^5)$ .

Nākamajā ievaddatu rindā doti $N$ naturāli skaitļi – virknes elementi. Zināms, ka neviens skaitlis virknē nav lielāks par $10^9$ .

Starp katriem diviem blakus skaitļiem ievaddatos ir tukšumzīme.

Izvaddati

Izvaddatu pirmajā rindā jāizvada naturāls skaitlis $G$ – garākā fragmenta, kas satur dažādus skaitļus, garums.

Izvaddatu otrajā rindā jāizvada naturāls skaitlis $H$ – cik vietās skaitļu virknē var atrast dažādu skaitļu fragmentus garumā $G$ .

Izvaddatu trešajā rindā augošā secībā jāizvada $H$ naturāli skaitļi – to virknes elementu indeksi, kuros sāktie fragmenti garumā $G$ nesatur vienādus skaitļus. Virknes elementu indeksi sākas no $1$ .

Starp katriem diviem blakus skaitļiem jābūt tukšumzīmei.

Piemēri

Ievaddati

9
1 3 6 3 1 4 5 3 1

Izvaddati

5
1
3

Piezīme:

Atbilst piemēram uzdevuma tekstā

Ievaddati

7
3 3 3 15 15 7 15

Izvaddati

2
3
3 5 6

Piezīme:

Ir vairāki derīgi fragmenti garumā 2: [3,15], [15,7] un [7,15].

Izpildes resursu ierobežojumi

CPU izpildes laiks uz testu: 0.5 sekundes.

RAM atmiņas apjoms uz testu: 256 megabaiti.

Apakšuzdevumi un to vērtēšana

#	Apraksts un ierobežojumi	Punkti
1.	Uzdevuma tekstā dotie trīs testi	2
2.	$N \leq 100$ , $H = 1$	12
3.	$N \leq 1000$ , neviens no virknes elementiem nepārsniedz $5$	15
4.	$N \leq 1000$	20
5.	$N > 1000$ , neviens no virknes elementiem nepārsniedz $10^6$	21
6.	Bez papildu ierobežojumiem	30

Apakšuzdevumu punktu summa = 100.

1. apakšuzdevuma ievaddati

14
1 3 5 3 2 3 7 9 3 8 6 4 9 3

14
9 8 7 9 8 6 9 8 5 9 7 4 9 8

20
11 65 12 86 50 17 65 86 58 35 83 85 10 50 17 65 86 58 35 83

Dažādie skaitļi

viegls

Uzdevums no Latvijas 37. (2023./2024. m. g.) informātikas olimpiādes (LIO) novada kārtas.

Stāsts

Naturālu skaitļu virknē nepieciešams atrast garāko fragmentu (secīgu elementu virkni), kur visi skaitļi būtu atšķirīgi.

Piemēram, virknē $1, 3, 6, 3, 1, 4, 5, 3, 1$ garākais fragments, kur visi skaitļi ir atšķirīgi, ir garumā $5$ un sākas ar trešo elementu: $6, 3, 1, 4, 5$ .

Uzrakstiet datorprogrammu, kas dotai skaitļu virknei atrod garākā fragmenta, kurā visi skaitļi ir atšķirīgi, garumu un visas šādu fragmentu atrašanās vietas!

Ievaddati

Ievaddatu pirmajā rindā dots naturāls skaitlis – virknes elementu skaits $N$ $(N \leq 2 \cdot 10^5)$ .

Nākamajā ievaddatu rindā doti $N$ naturāli skaitļi – virknes elementi. Zināms, ka neviens skaitlis virknē nav lielāks par $10^9$ .

Starp katriem diviem blakus skaitļiem ievaddatos ir tukšumzīme.

Izvaddati

Izvaddatu pirmajā rindā jāizvada naturāls skaitlis $G$ – garākā fragmenta, kas satur dažādus skaitļus, garums.

Izvaddatu otrajā rindā jāizvada naturāls skaitlis $H$ – cik vietās skaitļu virknē var atrast dažādu skaitļu fragmentus garumā $G$ .

Starp katriem diviem blakus skaitļiem jābūt tukšumzīmei.

Piemēri

Ievaddati

9
1 3 6 3 1 4 5 3 1

Izvaddati

5
1
3

Piezīme:

Atbilst piemēram uzdevuma tekstā

Ievaddati

7
3 3 3 15 15 7 15

Izvaddati

2
3
3 5 6

Piezīme:

Ir vairāki derīgi fragmenti garumā 2: [3,15], [15,7] un [7,15].

Izpildes resursu ierobežojumi

CPU izpildes laiks uz testu: 0.5 sekundes.

RAM atmiņas apjoms uz testu: 256 megabaiti.

Apakšuzdevumi un to vērtēšana

#	Apraksts un ierobežojumi	Punkti
1.	Uzdevuma tekstā dotie trīs testi	2
2.	$N \leq 100$ , $H = 1$	12
3.	$N \leq 1000$ , neviens no virknes elementiem nepārsniedz $5$	15
4.	$N \leq 1000$	20
5.	$N > 1000$ , neviens no virknes elementiem nepārsniedz $10^6$	21
6.	Bez papildu ierobežojumiem	30

Apakšuzdevumu punktu summa = 100.

1. apakšuzdevuma ievaddati

14
1 3 5 3 2 3 7 9 3 8 6 4 9 3

14
9 8 7 9 8 6 9 8 5 9 7 4 9 8

20
11 65 12 86 50 17 65 86 58 35 83 85 10 50 17 65 86 58 35 83