Simulare OJI VII | campionat

This was the problem page during the contest. Access the current page here.
Time limit: 0.2s Memory limit: 64MB Input: campionat.in Output: campionat.out

Ne aflăm la un anumit moment al desfășurării campionatului național de fotbal. O parte dintre meciuri s-au jucat, altele urmează să fie disputate. Se cunoaște numărul de puncte acumulate deja de fiecare echipă înaintea desfășurării meciurilor restante. Se cunoaște, de asemenea, că un meci se poate termina egal, caz în care fiecare dintre echipe primește câte un punct, sau cu victoria uneia dintre echipe, iar în acest caz acea echipă primește trei puncte, iar cealaltă zero puncte.

Cerință

Avem de răspuns la întrebări de două tipuri:

  1. Care echipe ar fi pe locul I dacă toate meciurile restante s-ar termina la egalitate? O echipă este pe locul I dacă are număr maxim de puncte.
  2. Care echipe depind strict de propriile rezultate pentru a deveni campioane? O echipă devine campioană (câștigă campionatul) dacă termină cu număr de puncte strict mai mare decât oricare dintre celelalte echipe. Spunem că o echipă depinde strict de propriile rezultate pentru a deveni campioană dacă ea devine campioană câștigând toate meciurile pe care trebuie să le mai joace, indiferent de rezultatele celorlalte meciuri.

Date de intrare

Fișierul de intrare campionat.in conține pe prima linie un număr TT, reprezentând tipul de întrebare (11 sau 22). Pe linia a doua se află un număr NN reprezentând numărul de echipe din campionat (considerăm că echipele sunt etichetate cu numere distincte de la 11 la NN). Pe linia a treia se află NN numere naturale separate prin câte un spațiu, al ii-lea număr reprezentând punctajul celei de-a ii-a echipe. Pe linia a patra se află un număr DD, reprezentând numărul de meciuri restante. Pe fiecare dintre următoarele DD linii se află câte două numere distincte i,ji, j, cuprinse între 11 și NN, cu semnificația că echipele ii și jj au de disputat un meci restant.

Date de ieșire

Fișierul de ieșire campionat.out va conține o singură linie.

Dacă T=1T = 1, linia va conține etichetele echipelor care termină pe locul I, în cazul în care toate meciurile restante se termină la egalitate.
Dacă T=2T = 2, linia va conține etichetele echipelor care depind strict de propriile rezultate pentru a deveni campioane. Dacă nicio echipă nu poate deveni campioană depinzând doar de rezultatele sale, în fișierul de ieșire se va scrie doar numărul 00.
Atât pentru T=1T = 1, cât și pentru T=2T = 2 etichetele echipelor vor fi scrise în ordine crescătoare, separate prin câte un spațiu.

Restricții și precizări

  • 2N1 0002 \leq N \leq 1 \ 000;
  • 1D500 0001 \leq D \leq 500 \ 000;
  • Punctajele inițiale ale echipelor sunt numere naturale cel mult egale cu 1 0001 \ 000.
  • Regulile de desfășurare a campionatului sunt mai ciudate, nu trebuie să vă puneți problema dacă este posibil ca echipele să aibă șirul dat al punctajelor în urma meciurilor disputate deja (considerăm că până la momentul de față federația a acordat diverse bonusuri și depunctări).
  • Dacă între meciurile rămase de jucat este vreunul care apare de mai multe ori (fie sub forma (i,j)(i, j) fie sub forma (j,i)(j, i)), el se va disputa o singură dată.
  • Programarea meciurilor s-a făcut în mod indisciplinat, deci este posibil ca unele echipe să mai aibă de jucat mai multe meciuri decât altele, iar unele chiar să nu mai aibă de jucat niciun meci.
  • Pentru teste valorând 2222 de puncte, T=1T = 1.
  • Pentru alte teste valorând 99 puncte, T=2T = 2 și fiecare echipă are de disputat exact 22 meciuri cu alte echipe.
  • Pentru alte teste valorând 88 puncte, T=2T = 2 și fiecare echipă are de disputat câte un meci cu fiecare altă echipă.
  • Pentru alte teste valorând 1010 puncte, T=2T = 2 și există o singura echipă care joacă câte un meci cu fiecare altă echipă, celelalte echipe neavând alte meciuri restante de jucat.

Exemplul 1

campionat.in

1
4
2 3 2 1
3
1 3
1 2
3 1

campionat.out

1 2

Explicație

Echipa 22 are de disputat un singur meci cu echipa 11, iar al doilea meci se va disputa între echipele 11 și 33 (chiar dacă în listă apare de două ori perechea 1 31 \ 3, este vorba despre un singur meci).
Cele două jocuri se vor termina la egalitate, și astfel punctajele echipelor la final vor fi: 4 4 3 14 \ 4 \ 3 \ 1. Așadar echipele 11 și 22 ies pe primul loc.

Exemplul 2

campionat.in

2
4
1 3 2 1
3
1 3
1 2
3 1

campionat.out

1 2

Explicație

Echipa 11 devine campioană dacă învinge în ambele meciuri, nicio altă echipă neputând să o egaleze la puncte sau să o depășească.

De asemenea, echipa 22 devine campioană dacă învinge echipa 11 în meciul restant, indiferent de rezultatul celuilalt meci. Echipa 33, chiar dacă învinge în meciul cu echipa 11, nu depinde doar de rezultatul său întrucât echipa 22 ar depăși-o la puncte dacă și ea ar câștiga meciul pe care îl mai are de disputat.

Log in or sign up to be able to send submissions!