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.|

HILLS - Wieżyca

W ramach integracji członkowie STI wybrali się na wycieczkę w rejon Wieżycy. Wędrowali tu i tam przez cały dzień. W pewnym momencie stwierdzili z przerażeniem, że zrobiło się bardzo, bardzo późno i bardzo, bardzo ciemno, a przy tym bardzo, bardzo daleko od jakiejkolwiek cywilizacji. Mówiąc krótko - zgubili się.

Członkowie STI nie byliby jednak członkami STI, gdyby nie mieli dostępu do odpowiednich na taką okoliczność technologii. W ciągu kilku sekund dysponowali 20 zdjęciami satelitarnymi okolicy i postanowili napisać na poczekaniu program, który przeanalizuje zdjęcia i podpowie dalszą drogę.

Zdjęcia są dostępne pod adresem. Każde zdjęcie jest plikiem graficznym i przedstawia prostokąt o rozmiarze 320x240. Pliki są w formacie raw, 24bpp, interleaved RGB, tj.:

  • Mamy 240 wierszy po 320 pikseli w każdym. Współrzędne piksela to ( x , y ), gdzie 0 <= x <= 319, 0 <= y <= 239. Piksel ( 0 , 0 ) znajduje się w lewym górnym rogu zdjęcia.
  • Każdy piksel zakodowany jest na trzech bajtach pliku. Dla piksela o współrzędnych ( x , y ) będą to bajty o numerach (od 0):
    • 3 * (320 * y + x) [ składowa czerwona koloru ]
    • 3 * (320 * y + x) + 1 [ składowa zielona koloru ]
    • 3 * (320 * y + x) + 2 [ składowa niebieska koloru ]

Kolor piksela opisuje wysokość terenu w odpowiednim punkcie, podobnie jak na tradycyjnych mapach hipsometrycznych. Składowa niebieska jest zawsze zerowa. Wysokość h, w postaci liczby całkowitej z zakresu [ 0 , 255 ], wyznaczamy ze składowej czerwonej r i zielonej g następująco:

  • Jeśli r = 255, to h = 127 + (255 - g),
  • w przeciwnym wypadku h = r - 127.

Dla każdego zdjęcia rozstrzygnij, czy można przejść z dowolnego punktu na lewej krawędzi (x = 0) do dowolnego punktu na prawej krawędzi (x = 319), poruszając się o jeden punkt w górę, dół, prawo lub lewo. Problem byłby trywialny gdyby nie fakt, że studenci są już bardzo, bardzo zmęczeni. Wobec tego nie wolno poruszać się "pod górkę"! Jeśli przechodzimy z punktu p1 na sąsiedni punkt p2, to wysokość p2 musi być mniejsza lub równa wysokości p1!

Twój program (część zgłaszana na SPOJa) powinien wygenerować dokładnie 20 wierszy tekstu. Kolejne wiersze odpowiadają kolejnym zdjęciom hills-in0.raw, hills-in1.raw, hills-in2.raw, ..., hills-in19.raw. Każdy wiersz to słowo "TAK" lub "NIE", odpowiednio jeśli przejście jest możliwe i w przeciwnym wypadku. Zgłaszany program nie powinien niczego wczytywać!

Spodziewane wyjście (niepełne; [...] - komentarz, nie powinien być generowany)

TAK [ dla hills-in0.raw ]
NIE [ dla hills-in1.raw ]
...

Dodane przez:Kuba Białogrodzki
Data dodania:2006-05-01
Limit czasu wykonania programu:0.100s
Limit długości kodu źródłowego50000B
Limit pamięci:1536MB
Cluster: Cube (Intel G860)
Języki programowania:All except: ERL GOSU JS-RHINO NODEJS PERL6 VB.NET

ukryj komentarze
2012-02-25 07:49:19 Jacek Sawicki
Słowo "dowolnego", użyte dwukrotnie w treści zadania wprowadziło w moim przypadku dowolność interpretacji jego znaczenia. Okazało się, że należy je traktować jako "z przynajmniej jednego" a nie "z każdego".
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.