Perché la mucca ha attraversato la strada (Oro)#10538
La fattoria di Farmer John è una griglia quadrata n \times n di campi. All'interno della fattoria ci sono n - 1 strade che vanno da nord a sud e n - 1 strade che vanno da est a ovest, che separano i campi adiacenti. Lungo il perimetro della fattoria è installata un'alta recinzione che impedisce alle mucche di lasciare la fattoria. La mucca Bessie può spostarsi liberamente da qualsiasi campo a qualsiasi campo adiacente (a nord, est, sud o ovest), a condizione che, prima di attraversare la strada che separa due campi, guardi attentamente in entrambe le direzioni. Attraversare una singola strada le richiede unità di tempo.
Un giorno, Farmer John invita Bessie a casa sua per giocare a scacchi in amicizia. Bessie inizia il suo cammino dal campo situato nell'angolo nord-ovest, mentre la casa di Farmer John si trova nel campo nell'angolo sud-est, quindi Bessie dovrà percorrere un tragitto piuttosto lungo. Lungo il percorso si affamerà e si fermerà a mangiare l'erba a ogni terzo campo che visita (il campo iniziale non viene conteggiato, ma l'ultimo campo in cui si ferma potrebbe risultare essere proprio il campo con la casa di Farmer John). Alcuni campi hanno erba migliore di altri, quindi il tempo necessario a Bessie per fermarsi e mangiare l'erba dipende dal campo in cui si ferma.
Aiuta Bessie a determinare il tempo minimo in cui può raggiungere la casa di Farmer John.
La prima riga contiene n~(3 \le n \le 100) e t~(0 \le t \le 10^6). Le successive righe contengono numeri interi positivi ciascuna (ognuno non superiore a 10^5), che descrivono il tempo necessario per mangiare l'erba in ogni campo. Il primo numero della prima riga corrisponde al campo nell'angolo nord-ovest.
Stampa il tempo minimo necessario a Bessie per raggiungere la casa di Farmer John.
In questo esempio, il percorso ottimale consiste nel camminare verso est per campi e mangiare l'erba, il che richiede unità di tempo, poi camminare due campi verso sud e un campo verso est e mangiare l'erba, il che richiede unità di tempo, e infine camminare un campo verso sud e un campo verso est, raggiungendo la meta.
Esempio 1