Fişierul intrare/ieşire:patru.in, patru.outSursăONI 2012 baraj gimnaziu
AutorMarius NicoliAdăugată defrancuCristian Francu francu
Timp execuţie pe test0.2 secLimită de memorie4096 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise

Patru (baraj gimnaziu)

Numim putere4 un număr care poate fi scris sub forma X4 + Y4 (cu X şi Y numere naturale nenule).

Fie un şir de N numere naturale T1, T2, ..., TN. Suma unei secvenţe de K termeni ai şirului T4i + T4i+1 + ... + T4i+K-1, se numeşte sumă4 dacă are ultima cifră 4.
Cerinţă

Scrieţi un program care citeşte numerele naturale nenule N şi K şi un şir de N numere naturale nenule şi determină:

  • numărul de termeni din şirul dat care sunt putere4;
  • numărul de secvenţe de lungime K ale şirului dat ce reprezintă o sumă4.

Date de intrare

Prima linie a fişierului patru.in conţine două numere naturale N şi K, separate printr-un spaţiu. Pe linia a doua se află N numere naturale, separate prin câte un spaţiu, ce reprezintă termenii şirului dat.

Date de ieşire

Fişierul de ieşire patru.out conţine pe prima linie numărul de termeni ai şirului care sunt putere4. Pe linia a doua se găseşte numărul de secvenţe de tipul cerut.

Restricţii

  • 2 ≤ K ≤ N ≤ 20 000
  • termenii şirului sunt numere naturale mai mici sau egale cu 1 miliard;
  • prin secvenţă înţelegem o succesiune de elemente din şir aflate pe poziţii consecutive.

Exemplu

patru.inpatru.outExplicaţie
7 5
1 2 17 15 23 19 17
3
2
Sunt trei elemente putere4 adică 2, 17 şi 17. Sunt 2 secvenţe sumă4
de lungime 5 cu proprietatea din enunţ (cea care începe pe poziţia 1
şi cea care începe pe poziţia 2).
Trebuie sa te autentifici pentru a trimite solutii. Click aici