7/24/2019 11-12_immortal (1)

1/1

Clasele a XIa i a XII-a

Problema 1 immortal 100 puncte

Cei care au vzut filmul Nemuritorul, tiu c fraza cu care nemuritorii ncep lupta este "Nu poate srmn dect unul singur". S ncercm s simulm povestea nemuritorilor.

ntr-o zon dreptungiular format din nlinii !numerotate de la 1la n i mcoloane !numerotate dela 1la m se afl ma#im nxm-1nemuritori. $oi nemuritori vecini se "lupt" ntre ei i cel care pierdelupta este eliminat. "%upta" const n sritura unuia dintre nemuritori peste cellalt, dac aceastsritur se poate face. Sritura se poate face pe orizontal sau vertical i nemuritorul peste care s-asrit dispare. &rin vecin al nemuritorului din pozi'ia (i,j)n'elegem un nemuritor din una dintre

pozi'iile (i-1,j), (i+1,j), (i,j-1), (i,j+1). $eci, dup lupt nemuritorul din cmpul (i,j)seva gsi n una dintre pozi'iile( (i-2,j), (i+2,j), (i,j-2)sau(i,j+2), dac aceast pozi'ie esteli)er i este n interiorul zonei.

Cerin

Se cere s se determine o succesiune a luptelor ce pot fi purtate, astfel nct la final s rmn unsingur nemuritor.

Date de intrare*iierul de intrare immortal.incon'ine pe prima linie trei valori naturale n m I, separate prin cteun spa'iu, reprezentnd numrul de linii, numrul de coloane ale zonei descrise i respectiv numrulde nemuritori e#isten'i ini'ial. +rmtoarele Ilinii con'in fiecare cte dou numere naturale x yseparate printr-un spa'iu, reprezentnd pozi'iile unde se gsesc ini'ial cei I nemuritori !linia icoloana.

Date de ieire

*iierul de intrare immortal.outva con'ine I-1linii, fiecare linie descriind o "lupt". %uptele vorfi scrise n ordinea n care au avut loc. linie va con'ine numere naturale care indic( primeledou pozi'ia de pe care pleac un nemuritor la "lupt", ultimele dou pozi'ia pe care acesta aungedup "lupt". &entru ca "lupta" s fie corect, n pozi'ia peste care nemuritorul "sare" tre)uie se#iste un nemuritor care va "muri". pozi'ie va fi specificat prin indicele de linie urmat deindicele de coloan. /alorile scrise pe aceeai linie vor fi separate prin spa'ii.

Restricii1 < n, m 20

1 < I min{15, n*m-1}

&entru datele de test e#ist ntotdeauna solu'ie.

Exempluimmortal.in immortal.out

3 4 4

1 2

2 1

3 2

3 3

3 3 3 1

3 1 1 1

1 1 1 3

1 2 3 4

(3,3) --! (3,1) "i#$ar% (3,2)

1& & * & & & (3,1) --! (1,1) "i#$ar% (2,1)

&---------------& (1,1) --! (1,3) "i#$ar% (1,2)

2& * & & & &

&---------------&

3& & * & * & &

imp maxim de execuie!test"0.1 secunde2test#emorie total disponibil" 3 45, din care 6 45 pentru stiv.Dimensiune maxim a sursei"30 75