Programozás‎ > ‎Feladatok‎ > ‎

Tökéletes mátrixok

A tökéletes mátrix élszomszédos celláiban relatív prím pozitív egész számok állnak, vagyis olyan egészek, amelyeknek nincs egynél nagyobb közös osztója, továbbá minden elem egynél nagyobb. 

Például:

 12 25   3
 5 49   121
 3  4  21

Feladat

Írjunk programot, ami egy adott A mátrixról eldönti, hogy van olyan B tökéletes mátrix, 
  • aminek mérete azonos A méretével;
  • és i, j osztója A i, j-nek.

Bemenet

A bemenet első sora az A mátrix sorainak és oszlopainak számát adja meg (1 <= S, O <= 40),
Ezután S sorban O szám következik, A elemei. Ezek pozitív egész számok, továbbá 2 <= A i, j <= 1000.

Kimenet

A kimenet első sora az 1 vagy 0 számot tartalmazza aszerint, hogy létezik vagy nem létezik megfelelő B mátrix.
Ha ez 1, akkor a következő sorokban egy megfelelő B mátrix elemei legyenek, a bemenetnek megfelelő sorrendben.

Példa

Bemenet  Kimenet
2 3
2 4 8
4 8 16
0

4 3
2 9 8
3 60 12
25 34 49
6 10 15     
1
2 3 2
3 2 3
5 17 7
2 5 3

Tesztadatok

matrix.zip (A kimenetekben egy-egy lehetséges mátrixot is megadtunk.)

Címkék

A feladat forrása: Bubble Cup - Student programming contest Serbia, 2010
Algoritmusok: visszalépéses keresés, backtrack

megoldás