ArithmeticHungarian

From CEOIWiki

Jump to: navigation, search

July 12-19
Košice, Slovakia
Task: arithmetic
Language: Hungarian


[edit] Számtani téglalap

Egy számokat tartalmazó négyzetrácsos téglalapot számtani téglalapnak nevezünk, ha minden sora és minden oszlopa is számtani sorozat (a számtani sorozatban a szomszédos elemek különbsége konstans). Egy R\times C méretű négyzetrácson számok és üres cellák vannak. Ki kell tölteni úgy, hogy számtani téglalap legyen belőle!

Példa egy 3\times 5-ös számtani téglalapra:

 1  3  5  7  9
 2  2  2  2  2
 3  1 -1 -3 -5

[edit] Feladat

Írj programot, amely meghatározza, hogy az üres helyeket ki lehet-e úgy tölteni racionális számokkal, hogy számtani téglalapot kapjunk! Ha van megoldás, meg is kell adni egyet!

[edit] Bemenet

Az első sorban a téglalap méretét megadó R és C pozitív egész számok vannak. A következő R sor mindegyike pontosan C elemet tartalmaz, egy-egy szóközzel elválasztva: üres helyet jelölő pontot (.) vagy egész számot.

[edit] Korlátok

Minden X egész számra: -100 \le X \le 100. 10 tesztcsomag van, mindegyik 10 pontot ér. Az első 9 esetén 1 \le R, C \le 6. Az egyes csomagokra az alábbiak teljesülnek:

  • 1. csomag Nincs üres hely.
  • 2. csomag Vagy R = 1 vagy C = 1.
  • 3. csomag R = C = 2.
  • 4. csomag Egyetlen megoldás van, ami az első példa megoldása alapján adható meg.
  • 5. csomag Egyetlen megoldás van, egész számokkal.
  • 6. csomag Egyetlen megoldás van.
  • 7. csomag Vagy egyetlen megoldás van, ami egész számokat tartalmaz, vagy nincs megoldás.
  • 8. csomag Vagy egyetlen megoldás van, vagy nincs megoldás.
  • 9. csomag Tetszőleges bemenet.
  • 10. csomag Tetszőleges bemenet, ahol 1 \le R, C \le 50.

[edit] Kimenet

Ha nincs megoldás, akkor a "No solution." szöveget kell kiírni, idézőjelek nélkül!

Ha több megoldás van, közülük egy tetszőlegeset kell kiírni!

Ha van megoldás, akkor R sort, soronként C racionális számot kell kiírni, egy-egy szóközzel elválasztva!

Minden racionális számot "N/D" alakban kell kiírni, ahol D pozitív egész, N és D relatív prím! Ha D = 1, akkor a "/D" nevezőt nem kell kiírni!

Minden szám legfeljebb 20 számjegyet tartalmaz.

[edit] Példák

input:

3 5
. . 3 . 5
. . . 5 .
. . . . 7

output:

1 2 3 4 5
2 3 4 5 6
3 4 5 6 7

A fenti példában a második sor utolsó száma csak a 6 lehet. Ezután az első és a második sor egyértelműen kitölthető. Majd az első 4 oszlop is kitölthető.

input:

1 6
4 . . 0 . .

output:

4 8/3 4/3 0 -4/3 -8/3

input:

1 4
1 2 . 2

output:

No solution.


input:

3 3
1 . .
. 2 .
. . 3

output:

1 2 3
1 2 3
1 2 3

Ez egy a sok lehetséges megoldás közül.