Python stazaCjelina 4 · Prvi algoritmiLekcija 29

Ponavljanje: prvi algoritmi

Nema novog gradiva. Na jednom mjestu su svi pristupi iz cjeline i tragovi po kojima ih prepoznaješ, a zatim šest zadataka razine županijskog natjecanja.

Pythonoko 90 minuta6 zadataka za evaluator

1Podsjetnik

LekcijaIdejaKljučni zapis
22simulacija: stanje, pravila, ponavljanjevarijable stanja + petlja
23gruba sila (brute force): isprobaj svepetlje po svim mogućnostima, j od i + 1
24rječnik, skup, n-torkad[k] += 1 · s.add(x) · (kraj, pocetak)
25složenost (time complexity)O(N), O(N²), O(log N), skrivene petlje
26prefiksni zbroj (prefix sum)p[r] - p[l - 1]
27binarno pretraživanje (binary search)mid = (lo + hi) // 2
28pohlepni algoritam (greedy)sortiraj, pa uzimaj najbolje

2Kako prepoznati pristup

Kad pročitaš zadatak, ovi tragovi često otkriju koji pristup treba:

Trag u zadatkuVjerojatan pristup
opisana su pravila koja se ponavljajusimulacija
mali N (do 20, do 200)gruba sila
„koliko puta se pojavljuje“, „različiti“, „je li već viđen“rječnik ili skup
mnogo pitanja o zbroju dijela nizaprefiksni zbroj
sortirani podaci, „najmanji koji…“, „najveći koji…“, ogroman Nbinarno pretraživanje
„što više“, „što manje“, a podatke možemo poredatipohlepno, uz provjeru
Ključna ideja

Uvijek prvo pogledaj ograničenja i procijeni složenost, kao u lekciji 25. Rješenje koje je točno, ali presporo, evaluator ne prihvaća.

3Provjeri se

Prije zadataka provjeri jesi li razumio gradivo. Klikni na odgovor za koji misliš da je točan.

Pitanje

Ograničenje N ≤ 10^5. Koje je rješenje vjerojatno dobro?

Pitanje

Puno upita o zbroju dijela niza. Koji pristup?

Pitanje

Traži se najmanji X za koji uvjet vrijedi, a uvjet „raste” s X. Koji pristup?

4Zadaci

Poredani su od lakšeg prema težem. Za svaki zadatak prvo odluči koji pristup treba, pa tek onda piši program.

Najčešći broj

★☆☆ lagano

Koji se broj u listi pojavljuje najviše puta? Ako ih je više, ispiši najmanji od njih.

Ulaz
U prvom retku N. U drugom retku N cijelih brojeva.
Izlaz
Najčešći broj.
Ograničenja
1 ≤ N ≤ 100 000
Ulaz
7 4 1 4 2 1 9 1
Izlaz
1
Ulaz
4 5 3 5 3
Izlaz
3
Riješi u evaluatoru

Različite riječi

★☆☆ lagano

Koliko je različitih riječi u tekstu?

Ulaz
Jedan redak teksta od malih slova i razmaka.
Izlaz
Broj različitih riječi.
Ograničenja
Tekst ima najviše 100 000 riječi.
Ulaz
mali mrav i mali puž i mrav
Izlaz
4
Riješi u evaluatoru

Kutije

★★☆ srednje

Predmeti stižu na traku jedan za drugim, a znamo masu svakog. Pakiramo ih redom u kutije nosivosti C: predmet ide u trenutnu kutiju ako stane, a ako ne stane, zatvaramo kutiju i otvaramo novu. Koliko je kutija potrebno?

Ulaz
U prvom retku N i C. U drugom retku N masa.
Izlaz
Broj kutija.
Ograničenja
1 ≤ N ≤ 100 000, svaka masa je od 1 do C, C ≤ 10⁹
Ulaz
6 10 4 5 3 7 2 6
Izlaz
3
Treba ti pomoć?

Simulacija: stanje je koliko je već u trenutnoj kutiji. U primjeru su kutije 4 + 5, zatim 3 + 7 i na kraju 2 + 6.

Riješi u evaluatoru

Trojke

★★☆ srednje

Koliko ima trojki brojeva iz liste (na različitim mjestima) čiji je zbroj 0?

Ulaz
U prvom retku N. U drugom retku N cijelih brojeva.
Izlaz
Broj trojki.
Ograničenja
3 ≤ N ≤ 150, brojevi su od −1000 do 1000
Ulaz
5 -1 0 1 2 -1
Izlaz
3
Treba ti pomoć?

N je mali, pa je dovoljna gruba sila sa tri petlje. Koliko je to trojki za N = 150?

Riješi u evaluatoru

Kiša

★★★ teže

Za N dana znamo količinu kiše. Q puta pitamo: kojeg je dana ukupna količina kiše od prvog dana prvi put dosegla barem X? Dani su numerirani od 1. Ako se to nikad ne dogodi, ispiši −1.

Ulaz
U prvom retku N, u drugom N količina. U trećem retku Q, u četvrtom Q brojeva X.
Izlaz
Q redaka s odgovorima.
Ograničenja
1 ≤ N, Q ≤ 100 000, količine su od 0 do 1000, 1 ≤ X ≤ 10⁹
Ulaz
5 3 0 4 1 5 4 3 4 13 14
Izlaz
1 3 5 -1
Treba ti pomoć?

Prefiksni zbrojevi kiše nikad ne padaju, jer količina nije negativna. Zato na njima možeš binarno tražiti prvi dan s p[dan] ≥ X.

Riješi u evaluatoru

Kanui

★★★ teže

Na izletu je N učenika i znamo masu svakog. U kanu stanu najviše dva učenika, a njihova ukupna masa ne smije biti veća od W. Koliko najmanje kanua treba?

Ulaz
U prvom retku N i W. U drugom retku N masa.
Izlaz
Najmanji broj kanua.
Ograničenja
1 ≤ N ≤ 100 000, svaka masa je od 1 do W, W ≤ 10⁹
Ulaz
4 100 80 50 30 20
Izlaz
2
Ulaz
3 10 9 8 7
Izlaz
3
Treba ti pomoć?

Sortiraj mase. Najteži učenik mora u neki kanu. Ako s njim stane najlakši, neka idu zajedno; ako ne stane, najteži ide sam. Pamti dva indeksa: najlakšeg i najtežeg koji još nisu raspoređeni.

Riješi u evaluatoru
Vježbaj dalje: zadaci s natjecanja

Ovi zadaci s Infokupa traže upravo ovo gradivo. Kreni od prvoga.

  1. Promet Infokup 2024 · državno · 6. r. OŠ
  2. Tablica Infokup 2018 · državno · 7. r. OŠ
  3. Igra Infokup 2016 · državno · 5. r. OŠ

5Što smo naučili

  • Prvo pročitaj ograničenja i procijeni složenost.
  • Mali N: gruba sila. Pravila: simulacija. Brojanje i „već viđeno“: rječnik i skup.
  • Mnogo pitanja o zbrojevima: prefiksni zbroj. Sortirani podaci i ogroman N: binarno pretraživanje.
  • „Što više / što manje“: pohlepno, ali tek nakon provjere.
Najčešće greške

Točno, ali presporo rješenje · pohlepno pravilo bez provjere · pomak indeksa za jedan u prefiksnim zbrojevima i binarnom pretraživanju