La falciatura del campo#10594
Fermer Giovanni è piuttosto affidabile in tutti gli aspetti della gestione della sua fattoria, tranne uno: non è per nulla capace di falciare l'erba in modo tempestivo e organizzato.
La fattoria è rappresentata da una grande griglia bidimensionale di celle quadrate, ciascuna di area unitaria. Al momento t = 0 Fermer Giovanni si trova inizialmente in una di queste celle e falcia l'erba in essa, quindi inizialmente questa è l'unica cella con l'erba falciata. Il successivo percorso di Fermer Giovanni è descritto da una sequenza di comandi. Ad esempio, se il primo comando è "W 10", allora nei momenti t = 1 fino a t = 10 (cioè nelle successive unità di tempo) Fermer Giovanni si sposta di una cella verso ovest a ogni passo, falciando l'erba in ogni cella visitata. Dopo aver eseguito questi passi, al momento t = 10 si troverà celle a ovest della sua posizione iniziale, avendo falciato l'erba in tutte le celle attraversate.
Fermer Giovanni si muove così lentamente che parte dell'erba da lui falciata potrebbe fare in tempo a ricrescere prima che finisca di falciare. Qualsiasi erba falciata al momento ricresce nuovamente al momento t + x.
Il percorso di Fermer Giovanni può far sì che egli visiti più volte la stessa cella. Tuttavia, egli osserva che non visita mai una cella mentre l'erba in essa è ancora falciata. In altre parole, ogni volta che visita una cella, la sua precedente visita a quella stessa cella deve essere avvenuta almeno unità di tempo prima, affinché l'erba abbia fatto in tempo a ricrescere.
Determinate il massimo valore possibile di per cui l'osservazione di Fermer Giovanni rimane vera.
Nella prima riga è contenuto un intero n~(1 \le n \le 100). In ciascuna delle successive righe è contenuto un comando della forma "d s", dove — è un carattere che indica la direzione ( = nord, = est, = sud, = ovest), e s~(1 \le s \le 10) — è il numero di passi da compiere in quella direzione.
Stampate il valore massimo di per cui Fermer Giovanni non calpesta mai una cella con l'erba falciata. Se Fermer Giovanni non visita mai alcuna cella più di una volta, stampate .
In questo esempio Fermer Giovanni visita una cella al momento , che aveva già visitato al momento . Di conseguenza, deve essere non superiore a ; altrimenti, l'erba dopo la prima visita non avrebbe fatto in tempo a ricrescere. Egli visita anche una cella al momento , che aveva già visitato al momento , quindi deve essere anche non superiore a . Poiché il primo di questi due vincoli è il più restrittivo, si ottiene che può essere al massimo .
Esempio 1