Fişierul intrare/ieşire:aquapark.in, aquapark.outSursăOJI 2018, Clasele 11-12
AutorZoltan SzaboAdăugată debciobanuBogdan Ciobanu bciobanu
Timp execuţie pe test1 secLimită de memorie131072 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Aquapark

Pentru a atrage turiştii, primăria unui oraş a hotărât că va construi un parc acvatic imens cu n piscine. Parcul va avea o zonă acoperită şi va fi înconjurat de un spaţiu deschis pentru activităţi în aer liber.

Zona închisă va fi acoperită de o singură clădire de forma unui poligon, iar piscinele vor fi proiectate în vârfurile poligonului şi vor putea comunica între ele prin m căi de acces care nu se vor intersecta. Căile de acces între două piscine pot fi de tipul 1: canal umplut cu apă în interiorul clădirii, sau de tipul 2: o alee în afara clădirii.

În exemplul alăturat prin linie punctată se delimitează partea acoperită a parcului.
Avem 5 piscine, există 6 căi de acces: (1,2), (2,5), (1,4), (1,3), (3,4), (3,5), dintre care 2 sunt canale (tipul 1): (1,3) şi (1,4), respectiv 4 sunt alei (tipul 2): (1,2), (2,5), (3,4) şi (3,5).
Un alt proiect ce păstrează aceleaşi căi de acces, dar diferă prin tipul acestora, este să construim 4 canale: (1,2), (3,4), (3,5), (2,5) respectiv 2 alei: (1,3), (1,4).
În total putem construi 8 proiecte distincte cu aceste căi de acces. Două proiecte se consideră distincte dacă există cel puţin o cale de acces ce are tipuri diferite pe cele două proiecte.

Cerinţe

Cunoscând căile de acces între piscine, să se determine una dintre cerinţele următoare:

  1. o modalitate de construire a căilor de acces, precizând tipul fiecăreia;
  2. numărul proiectelor distincte.

Date de intrare

Fişierul de intrare aquapark.in conţine pe prima linie trei numerele separate prin câte un spaţiu c n m reprezentând în această ordine tipul cerinţei, numărul piscinelor respectiv numărul căilor de acces.
Următoarele m linii conţin câte două numere x şi y, reprezentând o cale de acces între piscina x şi piscina y.

Date de ieşire

Fişierul de ieşire aquapark.out va conţine în funcţie de valoarea lui c următoarele informaţii:

  • dacă c=1: pe m linii se vor tipări câte trei numere separate prin câte un spaţiu x y t, semnificând că între piscina x şi piscina y există o cale de acces de tipul t (1-canal, 2-alee). Fiecare muchie citită din fişierul de intrare va trebui să apară exact o dată în fişierul de ieşire, indiferent de ordinea citirii.
  • dacă c=2: se va tipări un singur număr ce va semnifica numărul proiectelor distincte modulo 666013.

Restricţii

  • 1 ≤ n ≤ 70 000
  • 1 ≤ m ≤ 100 000
  • Între două piscine există cel puţin o cale de acces
  • Nu există o cale de acces de la o piscină la ea însăşi
  • Se asigură că pentru datele de test există cel puţin o soluţie,
  • Dacă există mai multe soluţii se poate afişa oricare dintre acestea.
  • Pentru teste în valoare de 16 puncte n,m ≤ 15
  • Pentru alte teste în valoare de 49 de puncte n ≤ 1 000, m ≤ 1 500
  • Conform regulamentului OJI, 10 puncte se vor acorda pe exemple.

Exemplu

aquapark.inaquapark.outExplicaţie
1 5 6
1 2
2 5
1 4
3 1
4 3
5 3
1 2 1
1 3 1
1 4 1
2 5 2
3 4 1
3 5 2
c=1, se cere o modalitate de construcţie a căilor de acces:
Avem cale de acces de tip 1 (canale) între piscinele (1,2), (1,3), (1,4) şi (3,4). Avem cale de acces de tip 2 (alee) între piscinele (2,5) şi (3,5)..
Vezi desenul de mai sus.
2 5 6
1 2
2 5
1 4
3 1
4 3
5 3
8
Avem 8 modalităţi distincte de a construi căile parcului acvatic. Toate variantele posibile se pot consulta in tabelul de mai jos.
Soluţiecăi de tipul 1căi de tipul 2
1(1,2) (1,3) (1,4) (3,4)(2,5) (3,5)
2(1,3) (1,4) (3,4)(1,2) (2,5) (3,5)
3(1,2) (1,3) (1,4)(2,5) (3,5) (3,4)
4(1,3) (1,4)(1,2) (2,5) (3,5) (3,4)
5(2,5) (3,5)(1,2) (1,3) (1,4) (3,4)
6(1,2) (2,5) (3,5)(1,3) (1,4) (3,4)
7(2,5) (3,5) (3,4)(1,2) (1,3) (1,4)
8(1,2) (2,5) (3,5) (3,4)(1,3) (1,4)
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?