immortal

Time limit: 0.4s
Memory limit: 4MB
Input: immortal.in
Output: immortal.out

Cei care au văzut filmul Nemuritorul, ştiu că fraza cu care nemuritorii încep lupta este "Nu poate să rămână decât unul singur". Să încercăm să simulăm povestea nemuritorilor.

Într-o zonă dreptunghiulară formată din nn linii (numerotate de la 11 la nn) şi mm coloane (numerotate de la 11 la mm) se află maxim n×m1n \times m-1 nemuritori. Doi nemuritori vecini se "luptă" între ei şi cel care pierde lupta este eliminat. "Lupta" constă în săritura unuia dintre nemuritori peste celălalt, dacă această săritură se poate face. Săritura se poate face pe orizontală sau verticală şi nemuritorul peste care s-a sărit dispare. Prin vecin al nemuritorului din poziţia (i,j)(i, j) înţelegem un nemuritor din una dintre poziţiile (i1,j),(i+1,j),(i,j1),(i,j+1)(i-1,j), (i+1,j), (i,j-1), (i,j+1). Deci, după luptă nemuritorul din câmpul (i,j)(i,j) se va găsi în una dintre poziţiile: (i2,j),(i+2,j),(i,j2)(i-2,j), (i+2,j), (i,j-2) sau (i,j+2)(i,j+2), dacă această poziţie este liberă şi este în interiorul zonei.

Cerinţă

Se cere să se determine o succesiune a luptelor ce pot fi purtate, astfel încât la final să rămână un singur nemuritor.

Date de intrare

Fişierul de intrare immortal.in conţine pe prima linie trei valori naturale nmIn m I, separate prin câte un spaţiu, reprezentând numărul de linii, numărul de coloane ale zonei descrise şi respectiv numărul de nemuritori existenţi iniţial. Următoarele II linii conţin fiecare câte două numere naturale x yx\ y separate printr-un spaţiu, reprezentând poziţiile unde se găsesc iniţial cei II nemuritori (linia şi coloana).

Date de ieşire

Fişierul de intrare immortal.out va conţine I1I-1 linii, fiecare linie descriind o "luptă". Luptele vor fi scrise în ordinea în care au avut loc. O linie va conţine 44 numere naturale care indică: primele două poziţia de pe care pleacă un nemuritor la "luptă", ultimele două poziţia pe care acesta ajunge după "luptă". Pentru ca "lupta" să fie corectă, în poziţia peste care nemuritorul "sare" trebuie să existe un nemuritor care va "muri". O poziţie va fi specificată prin indicele de linie urmat de indicele de coloană. Valorile scrise pe aceeaşi linie vor fi separate prin spaţii.

Restricţii

  • 1<n,m201 < n, m ≤ 20
  • 1<Imin15,n×m11 < I ≤ min{15, n \times m-1}
  • Pentru datele de test există întotdeauna soluţie.

Exemplu

immortal.in

3 4 4
1 2
2 1
3 2
3 3

immortal.out

3 3 3 1
3 1 1 1
1 1 1 3

Explicații

   1   2   3   4
 =================   
1|   | * |   |   |    
 |---------------|   
2| * |   |   |   |
 |---------------|
3|   | * | * |   |
 =================

(3,3)(3,1)(3, 3) \rarr (3,1) dispare (3,2)(3, 2)
(3,1)(1,1)(3, 1) \rarr (1,1) dispare (2,1)(2, 1)
(1,1)(1,3)(1, 1) \rarr (1,3) dispare (1,2)(1, 2)

Problem info

ID: 41

Editor: liviu

Author:

Source: OJI 2010 XI-XII: Problema 1

Tags:

OJI 2010 XI-XII

Log in or sign up to be able to send submissions!