Apocalypse Now P50934

Al joc Apocalypse Now (com a tots els altres jocs de l’assignatura) és recomanable provar el codi contra el d’altres jugadors. Suposeu, però, que cada parell de jugadors té un grau d’enemistat directa. Es considera que els codis de dos jugadors poden jugar entre ells si tenen una relació d’enemistat directa o indirecta amb suma menor a 100. Per exemple, amb la matriu d’enemistats següent,

els jugadors 0 i 1 podran jugar entre ells, perquè tot i que la seva enemistat directa és 100, passant per 2 tenen una relació que només suma 30.

A més de les enemistats, hi ha un altre inconvenient, i és que no es poden fer tantes partides com es vulgui: cada jugador pot demanar fer un nombre màxim de partides cada dia, que varia en funció de qui sigui (tot i que això no us ho havien dit).

Feu un programa que calculi el mínim nombre de dies per poder fer totes les partides necessàries entre els jugadors que són prou amics.

Entrada

L’entrada consisteix en diversos casos. Cada cas comença amb el nombre de jugadors n, entre 2 i 30. A continuació ve una matriu n × n, simètrica i amb zeros a la diagonal, on a la posició (i, j) hi ha un natural més petit o igual a 100 que indica el grau d’enemistat directa entre i i j. A continuació ve una altra matriu n × n, simètrica i amb zeros a la diagonal, on a la posició (i, j) hi ha un nombre menor que 10000 que indica quantes partides són necessàries per poder provar bé aquelles dues IAs entre si. Finalment venen n nombres entre 1 i 10000, indicant quantes partides diàries pot demanar fer cada jugador.

Sortida

Per a cada cas, escriviu el mínim nombre de dies necessaris perquè tots els jugadors provin les seves IAs tant com cal contra tots els jugadors que són prou amics. Tingueu en compte que quan es juga una partida, la veuen tant el jugador que l’ha demanada com l’altre implicat, sense que a aquest últim li compti com una partida demanada.