Zgłaszanie | Wszystkie zgłoszenia | Najlepsze | Lista |
FR_17_06 - Czekolada |
Tak to dziś! Kolejna edycja konkursu "FRAKTAL". Wybitni autorzy zadań zawitali w mieście wielu algorytmów, czyli w Działdowie.
Podczas przywitania włodarze Marcin i Tomasz chcieli ugościć wspaniałych autorów Maćka i Grześka kubkiem gorącej czekolady. Gospodarze przygotowali n identycznych kubków o pojemności p i ustawili je w jednym rzędzie. Gdy Grzesiek sięgał po pierwszy kubek, w tym momencie Marcin krzyknął: "Hola Hola! Nie ma tak łatwo! Przygotowaliśmy dla was zagadkę. Jeśli na nią odpowiesz, to dostaniesz wybrany przez siebie kubek z czekoladą."
Kubki zostały ponumerowane od 1 do n. Tomasz do każdego kubka nalał (lub nie) pewną ilość czekolady. Natomiast Marcin wykonywał następujące czynności:
- Z pierwszego kubka przelał możliwie dużo czekolady do drugiego kubka.
- Z drugiego kubka przelał możliwie dużo czekolady do trzeciego kubka.
- Z trzeciego do czwartek i tak dalej aż dotarł do ostatniego kubka. Jego zawartości już nigdzie nie przelewał.
- Następnie Marcin rozpoczynał przelewanie od początku.
Powyższe czynności zostały wykonywane tak długo, jak długo możliwe było wykonanie chociażby jednego przelania w całym cyklu.
A oto jest pytanie — powiedział Tomek, "znając początkowe zawartości kubków podaj ilość czekolady w i-tym kubku".
Czyżby zadanie było arcytrudne? Być może. Grzesiek już zna odpowiedź, a Ty?
Wejście
W pierwszym wierszu znajdują się dwie liczby n i p określające liczbę kubków oraz ich pojemności 0 < n, p < 2001.
W kolejnym wierszu znajduje się n liczb całkowitych z zakresu [0..p] określających początkową zawartosć czekolady w kolejnych kubkach (w przynajmniej jednym kubku jest czekolada).
W trzecim wierszu znajduje się jedna liczba q określająca ilość zapytań, nie większa niż 2000.
W kolejnych q wierszach znajduje się numer kubka, dla którego należy podać ostateczną ilość czekolady. Kubki numerujemy od 1 do n.
Wyjście
Dla każdego zapytania jedna liczba określająca zawartość kubka.
Przykład
Wejście:
5 5 1 2 4 4 5 3 1 2 5
Wyjście:
0 1 5
Dodane przez: | Marcin Kasprowicz |
Data dodania: | 2023-04-18 |
Limit czasu wykonania programu: | 1s |
Limit długości kodu źródłowego | 50000B |
Limit pamięci: | 1536MB |
Cluster: | Cube (Intel G860) |
Języki programowania: | All except: ASM32-GCC COBOL D-CLANG D-DMD ELIXIR FANTOM GOSU GRV JS-MONKEY NIM OBJC OBJC-CLANG PICO RUST SCM qobi CHICKEN VB.NET |