Fișierul intrare/ieșire patru.in, patru.out Sursă ONI 2012 baraj gimnaziu
Autor Marius Nicoli Adăugată de avatar francu Cristian Frâncu francu
Timp de execuție pe test 0.2 sec Limită de memorie 4096 KB
Scorul tău N/A Dificultate stea de rating de tip fullstea de rating de tip fullstea de rating de tip emptystea de rating de tip emptystea de rating de tip empty
open book Poți vedea testele pentru această problemă accesând atașamentele .

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.in patru.out Explicaț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 să te autentifici pentru a trimite soluții. Click aici

Indicii de rezolvare

Arată 4 categorii