0965 - Joc 3

Rareş şi Bogdan vor să facă mişcare în aer liber aşa că s-au gândit la un nou joc.

Pe terenul de fotbal, ei au desenat două cercuri concentrice (cu acelaşi centru) şi au împărţit pista cuprinsă între cele două cercuri în n sectoare congruente, ca în desenul de mai jos unde n=16.

Ei au etichetat cele n sectoare cu numerele distincte de la 1 la n, în ordinea acelor de ceasornic. Au stabilit ca jocul să se desfăşoare astfel:

• Se vor aşeza amândoi în sectorul numerotat cu 1, spate în spate.
• Prin sărituri executate simultan în anumite sectoare, copii se vor deplasa pe pistă în sensuri contrare. Bogdan se va deplasa în sensul acelor de ceasornic iar Rareş în sensul contrar. Copii vor executa un număr egal de sărituri.
• O săritură a lui Bogdan are efect deplasarea acestuia din sectorul curent, în sensul acelor de ceasornic, direct în cel de-al x-lea sector de pe pistă. De exemplu, dacă n=16 şi x=2 atunci, pornind din sectorul 1, Bogdan se va deplasa sărind succesiv, în această ordine, în sectoarele etichetate cu: 3,5,7,9,...
• O săritură a lui Rareş are efect deplasarea acestuia din sectorul curent, în sens contrar acelor de ceasornic, direct în cel de-al y-lea sector de pe pistă. De exemplu, dacă n=16 şi y=3 atunci, pornind din sectorul 1, Rareş se va deplasa sărind succesiv, în această ordine, în sectoarele: 14,11,8,5,...
• Jocul se termină când cei doi copii ajung în urma săriturilor într-un acelaşi sector de pe pistă sau dacă unul din cei doi copii ajunge pentru a doua oară într-un acelaşi sector.

Cerința

Scrieţi un program care să citească cele trei numere naturale nenule n, x şi y, şi apoi să determine:

a) numărul t al sectoarelor de pe pistă prin care nu trece niciunul din cei doi copii în urma săriturilor executate până la terminarea jocului;

b) numărul s de sărituri executate de fiecare copil până la terminarea jocului;

c) etichetele b şi r ale sectoarelor în care ajung cei doi copii la terminarea jocului (Bogdan ajunge la finalul jocului în sectorul cu eticheta b, iar Rareş în cel cu eticheta r).

Date de intrare

Fișierul de intrare input.txt conține conţine pe prima linie trei numere naturale n, x şi y, separate prin câte un spaţiu, cu semnificaţia din enunţ.

Date de ieșire

Fișierul de ieșire output.txt va conține pe prima linie cele patru numere naturale determinate de program: t, s, b şi r, separate prin câte un spaţiu, în această ordine, cu semnificaţia din enunţ.

Restricții și precizări

• 20 ≤ n ≤ 30000

Exemplul 1

input.txt:

16 2 3

output.txt:

4 8 1 9

Explicație:

Cei doi copii, executând simultan sărituri, trec până la terminarea jocului prin sectoarele:

Jocul se termină după s=8 sărituri deoarece Bodgan ajunge din nou în sectorul cu eticheta cu b=1. La finalul jocului Rareş se află în sectorul cu eticheta cu r=9. Cei doi copii nu au trecut prin t=4 sectoare ale căror etichete sunt: 4,6,10,16.

Exemplul 2

input.txt:

16 6 2

output.txt:

12 2 13 13

Explicație:

Cei doi copii, executând simultan sărituri, trec până la terminarea jocului prin sectoarele:

Jocul se termină după s=2 sărituri deoarece Bodgan şi Rareş ajung amândoi în sectorul cu eticheta cu b=r=13. Cei doi copii nu au trecut prin t=12 sectoare ale căror etichete sunt: 2,3,4,5,6,8,9,10,11,12,14,16.

Exemplul 3

input.txt:

99999999999 6 2

Output:

Constrangeri neindeplinite

Rezolvare:

def ver(n):
    if not(20<=n<=30000):
        print("Constrangeri neindeplinite")
        exit()

def main():
    with open("input.txt", "r") as f:
        with open("output.txt", "w") as g:
            v = [0] * 40001
            n, x, y = map(int, f.readline().split())
            ver(n)
            t = 0
            s = 0
            b = 1
            r = 1
            v[1] = 11
            t = n - 1

            while True:
                s += 1
                b += x
                r -= y

                if r < 1:
                    r += n

                if b > n:
                    b -= n

                if v[b] == 0:
                    t -= 1

                if v[r] == 0 and b != r:
                    t -= 1

                v[b] += 1
                v[r] += 10

                if b == r or v[r] // 10 == 2 or v[b] % 10 == 2:
                    break

            g.write(f"{t} {s} {b} {r}\n")

if __name__ == "__main__":
    main()