ArithmeticHungarian
From CEOIWiki
![]() |
July 12-19
|
[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 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 -ö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: .
10 tesztcsomag van, mindegyik 10 pontot ér.
Az első 9 esetén
.
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
.
[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.