Zadanie 2. Trafione setki

Tomek i Kasia przez całe lato zbierali czereśnie. Każdego dnia udało im się zebrać dokładnie 15 kobiałek. Co więcej, codziennie jedna z kobiałek zawierała dokładnie 100 zebranych czereśni. Kasia codziennie zapisywała liczby czereśni w kobiałkach do pliku czeresnie.txt, przy okazji sortując kobiałki niemalejąco w ramach każdego dnia. Liczby czereśni w kobiałkach w ramach każdego dnia znajdują się w osobnych wierszach:

Napisz program, który dla każdego dnia z pliku czeresnie.txt wyznaczy, która z kolei była najmniejsza kobiałka, zawierająca 100 czereśni i zapisze wyznaczoną pozycję do odpowiadającego wiersza pliku pozycje.txt. Pamiętaj, że pomimo numerowania od 0 w komputerze, na co dzień numerujemy zaczynając od 1.

Uwaga: Wyszukiwanie kobiałki w ramach jednego dnia powinno mieć czasową złożoność obliczeniową, niższą niż liniowa.

Specyfikacja problemu:

Dane:

• czeresnie[][] – tablica liczb naturalnych, w której dla każdego dnia przechowywane jest 15 liczb całkowitych z przedziału $⟨1,200⟩$, oznaczających liczby zebranych czereśni do kobiałek danego dnia

Wynik:

• pozycje[] – tablica 90 liczb naturalnych, oznaczających, która z kolei najmniejsza była kobiałka zawierająca 100 czereśni z odpowiadającej podtabeli czeresnie[][]

Rozwiązanie

Schemat oceniania

• 2 pkt – za prawidłową odpowiedź,

• 1 pkt – za odpowiedź o złożoności obliczeniowej wyszukiwania gorszej niż logarytmiczna,

• 0 pkt – za nieprawidłową odpowiedź lub brak odpowiedzi.

Odpowiedzi do zadania

pozycje.txt