English
Zobacz więcej:
- dla uczniów szkół podstawowych: oij.edu.pl/start/
- dla uczniów szkół średnich: oi.edu.pl/l/jak_zaczac/
Zadanie Superkomputer (sup)
Liczba osob: 157
Liczba osob na 100 punktow: 68
Sredni wynik: 55.6306
Superkomputer
Limit pamięci: 256 MB
Bajtazar stworzył superkomputer o bardzo nowatorskiej konstrukcji. Może on zawierać wiele (takich samych) procesorów. Każdy procesor może w jednostce czasu wykonać jedną instrukcję.
Programy nie są w tym komputerze wykonywane sekwencyjnie, lecz mają strukturę drzewa.
Każda instrukcja programu może mieć zero, jedną lub wiele instrukcji następujących po niej.
Po wykonaniu każdej instrukcji należy wykonać instrukcje następujące po niej,
jednak można je wykonać w dowolnej kolejności; w szczególności można je wykonywać równolegle
na różnych procesorach.
Jeśli w superkomputerze jest 
procesorów, to w każdej jednostce czasu będzie można wykonać równolegle co najwyżej 
instrukcji.
Bajtazar ma do uruchomienia pewien program. Ponieważ chce optymalnie wykorzystywać swoje zasoby, zastanawia się, jak liczba procesorów wpłynie na szybkość obliczeń. Prosi Cię o określenie, dla danego programu i liczby procesorów, najkrótszego możliwego czasu wykonania tego programu z użyciem superkomputera o tylu procesorach.
Wejście
W pierwszym wierszu standardowego wejścia znajdują się dwie liczby całkowite 
i 
(
) oddzielone pojedynczym odstępem, oznaczające liczbę
instrukcji programu Bajtazara oraz liczbę zapytań.
W drugim wierszu wejścia znajduje się ciąg 
liczb całkowitych 
(
)
pooddzielanych pojedynczymi odstępami: 
oznacza liczbę procesorów, którymi dysponuje Bajtazar
w 
-tym zapytaniu.
W trzecim i ostatnim wierszu wejścia znajduje się ciąg 
liczb całkowitych 
(
) pooddzielanych pojedynczymi odstępami: 
określa numer instrukcji, po której następuje
instrukcja numer 
.
Instrukcje numerowane są kolejnymi liczbami naturalnymi od 1 do 
, przy czym instrukcja numer 1 to pierwsza instrukcja programu.
W testach wartych łącznie 35% punktów zachodzi dodatkowo warunek: 
, 
.
W podzbiorze tych testów wartym łącznie 20% punktów zachodzi dodatkowo warunek: 
, 
.
Wyjście
Twój program powinien wypisać na standardowe wyjście jeden wiersz zawierający ciąg
liczb całkowitych pooddzielanych pojedynczymi odstępami:
-ta z tych liczb powinna określać minimalny czas wykonania programu przy założeniu, że superkomputer Bajtazara posiada
procesorów.
Przykład
Dla danych wejściowych:
20 1 3 1 1 1 3 4 3 2 8 6 9 10 12 12 13 14 11 11 11 11
poprawną odpowiedzią jest:
8
Wyjaśnienie do przykładu:
Wykonanie programu może wyglądać następująco:
| Czas | Instrukcje | ||||||||||||||||||||||||||||||||
|
|
Testy "ocen":
- 1ocen:
, 
, drzewo instrukcji jest ścieżką; - 2ocen:
, 
, mały losowy test;
- 3ocen:
, 
, wszystkie instrukcje następują po instrukcji nr 
;
- 4ocen:
, 
, instrukcje tworzą pełne drzewo binarne;
- 5ocen:
, 
, drzewo instrukcji jest długą ścieżką.
Autor zadania: Michał Włodarczyk.
<Wyślij rozwiązanie> [0/100]