2013 - Intersectie Segmente

Numerele naturale nenule se scriu pe linii într-un triunghi de forma de mai jos:

1
2 3
4 5 6 
7 8 9 10
...

Cerinţa

Se dau două numere natural n și m. Determinați:

1. Suma numerelor de pe linia cu numărul n din triunghiul construit ca mai sus.

2. Linia pe care se află numărul m, precum și pe ce poziție se află el pe această linie.

Dându-se Q operații, să se raspundă în ordine la cele de tip 2 și 3.

Date de intrare

Fișierul de intrare numere18in.txt conține pe prima linie un număr natural C reprezentând cerința din problemă care trebuie rezolvată (1 sau 2).

Dacă C este egal cu 1, a doua linie din fișier conține un număr natural n, reprezentând numărul liniei pe care trebuie să se calculeze suma.

Dacă C este egal cu 2, a doua linie din fișier conține numărul natural m, reprezentând numărul care trebuie căutat în triunghi.

Date de ieșire

Fișierul de ieșire numere18out.txt va conține o singură linie. Dacă C=1, va fi scrisă suma cerută la punctul 1. Dacă C=2, vor fi scrise nouă numere: linia pe care a află numărul m, respectiv poziția acestuia pe această linie, separate printr-un spațiu.

Restricţii şi precizări

• 1 ⩽ n ⩽ 1000
• 1 ⩽ m ⩽ 1.000.000.000
• Pentru rezolvarea corectă a cerinţei 1 se acordă 45 de puncte; pentru rezolvarea corectă a cerinței 2 se acordă 55 de puncte.

Exemplul 1

numere18in.txt

1
4

numere18out.txt

34

Explicatie

În acest caz se rezolvă doar cerința 1. Numerele de pe linia a 4-a sunt: 7, 8, 9, 10, iar suma lor este 34

Exemplul 2

numere18in.txt

2
1500000000

numere18out.txt

Datele de intrare nu corespund restrictiilor impuse

Rezolvare

<syntaxhighlight lang="python" line> def suma_linie(n):

   if n < 1 or n > 1000:
       return "Datele de intrare nu corespund restrictiilor impuse"
   start = n * (n - 1) // 2 + 1
   end = start + n
   return sum(range(start, end))

def linie_numar(m):

   if m < 1 or m > 1000000000:
       return "Datele de intrare nu corespund restrictiilor impuse"
   linie = int(((8 * m + 1) ** 0.5 - 1) / 2)
   start = linie * (linie - 1) // 2 + 1
   pozitie = m - start + 1
   return linie, pozitie

with open('numere18in.txt', 'r') as fin:

   C = int(fin.readline().strip())
   num = int(fin.readline().strip())
   if C == 1:
       result = suma_linie(num)
   else:
       result = linie_numar(num)

with open('numere18out.txt', 'w') as fout:

   if isinstance(result, tuple):
       fout.write(' '.join(map(str, result)))
   else:
       fout.write(str(result))

</syntaxhighlight>