OpenKattis
Skånemästerskapen 2016

Start

2016-01-30 09:30 CET

Skånemästerskapen 2016

End

2016-01-30 14:30 CET
The end is near!
Contest is over.
Not yet started.
Contest is starting in -3229 days 20:52:43

Time elapsed

5:00:00

Time remaining

0:00:00

Problem D
Rektangelmagi

En magisk sekvens av längd $n + 1$ är en sekvens av tal $a, a + d, a + 2d, ..., a + nd$ för två rationella tal $a$ och $d$, t.ex. $2, 5.5, 9, 12.5$ eller $5, 5, 5$ eller $2, 1, 0, -1, -2$.

En magisk rektangel av storlek $R \times C$ är en rektangel där varje rad och kolumn är en magisk sekvens.

Givet en rektangel av heltal där vissa av talen är bortsuddade, avgör om det går att fylla i dessa bortsuddade tal så att rektangeln är en magisk rektangel.

Indata

Den första raden i indata innehåller talen $R$ och $C$, antalet rader och kolumner i den givna rektangeln. Sedan följer $R$ rader med $C$ heltal vardera.

Ett bortsuddat tal representeras som en punkt.

Utdata

Om ingen lösning finns, skriv ut ej magisk.

Annars, skriv ut $R$ rader med $C$ kolumner - en magisk rektangel där du tagit indatarektangeln och ersatt de bortsuddade talen.

Rationella tal ska anges på formen N/D, där $N$ och $D$ är högst 100 siffror långa. Observera att det inte ska vara mellanslag mellan talen och divisionstecknet.

Om $D = 1$ kan du skriva N.

Poäng

I de första 9 fallen gäller $1 \le R, C \le 6$.

  1. alla tal är redan ifyllda.

  2. Antingen $R$ eller $C$ är 1.

  3. $R = C = 2$

  4. varje testfall har en unik lösning, och rektangeln är konstruerad så att det finns en rad eller kolumn med bara ett bortsuddat tal, och när den fylls i finns det återigen en rad eller kolumn med bara ett tal, osv, ända tills hela rektangeln är ifylld.

  5. varje testfall har en unik lösning som innehåller enbart heltal.

  6. varje testfall har en unik lösning.

  7. varje testfall har antingen en unik lösning som innehåller enbart heltal, eller så har det inte en lösning.

  8. varje testfall har antingen en unik lösning eller ingen lösning alls.

  9. inga ytterligare begränsningar.

  10. inga ytterligare begränsningar, men $1 \le R, C \le 50$.

Sample Input 1 Sample Output 1
3 5
. . 3 . 5
. . . 5 .
. . . . 7
1 2 3 4 5
2 3 4 5 6
3 4 5 6 7
Sample Input 2 Sample Output 2
1 6
4 . . 0 . .
4 8/3 4/3 0 -4/3 -8/3
Sample Input 3 Sample Output 3
1 4
1 2 . 2
ej magisk
Sample Input 4 Sample Output 4
3 3
1 . .
. 2 .
. . 3
1 0 -1
3 2 1
5 4 3