Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

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ę liczbą 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łowego50000B
Limit pamięci:1536MB
Cluster: Cube (Intel G860)
Języki programowania:All except: GOSU

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.