Fișierul intrare/ieșire 235.in, 235.out Sursă OJI 2009 clasa a 8-a
Autor Marius Nicoli Adăugată de avatar Mstar_Angel Coman Mara Mstar_Angel
Timp de execuție pe test 0.6 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 .

235 (clasa a 8-a)

Definim o putere a lui 3 un număr de forma 3k, (k număr natural strict pozitiv), o putere a lui 5 un număr de forma 5k (k număr natural strict pozitiv), iar o putere a lui 2 un număr de forma 2k (k număr natural strict pozitiv).
Se dă un șir de n numere naturale. Plecând de la acest șir, formăm un nou șir prin eliminarea tuturor numerele care nu sunt puteri ale lui 3 și nici puteri ale lui 5. Ordinea relativă între numerele care nu sunt eliminate se păstrează.

Cerință

Să se determine câte numere conține șirul nou format.
Să se determine de asemenea numărul de secvențe având lungimea egală cu o putere a lui 2 existente în șirul nou format în care numărul de puteri ale lui 3 este egal cu numărul de puteri ale lui 5. O secvență este formată din elemente aflate pe poziții consecutive în acest șir nou format, iar lungimea unei secvențe este egală cu numărul de elemente pe care aceasta îl conține.

Date de intrare

Pe prima linie in fișierul 235.in se afla un număr natural n. Pe fiecare dintre următoarele n linii câte un număr natural mai mare decât 1 reprezentând numerele șirului inițial.

Date de ieșire

Pe prima linie a fișierului 235.out se va afla o valoare naturală m care va reprezenta numărul de elemente rămase în șir după eliminare. Pe a doua linie se va afla o valoare naturală S reprezentând numărul de secvențe din șirul nou format care au proprietățile cerute.

Restricții

  • 2 ≤ n ≤ 500000
  • Numerele din șirul inițial sunt numere naturale din intervalul [2,2000000000].
  • Se garantează că m ≤ 40000 pentru fiecare set de date de intrare.

Exemplu

235.in 235.out Explicatii
8
625
125
5
9
15
81
100
125
6
4
Șirul rămas după eliminarea numerelor care nu sunt puteri ale lui 5 sau ale lui 3 are 6 elemente:
625, 125, 5, 9, 81, 125.
În acest șir sunt:
- două secvențe formate din două valori care conțin un număr egal de puteri ale lui 3 și ale lui 5: 5,9 și 81,125;
- două secvențe de patru numere care conțin un număr egal de puteri ale lui 3 și ale lui 5: 125, 5, 9, 81 și 5, 9, 81, 125

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

Indicii de rezolvare

Arată 2 categorii