Fișierul intrare/ieșire cavaleri.in, cavaleri.out Sursă Olimpiada locala 2012, Clasa a 5-a
Autor Gilda Gebăilă Adăugată de avatar ioanab Ioana Bica ioanab
Timp de execuție pe test 0.1 sec Limită de memorie 2048 KB
Scorul tău N/A Dificultate N/A
open book Poți vedea testele pentru această problemă accesând atașamentele .

Cavaleri (clasa a 5-a)

Notă: Testele au fost modificate pentru a corespunde cu enunțul.

Regina Numerelor provoacă pe toți cavalerii din regiune la o întrecere. Primul cavaler care va ajunge la castelul acesteia va fi acceptat în ilustrul cerc al „Cavalerilor Numerelor Fericite”. Dar pentru a străbate drumul, cavalerii au nevoie de puțin „noroc” și trebuie să știe puțină matematică, pentru că atotcunoscătorul vrăjitor Matematicus, va verifica calculele. Dorești să devii un Cavaler al Numerelor Fericite? Atunci răspunde provocării și înscrie-te!

La înscriere, cavalerii primesc un număr de ordine. Cavalerii au de parcurs un drum de x km. La pornire, fiecare cavaler primește de la unul dintre gardienii reginei un număr p, care va reprezenta numărul de kilometri pe care trebuie să-i străbată în prima zi. Dacă la sfârșitul unei zile un cavaler se găsește la un kilometru k care este număr fericit, în ziua următoare el va avea de parcurs un număr de kilometri egal cu numărul k, altfel el va putea să străbată în ziua următoare doar un kilometru. Regula rămâne aceeași în fiecare zi, pentru fiecare dintre cavaleri.

Un număr este fericit dacă se obține 1 la sfârșitul următorului șir de operații: se calculează suma pătratelor cifrelor numărului, apoi din nou suma pătratelor cifrelor sumei și așa mai departe până când se obține un număr format dintr-o cifră. Exemplu: numărul 13 este număr fericit pentru că: 12 + 32 = 10 apoi 12 + 02 = 1; 7 este de asemenea fericit pentru că 72 = 49, apoi 42 + 92 = 97, 9^2 ^ + 72 = 130, 12 + 32 + 02 = 10, 12 + 02 = 1; dar numărul 16 nu este fericit pentru că în urma calculului sumelor pătratelor cifrelor se obține cifra 4 (nu 1): 12 + 62 = 37, 32 + 72 = 58, 52 + 82 = 89, 82 + 92 = 145, 12 + 42 + 52 = 42, 42 + 22 = 20, 22 + 02 = 4.

Să se determine cavalerul ce va fi acceptat în cercul „Cavalerilor Numerelor Fericite” și numărul de zile după care ajunge la castel.

Date de intrare

Pe prima linie a fișierului cavaleri.in se găsesc două numere naturale: x ce reprezintă numărul de kilometri ce trebuie parcurși de cavaleri și N ce reprezintă numărul de cavaleri.
Pe a doua linie se găsesc N numere naturale, ce reprezintă numărul de kilometri pe care trebuie să-i parcurgă câte un cavaler în prima zi (primul număr corespunde distanței ce trebuie parcursă de primul cavaler, al doilea număr distanței ce trebuie parcursă de al doilea cavaler etc.).

Date de ieșire

Fișierul de ieșire cavaleri.out va conține numărul de ordine al cavalerului ce a ajuns la regină într-un număr minim de zile și numărul de zile necesare. Dacă sunt mai mulți cavaleri care vor parcurge o distanță mai mare sau egală cu x în același număr minim de zile se va scrie cavalerul cu cel mai mic număr de ordine.

Restricții

  • 0 < N ≤ 1000
  • 0 < x ≤ 10 000
  • 0 < p ≤ 200

Exemplu

cavaleri.in cavaleri.out
13 4
5 3 10 6
3 2

Explicație

Cavalerul 1 în prima zi ajunge la km 5; fiindcă acesta nu este nr fericit, a doua zi parcurge 1 km, deci ajunge la km 6. Fiindcă acest număr nu este nr fericit, parcurge în a treia zi incă 1 km ajungând la km 7. Fiindcă acesta este fericit în a patra zi mai poate parcurge 7 km deci ajunge la regină.
Cavalerul 2 are nevoie de 6 zile (3, 4, 5, 6, 7, 14)
Cavalerul 3 parcurge distanța doar în 2 zile (10, 20)
Cavalerul 4 ajunge după 3 zile (6, 7, 14)

Trebuie să te autentifici pentru a trimite soluții. Click aici