14142번 - Maxplus 다국어

Max-plus algebra je algebra nad realnim brojevima u kojoj su jedine dvije binarne operacije, operacija maksimuma ⊕ i operacija zbrajanja ⊗ . Pri tom operacije ⊗ imaju veći prioritet od operacija ⊕ . Definiramo: 

x ⊕ y = max(x ,y )
x ⊗ y = x + y

Na primjer: 3 ⊕ 5 = 5, 7 ⊕ 4 = 7 , 3 ⊗ 5 = 8 i 7 ⊗ 4 = 11.

U mnogim primjenama ove algebre koristi se matrično max-plus množenje dvaju matrica realnih brojeva A ⊗ B = C. Množenje se definira slično klasičnom množenju matrica, samo se operator '·' (množenje) zamijeni operatorom ⊗ (zbrajanje), a operator '+' (zbrajanje) operatorom ⊕ (maksimum).

U ovom zadatku proučavat ćemo max-plus množenje cjelobrojnih 3×3 matrica: 

\[ \begin{bmatrix} a_{1,1} & a_{1,2}&a_{1,3} \\ a_{2,1} & a_{2,2}&a_{2,3} \\ a_{3,1}&a_{3,2}&a_{3,3} \end{bmatrix} \bigotimes \begin{bmatrix} b_{1,1} & b_{1,2}&b_{1,3} \\ b_{2,1} & b_{2,2}&b_{2,3} \\ b_{3,1}&b_{3,2}&b_{3,3} \end{bmatrix} = \begin{bmatrix} c_{1,1} & c_{1,2}&c_{1,3} \\ c_{2,1} & c_{2,2}&c_{2,3} \\ c_{3,1}&c_{3,2}&c_{3,3} \end{bmatrix} \]

Gdje je: c_i,j = a_i,1 ⊗ b_1,j ⊕ a_i,2 ⊗ b_2,j ⊕ a_i,3 ⊗ b_3,j, dakle c_i,j je najveća od tri sume odgovarajućih elemenata. 

Na primjer: \( \begin{bmatrix} 1 & 2&3 \\ 2 & 3&1 \\ 3&1&4 \end{bmatrix} \bigotimes \begin{bmatrix} 4 & 2&4 \\ 2 & 1&2 \\ 3&2&3 \end{bmatrix} = \begin{bmatrix} 6 & 5&6 \\ 6 & 4&6 \\ 7&6&7 \end{bmatrix} \)

Zadane su matrice A i C ; obje se sastoje od cijelih brojeva po apsolutnoj vrijednosti manjih od 100.

Napišite program koji će pronaći bilo koju matricu B , koja se sastoji od cijelih brojeva po apsolutnoj vrijednosti manjih od 1000, tako da vrijedi: A ⊗ B = C ili ispisati „nemoguce“, ako ne postoji takva matrica. 

U prva tri retka nalaze se po tri cijela broja, matrica A .

U sljedeća tri retka nalaze se po tri cijela broja, matrica C .

Svi brojevi bit će po apsolutnoj vrijednosti manji od 100. 

U tri retka treba ispisati po tri cijela broja, matricu B . Ako ne postoji matrica B takva da vrijedi A ⊗ B = C, u prvi i jedini redak ispišite riječ „nemoguce“.

Brojevi moraju biti po apsolutnoj vrijednosti manji od 1000.

Rješenje ne mora bit jedinstveno.