Zgłaszanie | Wszystkie zgłoszenia | Najlepsze | Lista |
FR_12_16 - Ice Tower |
Nie zna życia ten, kto nie grywał w Ice Tower na szkolnych komputerach w czasie przerwy przed i po lekcji informatyki (w trakcie lekcji także). To prosta gra platformowa, w której skaczesz po platformach, aby dostać się na szczyt bardzo wysokiej wieży.
Jako doświadczony gracz postanawiasz nieco utrudnić sobie wyzwanie (jest za to odpowiednia odznaka w grze).
Przypomnijmy sobie jakie zasady obowiązują:
- Zaczynasz z dowolnej najniżej położonej platformy.
- Celem jest dotarcie na jedną z najwyżej położonych platform wykonując jak najmniej skoków.
- Możesz skakać tylko prosto w górę (nie wolno skręcać w czasie lotu).
- Nie wolno przeskakiwać między platformami na tym samym poziomie.
- Nie wolno schodzić na platformy poniżej tej, na której jesteś obecnie.
- Nie wolno przeskakiwać kilka platform równocześnie. Zawsze wskakujesz na pierwszą platformę wiszącą nad Tobą.
- Możesz skakać dowolnie wysoko (ale tylko do najbliższej platformy nad Tobą).
- Możesz się dowolnie przesuwać w obrębie jednej platformy.
Dla każdej platformy na najwyższym poziomie policz ile najmniej skoków należy wykonać, aby się tam dostać. Jeżeli jest to niemożliwe, wypisz NIE.
Wejście
W pierwszej linii wejścia znajduje się liczba zestawów danych t (0 < t < 10). W kolejnych liniach znajdują się zestawy danych.
W pierwszej linii każdego zestawu danych znajduje się liczba platform n (0 < n < 106).
W kolejnych n liniach znajdują się opisy platform. Platforma opisana jest trzema nieujemnymi wartościami: w, p, k oznaczającymi odpowiednio: wysokość na jakiej się znajduje (w < 105), jej początek i koniec (p, k < 2×107). W obrębie jednej wysokości platformy nie nachodzą na siebie i jest między nimi odstęp co najmniej 1. Platforma ma zawsze niezerową długość (p < k).
Wyjście
Na wyjściu należy wypisać t linii. Każda linia powinna zawierać wynik dla pojedynczego zestawu danych. Wynik dla pojedynczego zestawu danych powinien składać się z wyników dla każdej z najwyżej położonych platform. Wynik dla pojedynczej platformy to minimalna liczba skoków jaką należy wykonać, aby się na nią dostać albo słowo NIE jeżeli jest to niemożliwe. Wyniki dla platform wypisujemy w kolejności rosnących wartości ich początków p.
Przykład
Wejście:
2 2 0 0 5 5 4 10 11 1 5 6 1 2 4 2 3 5 3 3 5 4 3 5 5 3 5 6 2 6 7 2 3 8 0 3 9 0 1 9 6 10
Wyjście
1 4 NIE
Dodane przez: | Grzegorz Spryszyński |
Data dodania: | 2021-01-11 |
Limit czasu wykonania programu: | 1s-2s |
Limit długości kodu źródłowego | 50000B |
Limit pamięci: | 1536MB |
Cluster: | Cube (Intel G860) |
Języki programowania: | All except: ASM32-GCC MAWK BC C-CLANG NCSHARP CPP14-CLANG COBOL COFFEE D-CLANG D-DMD ELIXIR FANTOM FORTH GOSU GRV JS-MONKEY JULIA KTLN NIM OBJC OBJC-CLANG OCT PICO PROLOG R RACKET RUST SCM qobi CHICKEN SQLITE SWIFT UNLAMBDA VB.NET |