1558 - NPE

Cerința

Se desenează un șir de pătrate distincte, de latură: 1,2,3,4,….

Pătratele sunt numerotate cu numerele egale cu laturile lor. Fiecare pătrat este împărțit în pătrate elementare, adică pătrate de latură 1. De exemplu, un pătrat de latură k se împarte, trasând k-1 linii orizontale și k-1 linii verticale echidistante, în k*k pătrate elementare dispuse căte k pe fiecare rând, respectiv coloană. Începând de la primul pătrat desenat, parcurgând în spirală fiecare pătrat din șir, se numerotează toate pătratele elementare, ca în imaginea de mai jos:

În fiecare pătrat din șir, rândurile sunt numerotate de sus în jos cu numerele distincte 1,2,3…. Analog, coloanele sunt numerotate de la stânga la dreapta cu numerele distincte 1,2,3….

Dându-se un număr natural N să se determine:

1) Numărul P al pătratului din șir care conține pătratul elementar numerotat cu N;

2) Rândul R și coloana C în care este situat pătratul elementar cu numărul N în pătratul cu numărul P.

Date de intrare

Fișierul de intrare npein.txt conține pe prima linie numărul N.

Date de ieșire

Fișierul de ieșire npeout.txt va conține pe prima linie cele trei numere naturale P R C determinate, separate prin câte un spațiu, cu semnificația din enunț.

Restricții și precizări

• 1 ≤ N ≤ 2.000.000.000
• Pentru determinarea corectă a numărului P se acordă 40% din punctaj; pentru determinarea corectă a numărului R se acordă 30% din punctaj; pentru determinarea corectă a numărului C se acordă 30% din punctaj

Exemplu:

npein.txt

52

npeout.txt

5 4 3

Explicație

Pătratul cu numărul P=5 conține pe rândul R=4 și coloana C=3 pătratul elementar cu numărul N=52.

Rezolvare

def validate_input(n):
    if not (1 <= n <= 2000000000):
        raise ValueError("Valoarea de intrare N trebuie să fie între 1 și 2.000.000.000.")
def main():
    with open("npein.txt", "r") as f, open("npeout.txt", "w") as g:
        n = int(f.readline().strip())

        if n == 1:
            g.write("1 1 1\n")
            return
        # Calculul valorii lui p și nr
        p = 1
        nr = 0
        while n > nr + p * p:
            nr += p * p
            p += 1
        # Actualizarea valorii lui n
        n = n - nr
        # Verificarea cazului n == 1 după actualizare
        if n == 1:
            g.write(f"{p} 1 1\n")
            return
        # Calculul valorilor lui k și r
        k = p
        r = 1
        while n > 4 * k - 4 and k > 0:
            n = n - (4 * k - 4)
            k = k - 2
            r += 1
        # Verificarea cazului n == 1 după calculul lui k și r
        if n == 1:
            l = c = r
        else:
            # Calculul poziției (l, c) în funcție de valoarea lui n
            k = p - 2 * (r - 1)
            if n <= k:
                l = r
                c = r - 1 + n
            else:
                n = n - k
                if n <= k - 1:
                    l = r + n
                    c = p + 1 - r
                else:
                    n = n - (k - 1)
                    if n <= k - 1:
                        l = p + 1 - r
                        c = p - r + 1 - n
                    else:
                        n = n - (k - 1)
                        l = p + 1 - r - n
                        c = r

        g.write(f"{p} {l} {c}\n")

if __name__ == "__main__":
    main()