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

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))