Robot na siatce

Zadanie 15 z 15 · rozdział 17Trudność: 2 z 3dictkrotkizbiory

Treść zadania

Robot stoi na polu $(0, 0)$ nieskończonej kratkowanej płaszczyzny i wykonuje ciąg ruchów:

  • N — o jedno pole na północ: $y$ rośnie o 1,
  • S — na południe: $y$ maleje o 1,
  • E — na wschód: $x$ rośnie o 1,
  • W — na zachód: $x$ maleje o 1.

Pole startowe liczy się jako odwiedzone raz, a każdy ruch to jedno odwiedzenie pola, na które robot wchodzi. Wypisz:

  1. liczbę różnych odwiedzonych pól (razem z polem startowym),
  2. najczęściej odwiedzane pole i liczbę jego odwiedzin; przy remisie — to z nich, które robot odwiedził po raz pierwszy najwcześniej,
  3. Tak, jeśli po wykonaniu wszystkich ruchów robot stoi na polu startowym, w przeciwnym razie Nie.

Dane wejściowe

  • 1. linia: ciąg ruchów złożony z liter N, S, E, W (bez spacji)

Dane wyjściowe

  • 1. linia: liczba różnych odwiedzonych pól
  • 2. linia: x y k — współrzędne najczęściej odwiedzanego pola i liczba jego odwiedzin
  • 3. linia: Tak albo Nie

Ograniczenia

  • ciąg ma od 1 do 1000 ruchów

Uwagi

  • Pozycję trzymaj jako krotkę (x, y). Krotki — w przeciwieństwie do list — mogą być kluczami słownika i elementami zbioru, np. odwiedziny[(0, 0)] = 1.
  • Krotkę łatwo „rozpakować” do zmiennych: x, y = pozycja. Przesunięcia też można trzymać w słowniku: RUCHY = {"N": (0, 1), "S": (0, -1), "E": (1, 0), "W": (-1, 0)}, a potem dx, dy = RUCHY[ruch].
  • Liczba różnych pól to liczba kluczy słownika odwiedzin — albo rozmiar zbioru (set) odwiedzonych pozycji.
  • Kolejność kluczy w słowniku to kolejność pierwszego wstawienia, co ułatwia rozstrzygnięcie remisu.

Przykład

Wejście
NESW
Wyjście
4
0 0 2
Tak

Robot odwiedza kolejno pola $(0, 0)$, $(0, 1)$, $(1, 1)$, $(1, 0)$ i znowu $(0, 0)$ — to pole odwiedził dwa razy.

Potrzebujesz teorii?

Zasady obowiązujące w rozdziale 17

Zadania w tym rozdziale ćwiczą pracę ze słownikami (dict): tworzenie, dodawanie i usuwanie par, zliczanie wystąpień oraz grupowanie danych według klucza.
Każde zadanie (oraz każdy podpunkt) jest osobnym, niezależnym programem: czyta standardowe wejście (stdin) i wypisuje wynik na standardowe wyjście (stdout).

Konwencje wspólne:

  • Dane wczytuj dokładnie w kolejności podanej w sekcji Wejście; jeśli w jednej linii jest kilka wartości — rozbij ją po spacjach.
  • Jeśli wynikiem jest słownik, wypisz go tak, jak robi to print(slownik) w Pythonie: {klucz: wartość, klucz: wartość} — pary oddzielone przecinkiem i spacją, po dwukropku spacja, klucze i wartości napisowe w apostrofach (np. {'ala': 2, 'ma': 1}), liczby bez apostrofów (np. {1: 1, 2: 4}), pusty słownik to {}.
  • Kolejność par w wypisanym słowniku to kolejność, w jakiej klucze były do niego dodawane (tak zachowuje się słownik w Pythonie).
  • Program nie wypisuje komunikatów typu „Podaj liczbę:”.

Zadanie pochodzi z otwartego zbioru Nauka-Programowania (z rozwiązaniami wzorcowymi). Zgłoś błąd w treści lub testach.

Python uruchomi się w przeglądarce przy pierwszym teście.

Kod zapisuje się automatycznie w tej przeglądarce. Tab wstawia wcięcie; aby opuścić edytor klawiaturą, naciśnij Esc, a potem Tab.

Testy

Program dostaje „Wejście” przez input() i musi wypisać „Oczekiwane wyjście”. Liczby porównywane są z tolerancją 0,01, a tekst podany w input("…") nie jest sprawdzany.

Test 1

Nie uruchomiono
Wejście
N
Oczekiwane wyjście
2
0 0 1
Nie

Test 2

Nie uruchomiono
Wejście
NNSS
Oczekiwane wyjście
3
0 0 2
Tak

Test 3

Nie uruchomiono
Wejście
EEWWEE
Oczekiwane wyjście
3
1 0 3
Nie

Test 4

Nie uruchomiono
Wejście
SSWWNNEE
Oczekiwane wyjście
8
0 0 2
Tak

Test 5

Nie uruchomiono
Wejście
SSSNN
Oczekiwane wyjście
4
0 -1 2
Nie

Test 6

Nie uruchomiono
Wejście
NWWEE
Oczekiwane wyjście
4
0 1 2
Nie

Test 7

Nie uruchomiono
Wejście
NNEESSWWNE
Oczekiwane wyjście
9
0 0 2
Nie
Uruchom z własnymi danymi