Županijsko natjecanje 2011. godine za 1. i 2. razred Srednje Škole - 2. zadatak

Marko je zaljubljenik u kemiju i upravo je kupio novi set epruveta. Marko je oduševljen novim epruvetama, a još ga više oduševljavaju dvije stvari - to što su epruvete različitih polumjera i to što su epruvete beskonačno visoke.

Kao i svaki pravi kemičar, prije upotrebe kemikalija, Marko je odlučio testirati svoje epruvete pomodu obične vode.

Marko testira epruvete na način da poreda svih n epruveta jednu do druge i označi ih brojevima od 1 do n. Nakon toga svaku epruvetu napuni vodom do određene visine, te nasumično odabere dvije epruvete i prelije sav sadržaj iz jedne u drugu. Proces slučajnog odabira dviju epruveta i prelijevanja vode ponovi M puta.

Nakon svih prelijevanja, Marka zanima kolika je visina vode u svakoj pojedinoj epruveti.

Međutim, Marko, kao i svaki pravi kemičar, želi biti jako precizan u svojim mjerenjima, pa visinu vode želi predstaviti kao cijeli broj, potpuno skradeni razlomak ili potpuno skradeni parcijalni razlomak (ukoliko visina nije cijeli broj).

Pomozite Marku i napišite program koji za zadanih N epruveta i M prelijevanja izračuna visine vode u svim epruvetama na kraju testa.

ULAZNI PODACI

U prvom retku se nalazi prirodni broj N (1 ≤ N ≤ 10 000) koji označava broj epruveta koje je Marko kupio.

U svakom od sljededih N redaka nalaze se po dva prirodna broja Ri i Hi (1 ≤ R ≤ 1 000, 1 ≤ H ≤ 1 000 ) koji označavaju polumjer i-te epruvete i visinu vode u njoj.

U sljededem retku se nalazi jedan prirodan broj M (1 ≤ M ≤ 10 000) koji označava broj prelijevanja koje Marko želi izvesti.

U svakom od sljededih M redaka nalaze se po dva prirodna broja Xj i Yj (1 ≤ X,Y ≤ N) koji označavaju redne brojeve epruveta između kojih se vrši j-to prelijevanje. Sva voda se prelije iz epruvete X u epruvetu Y.

Napomena: volumen valjka iznosi V = r2

• h * π (gdje je V volumen, r radijus baze, a h visina valjka)

IZLAZNI PODACI

U prvih N redaka ispišite visinu vode u svakoj pojedinoj epruveti nakon svih izvršenih prelijevanja, počevši od prve, pa sve do n-te epruvete.

Visine vode ispisati na sljededi način:

• Ukoliko je visina vode cijeli broj, ispišite samo taj broj,
• Ukoliko visina vode nije cijeli broj i manja je od 1 tada ispišite visinu vode u obliku potpuno skradenog razlomka (2/3, 7/9, 23/44),
• Ukoliko visina vode nije cijeli broj i veda je od 1 tada ispišite visinu vode u obliku potpuno skradenog parcijalnog razlomka (7 3/5, 2 11/16, 1 14/17). Cijeli broj i razlomak moraju biti odvojeni jednim razmakom.

PRIMJERI TEST PODATAKA

ulaz

3
3 6
4 3
2 5
2
1 3
3 1

izlaz

8 2/9
3
0

ulaz

5
3 6
6 4
1 8
6 6
5 1
5
2 5
3 1
5 3
4 3
2 3

izlaz

6 8/9
0
385
0
0

ulaz

7
3 6
20 1
3 5
2 2
4 3
3 7
1 5
6
2 3
1 4
5 4
4 1
7 2
5 4

izlaz

12 2/9
1/80
49 4/9
0
0
7
0