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.
Cunoscând căile de acces între piscine, să se determine una dintre cerințele următoare:
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
.
Fișierul de ieșire aquapark.out
va conține în funcție de valoarea lui c
următoarele informații:
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.c=2
: se va tipări un singur număr ce va semnifica numărul proiectelor distincte modulo 666013
.1 ≤ n ≤ 70000
1 ≤ m ≤ 100000
16
puncte n,m ≤ 15
49
de puncte n ≤ 1000, m ≤ 1500
100
de puncte dintre care 10
puncte din oficiu.aquapark.in
1 5 6
1 2
2 5
1 4
3 1
4 3
5 3
aquapark.out
1 2 1
1 3 1
1 4 1
2 5 2
3 4 1
3 5 2
aquapark.in
2 5 6
1 2
2 5
1 4
3 1
4 3
5 3
aquapark.out
8
Pentru primul test:
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.
Pentru al doilea test:
Avem 8
modalități distincte de a construi căile parcului acvatic:
Soluție | căi de tipul 1 | că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) |
ID: 25
Upload: liviu
Input: aquapark.in/aquapark.out
Memory limit: 128MB/32MB
Time limit: 0.2s
Author: Szabo Zoltan, Budau Adrian
Source: OJI 2018 XI-XII: Problema 3
Points by default: 10p