Editing 1559 - Minge

<code>N</code> copii, numerotați de la <code>1</code> la <code>N</code>, se aşează în cerc, unul lângă altul, în ordinea crescătoare a numerelor lor, copilul cu numărul <code>N</code> ajungând să fie situat lângă copilul cu numărul <code>1</code>.

Un copil din cerc are o minge. El o aruncă unui alt copil din cerc. Acesta o aruncă și el unui alt copil din cerc care nu a atins vreodată mingea, … șamd. Fiecare aruncare este notată printr-o pereche de numere naturale distincte <code>(X,Y)</code> cu semnificația că copilul cu numărul <code>X</code> aruncă mingea copilului cu numărul <code>Y</code> care nu a mai atins mingea până în acel moment.

= Cerințe =
Cunoscându-se numerele <code>N</code>, <code>K</code> și cele <code>K</code> perechi de numere corespunzătoare celor <code>K</code> aruncări să se determine:

1) Numărul copiilor care nu ating niciodată mingea.

2) Traseul parcurs de minge plecând de la copilul care are mingea la începutul jocului, până la copilul care nu mai aruncă mingea.

= Date de intrare =
Fișierul de intrare <code>input.txt</code> conține

– pe prima linie, un număr natural <code>p</code>; pentru toate testele de intrare, <code>p</code> poate avea doar valoarea <code>1</code> sau valoarea <code>2</code>;

– pe a doua linie, cele două numere naturale <code>N K</code>, separate printr-un spațiu.

– pe fiecare dintre următoarele <code>K</code> linii (câte una pentru fiecare aruncare), câte o pereche de numere naturale <code>X Y</code>, separate printr-un spațiu, cu semnificația: copilul cu numărul <code>X</code> aruncă mingea copilului cu numărul <code>Y</code>.

= Date de ieșire =
– Dacă valoarea lui <code>p</code> este <code>1</code>, atunci se va rezolva numai cerința <code>1</code>. În acest caz, fişierul <code>output.txt</code> va conţine pe prima linie un număr natural reprezentând numărul copiilor care nu ating niciodată mingea

– Dacă valoarea lui <code>p</code> este <code>2</code>, atunci se va rezolva numai cerința <code>2</code>. În acest caz, fişierul <code>ouput.txt</code> va conţine pe prima linie, traseul parcurs de minge plecând de la copilul care are mingea la începutul jocului, până la copilul care nu mai aruncă mingea; traseul este descris prin șirul numerelor copiilor care ating mingea, separate prin câte un spațiu, în ordinea în care este aruncată mingea.

= Restricții și precizări =

* <code>6 ≤ N ≤ 10000</code>
* <code>1 ≤ K ≤ N-1</code>

== Exemplul 1 ==
input.txt:

1

7 4

4 3

2 6

3 1

6 4

output.txt:

2

Explicație:

<code>p=1</code>. Se rezolvă doar cerința <code>1</code>. Sunt <code>N=7</code> copii. Se fac <code>K=4</code> aruncări. Sunt <code>2</code> copii care nu ating mingea, cei cu numerele <code>5</code> și <code>7</code>.

== Exemplul 2 ==
input.txt:

2

7 4

4 3

2 6

3 1

6 4

output.txt:

2 6 4 3 1

Explicație:

<code>p=2</code>. Se rezolvă doar cerința <code>2</code>. Sunt <code>N=7</code> copii. Se fac <code>K=4</code> aruncări.

Traseul parcurs de minge pornește de la copilul cu numărul <code>2</code> și se termină la copilul cu numărul <code>1</code> este: <code>2 6 4 3 1</code>, deoarece se fac aruncările: <code>(2,6),(6,4),(4,3),(3,1)</code>

== Exemplul 3 ==
input.txt:

2

99999999 4

4 3

2 6

3 1

6 4

Ouput:

Constrangeri neindeplinite

== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
def ver(n,m):
    if not(6<=n<=10000):
        print("Constrangeri neindeplinite")
        exit()
    if not(1<=m<=n-1):
        print("Constrangeri neindeplinite")
        exit()

with open("input.txt", 'r') as fin, open("output.txt", 'w') as fout:
    freq = [0] * 10001
    col1 = [0] * 10001
    col2 = [0] * 10001

    t=int(fin.readline())
    n, m = map(int, fin.readline().split())
    
    ver(n,m)

    if t == 1:
        for _ in range(m):
            x, y = map(int, fin.readline().split())
            freq[x] += 1
            freq[y] += 1

        nr = sum(1 for i in range(1, n + 1) if freq[i] == 0)
        fout.write(str(nr))
    elif t == 2:
        for _ in range(m):
            x, y = map(int, fin.readline().split())
            freq[x] = y
            col1[x] += 1
            col2[y] += 1

        start, finish = 0, 0
        for i in range(1, 10001):
            if col1[i] > 0 and col2[i] == 0:
                start = i
            if col2[i] > 0 and col1[i] == 0:
                finish = i

        z = start
        fout.write(str(start) + ' ')
        while freq[z] != finish:
            fout.write(str(freq[z]) + ' ')
            z = freq[z]

        fout.write(str(finish))

</syntaxhighlight>