1932 - PC

Cerința

Gigel vrea un calculator nou care are prețul x. Tatăl acestuia, fiind profesor de matematica, i-a spus ca îi va cumpăra calculatorul dacă prețul x al acestuia este norocos. Un număr x este norocos dacă pătratul acestuia se poate scrie ca sumă de x numere consecutive. De exemplu, x = 7 este număr norocos deoarece, 7 * 7 = 4 + 5 + 6 + 7 + 8 + 9 + 10. Gigel a obţinut T oferte de preț și dorește să știe pentru fiecare dintre acestea dacă prețul este corespunzătar restricției pe care i-a impus-o tatăl său.

Date de intrare

Fișierul de intrare pc.in conține pe prima linie un singur număr natural T, reprezentând numărul de oferte. Pe a doua linie se află T numere naturale x1 x2 x3 … xT separate prin câte un spaţiu, cu semnificația din enunț.

Date de ieșire

Fișierul de ieșire pc.out va conține pe prima linie, separate prin câte un spațiu, cele T răspunsuri, în ordine: 1 dacă oferta este corespunzătoare restricției impuse și 0 în caz contrar.

Restricții și precizări

x < 2.000.000.000 T < 10

Exemplu:

pc.in 3 3 4 7

pc.out 1 0 1

Rezolvare

<syntaxhighlight lang="python" line> def is_lucky(x):

   for n in range(int(x**0.5)):
       if (2*x - n*n + n) % (2*n+2) == 0:
           return True
   return False

def read_input_file(input_file):

   with open(input_file, 'r') as fin:
       T = int(fin.readline())
       x_values = list(map(int, fin.readline().split()))
       
   result = []
   for x in x_values:
       if is_lucky(x):
           result.append(1)
       else:
           result.append(0)
           
   return result

def main(input_file, output_file):

   result = read_input_file(input_file)
   with open(output_file, 'w') as fout:
       fout.write(' '.join(map(str, result)))

</syntaxhighlight>

Explicatie

Pentru a verifica dacă un număr este norocos, trebuie să verificăm toate valorile de n posibile, unde n <= sqrt(x), utilizând formula sumei unei secvențe de numere consecutive. Dacă găsim o astfel de valoare de n, înseamnă că x este norocos. În funcția de intrare citim valorile din fișier și apelăm funcția de validare pentru fiecare valoare, stocând rezultatele într-o listă. În final, scriem rezultatele în fișierul de ieșire.