Fişierul intrare/ieşire:cavaleri.in, cavaleri.outSursăOlimpiada locala 2012, Clasa a 5-a
AutorGilda GebailaAdăugată deioanabIoana Bica ioanab
Timp execuţie pe test0.1 secLimită de memorie2048 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise

Cavaleri

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, 92 + 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.incavaleri.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 sa te autentifici pentru a trimite solutii. Click aici