Esplorando Marte (marte)

In una futura missione su Marte, un guscio contenente alcuni Veicoli per l'Esplorazione di Marte (VEM), numerati da 1 a N, atterrerà sulla superficie di Marte. Tutti i VEM saranno lasciati sul sito di atterraggio del guscio. Da lì dovranno raggiungere un trasmettitore che atterrerà poco lontano.
Nel loro viaggio verso il trasmettitore, i veicoli dovranno raccogliere campioni di rocce. Da ogni roccia si potrà prelevare un solo campione; a prelevarlo sarà il primo VEM a passare per quella roccia. La roccia non potrà offrire nuovi campioni, ma altri VEM potranno passarci sopra. I veicoli non potranno muoversi su terreni inagibili.

Il progetto del VEM è tale che esso può muovere solo a sud o a est, nel percorso che lo porterà al trasmettitore. Più VEM possono occupare la stessa posizione allo stesso tempo.

Dovete calcolare i singoli movimenti di ogni veicolo in modo da massimizzare il numero dei campioni di roccia raccolti e il numero di VEM a raggiungere il trasmettitore, usando i VEM atterrati con il guscio.

Attenzione: se un VEM non riesce a raggiungere il trasmettitore i suoi campioni saranno persi e non potranno essere recuperati nemmeno tornando sulle rocce da cui li ha presi.

Dati in input

La superficie del pianeta tra il guscio e il trasmettitore è rappresentata da una griglia di P colonne e Q righe con la posizione del guscio sempre a (1,1) e quella del trasmettitore a (P, Q). Ogni cella della griglia puo' essere di tipo:

• 0: terreno libero;
• 1: terreno inagibile;
• 2: terreno campionabile.

Nella prima riga del file input.txt è presente il numero N dei VEM nel guscio, nella seconda riga il numero di colonne P, nella terza il numero di righe Q e poi nelle successive Q righe P interi, ciascuno dei quali rappresentanti lo stato della corrispondente cella sulla griglia.
N, P e Q sono 3 interi con 1 ≤ N ≤ 1000, 1 ≤ P ≤ 255 e 1 ≤ Q ≤ 255.

Dati in output

Il file output.txt contiene una sequenza di linee rappresentanti i movimenti dei VEM verso il trasmettitore. Ogni linea conterrà il numero di un veicolo e una cifra, 0 o 1, dove 0 è una mossa di quel veicolo verso sud e 1 una mossa verso est.

Punteggio

Il calcolo del punteggio sarà basato sul numero di campioni raccolti e sull'arrivo o sul mancato arrivo dei VEM al trasmettitore. Una mossa illegale (fuori dalla griglia o su un terreno inagibile) invaliderà tutta la soluzione.

Punteggio = ( ( Numero dei campioni raccolti ) + ( Numero dei VEM arrivati al trasmettitore ) - ( Numero dei VEM non arrivati al trasmettitore ) ) / ( Massimo numero di campioni portabili al trasmettitore + N ) * 100

Quindi il minimo punteggio per ogni input è 0, il massimo 100.

Assunzioni

È sempre possibile arrivare dal sito di atterraggio al trasmettitore.

Esempio

File input.txt

2
10
8
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 1 1 0 0 0
0 0 0 1 0 2 0 0 0 0
1 1 0 1 2 0 0 0 0 1
0 1 0 0 2 0 1 1 0 0
0 1 0 1 0 0 1 1 0 0
0 1 2 0 0 0 0 1 0 0
0 0 0 0 0 0 0 0 0 0

File output.txt

1 1
1 0
2 1
2 0
1 1
1 1
2 0
2 1
2 0
2 0
2 0
2 0
1 1
1 0
1 0
1 0
1 0
1 0
1 0
2 0
2 1
1 1
1 1
1 1
1 1
1 1
2 1
2 1
2 1
2 1
2 1
2 1