Editing 3043 - cub3

Ionel are de rezolvat o nouă problemă. El trebuie să construiască un șir de <code>N</code> numere naturale. Numerele din șir pot avea ca divizori primi doar numere prime de o cifră. După construirea șirului, Ionel a constatat că există subsecvențe în șir pentru care produsul elementelor este cubul unui număr natural.

= Cerința =
Ionel vrea să determine numărul subsecvențelor din șirul construit care au produsul elementelor o valoare ce este cubul unui număr natural.

= Date de intrare =
Fișierul de intrare <code>input.txt</code> va conține pe prima linie numărul natural <code>N</code>, iar pe linia următoare se vor afla <code>N</code> numere naturale separate prin câte un spațiu, elementele șirului construit de Ionel.

= Date de ieșire =
Fișierul de ieșire <code>output.txt</code> va conține pe prima linie un număr natural reprezentând numărul subsecvenţelor din șirul construit care au produsul elementelor egal cu o valoare ce este cubul unui număr natural.

= Restricții și precizări =

* <code>N</code> și elemente șirului sunt numere naturale din intervalul <code>[2, 1.000.000]</code>.

== Exemplul 1 ==
input.txt:

8

15 3 5 15 7 63 21 125

output.txt:

6

Explicație:

Sunt <code>6</code> subsecvențe în șir cu produsul elementelor egal cu o valoare care este cubul unui număr natural:

<code>15 3 5 15</code>

<code>7 63 21</code>

<code>125</code>

<code>15 3 5 15 7 63 21</code>

<code>7 63 21 125</code>

<code>15 3 5 15 7 63 21 125</code>

== Exemplul 2 ==
input.txt:

99999999999

15 3 5 15 7 63 21 125

Output:

Input-ul nu convine conditiilor

== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
import math

def verificare(n):
    if not(2<=n<=1000000):
        print("Input-ul nu convine conditiilor")
        exit()

def convert():
    return crtState[3] * 3 * 3 * 3 + crtState[2] * 3 * 3 + crtState[1] * 3 + crtState[0]

fin = open("input.txt", "r")
fout = open("output.txt", "w")

n = int(fin.readline())
verificare(n)
i, j, nr, x, mul, sol = 0, 0, 0, 0, 0, 0
crtState = [0] * 4
states = [0] * 100
divs = [2, 3, 5, 7]

l=list(map(int, fin.readline().split()))

for _ in range(1, n + 1):
    x = l[i-1]

    for j in range(4):
        nr = 0
        while x % divs[j] == 0:
            nr += 1
            x //= divs[j]
            crtState[j] += 1

        crtState[j] %= 3

    states[convert()] += 1

states[0] += 1

for i in range(81):
    sol += states[i] * (states[i] - 1) // 2

fout.write(str(int(math.sqrt(sol))))

fin.close()
fout.close()

</syntaxhighlight>