Zgłaszanie | Wszystkie zgłoszenia | Najlepsze | Lista |
MWP2_1F - Avatar |
Widziałeś już najnowszy film Jamesa Camerona - "Avatar"? Wytwórnia wyłożyła na niego 250 milionów dolarów. Chodzą jednak słuchy, że tak naprawdę kosztował dwa razy tyle czyli bagatela pół miliarda dolarów. Zastanawiamy się czy te pieniądze się w ogóle zwrócą. Oczywiście ponieważ nie możemy tego oszacować w rzeczywistości, wymyśliliśmy prostą grę, która ma nam w tym pomóc. Nazwaliśmy ją "Wyszukiwanie pieniędzy". W grze tej mamy bardzo dużą tablicę z pewnymi kwotami pieniędzy podanymi w tysiącach dolarów oraz pewną początkową liczbę naturalną S. W każdym kroku gry wykonujemy następujące kroki:
- Dzielimy liczbę S przez 2 i wynik dzielenia zapisujemy z powrotem w S. Jeżeli liczba S nie jest podzielna bez reszty przez 2 to wynik zaokrąglamy w dół.
- W tablicy z kwotami pieniędzy wyszukujemy kwotę równą S. Jeżeli S nie występuje w tablicy to wyszukujemy kwotę większą od S i jednocześnie jak najbardziej do niej zbliżoną. Znalezioną kwotę oznaczmy jako X. Liczbie S przypisujemy wartość X.
- Sprawdzamy jaki numer porządkowy w tablicy ma kwota X w kolejności niemalejącej. Numer ten dodajemy do wyniku rozgrywki. Zakładamy, że najmniejsza kwota w tablicy ma numer 0.
- Jeżeli wynik przekracza wartość 500000 lub trafiliśmy na kwotę o numerze porządkowym równym 0 to kończymy grę.
Jeżeli po zakończeniu gry wynik przekracza 500000 to znaczy, że Cameron miał farta ;-)
Wejście
W pierwszej linii wejścia znajduje się jedna liczba naturalna d (1 ≤ d ≤ 1000) określająca ilość zestawów danych. W kolejnych liniach znajdują się zestawy danych.
Każdy zestaw danych składa się z 3 linii. W pierwszej linii znajduje się liczba n (2 ≤ n ≤ 500000) określająca ilość kwot w tablicy. W kolejnej linii znajduje się n kwot oddzielonych pojedynczymi spacjami. W ostatniej linii znajduje się jedna liczba naturalna S (1 ≤ S ≤ 1000001).
Wyjście
Dla każdego zestawu należy w osobnej linii wypisać TAK, jeżeli po zakończeniu gry wynik przekracza 500000 albo NIE w przeciwnym wypadku.
Przykład
Wejście:
1 5 2 5 4 3 1 10
Wyjście:
NIE
Wyjaśnienie przykładu
Jako, że część osób źle zrozumiała zasady naszej gry poniżej prezentujemy przebieg gry przykładowej:
- Dzielimy S przez 2. Jako, że 10 dzieli się bez reszty to nowa wartość S to 5.
- Wyszukujemy 5 w tablicy. Jest ono 4 w kolejności niemalejącej, tak więc wynik przyjmuje początkową wartość 4 zaś nowa wartość S to 5.
- Dzielimy S przez 2. Ponieważ nie jest podzielne bez reszty nowa wartość S to 2.
- Wyszukujemy 2 w tablicy. Kwota 2 ma numer porządkowy 1. Dodajemy 1 do wyniku otrzymując 5. Nowa wartość S to 2.
- Dzielimy S przez 2, otrzymujemy 1. Kwota 1 ma zerowy numer w kolejności niemalejącej, tak więc nic nie dodajemy do wyniku.
- Ponieważ trafiliśmy na najmniejszy element w tablicy to kończymy grę z wynikiem 5. Cameron nie miał szczęścia.
Dodane przez: | Maciej Boniecki |
Data dodania: | 2010-01-07 |
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: NODEJS OBJC PERL6 SCM qobi SQLITE VB.NET |