ID #123 · Colecția InfoAs · Operatori și expresii

Problema Comoara

Gigel a realizat harta casei lui sub formă de matrice `n × n`, în care fiecare căsuța reprezintă o cameră,căreia i se atribuie un număr natural de maxim `9` cifre. Acesta a ascuns într-o cameră un cufăr cu o comoară. Fiind neatent, a uitat unde a pus-o. ## Cerință **Cerinta 1.** Ajutați-l pe Gigel să găsească camera în care se află comoara, știind că numărul asociat acesteia este maximul pătrat perfect din matrice. Afișati numărul de ordine al camerei. Dacă există mai multe elemente maxime pătrate perfecte, să se afișeze numărul de ordine al primei camere găsite (Parcurgând harta de la stânga la dreapta, sus – jos începând din colțul stânga- sus). **Cerinta 2.** Fiecare cameră are un factor de securitate dat de prima cifră a numărului. Pentru a nu mai uita unde ascunde comoara, Gigel alege să numeroteze camerele de la `1` la `n<sup>2</sup>` începand din colțul din stânga-sus și continuând pe paralele la diagonala secundară ca în desenul de mai jos. Noua poziție a comorii se va afla pe cea de-a `k`-a paralela la diagonală (`1` se afla pe diagonala `0`, `2` și `3` pe diagonala `1`, …, etc.), în camera pentru care suma factorilor de securitate a camerei respective și a celor `8` camere adiacente este maximă. Afișați numărul de ordine al camerei. Dacă există mai multe elemente cu suma factorilor de securitate maximă, să se afișeze numărul de ordine al primei camere găsite.  ## Date de intrare Fișierul de intrare `comoara.in` conține pe prima linie numerele `c n`, unde `c` reprezintă numărul cerinței (`1` sau `2`), iar `n` dimensiunea hărții. Următoarele `n` linii conțin câte `n` valori, reprezentând harta casei lui Gigel. Pentru cerinta 2, după harta casei lui Gigel, se va citi și valoarea `k`. ## Date de ieșire Fișierul de ieșire `comoara.out` va conține `2` valori `i j`, separate printr-un singur spațiu, ce reprezintă: * pentru cerința `1`: linia și coloana unde se găsește comoara (matricea fiind indexată de la `0`) * pentru cerința `2`: linia și coloana unde va fi mutată comoara (matricea fiind indexată de la `0`) ## Restricții și precizări * `3 ≤ n ≤ 1000` * Elementele matricei vor fi mai mici decât `1.000.000.000` * Se garantează ca pentru cerința 1 există cel puțin un număr pătrat perfect * 30% din teste vor reprezenta cerința 1 * 70% din teste vor reprezenta cerința 2