1559 - Minge

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

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 (X,Y) cu semnificația că copilul cu numărul X aruncă mingea copilului cu numărul Y care nu a mai atins mingea până în acel moment.

Cerințe

Cunoscându-se numerele N, K și cele K perechi de numere corespunzătoare celor K 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 input.txt conține

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

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

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

Date de ieșire

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

– Dacă valoarea lui p este 2, atunci se va rezolva numai cerința 2. În acest caz, fişierul ouput.txt 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

• 6 ≤ N ≤ 10000
• 1 ≤ K ≤ N-1

Exemplul 1

input.txt:

1

7 4

4 3

2 6

3 1

6 4

output.txt:

2

Explicație:

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

Exemplul 2

input.txt:

2

7 4

4 3

2 6

3 1

6 4

output.txt:

2 6 4 3 1

Explicație:

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

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

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>