시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB210887150.000%

문제

유리수는 두 정수의 비로 나타낼 수 있다. 분자(n)와 분모(d)가 주어지면 이 분수를 n/d으로 쓴다. 유리수의 표현 방법은 유일하지 않다. 예를 들어, 1/2과 2/4는 그 값이 같다. 어떤 유리수 표현법 n/d이 gcd(|n|, |d|) = 1이라면 이것이 "기약분수로 표현되었다"라고 한다. 따라서 1/2은 기약분수로 표현되었지만 2/4는 아니다.

유리수의 덧셈은 다음과 같이 정의된다. 오른쪽 항이 기약분수로 표현되어 있다는 보장은 없음에 주목하라.

\[\frac{n_1}{d_1} + \frac{n_2}{d_2} = \frac{n_1d_2 + n_2d_1}{d_1d_2}\]

분자가 분모보다 크거나 같은 유리수는 대분수 꼴로 표현할 수 있는데, 이것은 정수부와 소수부로 이루어 진다. 예를 들어, $5 {{1}\over{3}}$은 16/3과 같은 값을 가지는 대분수 표현이다.

당신이 할 일은 유리수열을 읽어 그 합을 출력하는 것이다.

입력

입력은 몇 개의 테스트로 구성된다. 각 테스트의 정보는 첫 줄에 n(1 ≤ n < 1000)을 포함한다. n = 0인 경우 입력이 끝난다.

다음 n개의 줄은 공백이 없는 하나의 문자열이다. 각 문자열은 유리수 하나를 나타내며, 다음 세 형태 중 하나이고 기약분수로 표현되지 않을 수 있다 (w, n과 d는 정수이다: 0 ≤ w,n < 1000, 1 ≤ d < 1000).

  • w,n/d: (w * d + n) / d와 값이 같은 대분수
  • n/d: 정수부가 0인 유리수
  • w: 소수부가 0인 정수

출력

출력은 화면에 나온 대로 테스트 번호를 포함하여 합을 기약분수로 표현하여 출력한다. 만약 합의 정수부나 소수부가 없다면 각 부분을 생략하여 출력한다. 특수한 경우로, 정수부와 소수부가 모두 없다면 0을 출력해야 한다.

예제 입력 1

2
1/2
1/3
3
1/3
2/6
3/9
3
1
2/3
4,5/6
0

예제 출력 1

Test 1: 5/6
Test 2: 1
Test 3: 6,1/2
W3sicHJvYmxlbV9pZCI6IjkyMTUiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWMyZTBcdWIwOThcdWIyOTQgXHViZDg0XHVjMjE4IFx1YWNjNFx1YzBiMCIsImRlc2NyaXB0aW9uIjoiPHA+XHVjNzIwXHViOWFjXHVjMjE4XHViMjk0IFx1YjQ1MCBcdWM4MTVcdWMyMThcdWM3NTggXHViZTQ0XHViODVjIFx1YjA5OFx1ZDBjMFx1YjBiYyBcdWMyMTggXHVjNzg4XHViMmU0LiBcdWJkODRcdWM3OTAobilcdWM2NDAgXHViZDg0XHViYWE4KGQpXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljMFx1YmE3NCBcdWM3NzQgXHViZDg0XHVjMjE4XHViOTdjIG5cL2RcdWM3M2NcdWI4NWMgXHVjNGY0XHViMmU0LiBcdWM3MjBcdWI5YWNcdWMyMThcdWM3NTggXHVkNDVjXHVkNjA0IFx1YmMyOVx1YmM5NVx1Yzc0MCBcdWM3MjBcdWM3N2NcdWQ1NThcdWM5YzAgXHVjNTRhXHViMmU0LiBcdWM2MDhcdWI5N2MgXHViNGU0XHVjNWI0LCAxXC8yXHVhY2ZjIDJcLzRcdWIyOTQgXHVhZGY4IFx1YWMxMlx1Yzc3NCBcdWFjMTlcdWIyZTQuIFx1YzViNFx1YjVhNCBcdWM3MjBcdWI5YWNcdWMyMTggXHVkNDVjXHVkNjA0XHViYzk1IG5cL2RcdWM3NzQgZ2NkKHxufCwgfGR8KSA9IDFcdWM3NzRcdWI3N2NcdWJhNzQgXHVjNzc0XHVhYzgzXHVjNzc0ICZxdW90O1x1YWUzMFx1YzU3ZFx1YmQ4NFx1YzIxOFx1Yjg1YyBcdWQ0NWNcdWQ2MDRcdWI0MThcdWM1YzhcdWIyZTQmcXVvdDtcdWI3N2NcdWFjZTAgXHVkNTVjXHViMmU0LiBcdWI1MzBcdWI3N2NcdWMxMWMgMVwvMlx1Yzc0MCBcdWFlMzBcdWM1N2RcdWJkODRcdWMyMThcdWI4NWMgXHVkNDVjXHVkNjA0XHViNDE4XHVjNWM4XHVjOWMwXHViOWNjIDJcLzRcdWIyOTQgXHVjNTQ0XHViMmM4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM3MjBcdWI5YWNcdWMyMThcdWM3NTggXHViMzY3XHVjMTQ4XHVjNzQwIFx1YjJlNFx1Yzc0Y1x1YWNmYyBcdWFjMTlcdWM3NzQgXHVjODE1XHVjNzU4XHViNDFjXHViMmU0LiBcdWM2MjRcdWI5NzhcdWNhYmQgXHVkNTZkXHVjNzc0IFx1YWUzMFx1YzU3ZFx1YmQ4NFx1YzIxOFx1Yjg1YyBcdWQ0NWNcdWQ2MDRcdWI0MThcdWM1YjQgXHVjNzg4XHViMmU0XHViMjk0IFx1YmNmNFx1YzdhNVx1Yzc0MCBcdWM1YzZcdWM3NGNcdWM1ZDAgXHVjOGZjXHViYWE5XHVkNTU4XHViNzdjLjxcL3A+XHJcblxyXG48cD5cXFtcXGZyYWN7bl8xfXtkXzF9ICsgXFxmcmFje25fMn17ZF8yfSA9IFxcZnJhY3tuXzFkXzIgKyBuXzJkXzF9e2RfMWRfMn1cXF08XC9wPlxyXG5cclxuPHA+XHViZDg0XHVjNzkwXHVhYzAwIFx1YmQ4NFx1YmFhOFx1YmNmNFx1YjJlNCBcdWQwNmNcdWFjNzBcdWIwOTggXHVhYzE5XHVjNzQwIFx1YzcyMFx1YjlhY1x1YzIxOFx1YjI5NCBcdWIzMDBcdWJkODRcdWMyMTggXHVhZjM0XHViODVjIFx1ZDQ1Y1x1ZDYwNFx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMjk0XHViMzcwLCBcdWM3NzRcdWFjODNcdWM3NDAgXHVjODE1XHVjMjE4XHViZDgwXHVjNjQwIFx1YzE4Y1x1YzIxOFx1YmQ4MFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjQgXHVjOWM0XHViMmU0LiBcdWM2MDhcdWI5N2MgXHViNGU0XHVjNWI0LCAkNSB7ezF9XFxvdmVyezN9fSRcdWM3NDAgMTZcLzNcdWFjZmMgXHVhYzE5XHVjNzQwIFx1YWMxMlx1Yzc0NCBcdWFjMDBcdWM5YzBcdWIyOTQgXHViMzAwXHViZDg0XHVjMjE4IFx1ZDQ1Y1x1ZDYwNFx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViMmY5XHVjMmUwXHVjNzc0IFx1ZDU2MCBcdWM3N2NcdWM3NDAgXHVjNzIwXHViOWFjXHVjMjE4XHVjNWY0XHVjNzQ0IFx1Yzc3ZFx1YzViNCBcdWFkZjggXHVkNTY5XHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1OFx1YjI5NCBcdWFjODNcdWM3NzRcdWIyZTQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWM3ODVcdWI4MjVcdWM3NDAgXHViYTg3IFx1YWMxY1x1Yzc1OCBcdWQxNGNcdWMyYTRcdWQyYjhcdWI4NWMgXHVhZDZjXHVjMTMxXHViNDFjXHViMmU0LiBcdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4XHVjNzU4IFx1YzgxNVx1YmNmNFx1YjI5NCBcdWNjYWIgXHVjOTA0XHVjNWQwIG4oMSAmbGU7IG4gJmx0OyAxMDAwKVx1Yzc0NCBcdWQzZWNcdWQ1NjhcdWQ1NWNcdWIyZTQuIG4gPSAwXHVjNzc4IFx1YWNiZFx1YzZiMCBcdWM3ODVcdWI4MjVcdWM3NzQgXHViMDVkXHViMDljXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWIyZTRcdWM3NGMgblx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM3NDAgXHVhY2Y1XHViYzMxXHVjNzc0IFx1YzVjNlx1YjI5NCBcdWQ1NThcdWIwOThcdWM3NTggXHViYjM4XHVjNzkwXHVjNWY0XHVjNzc0XHViMmU0LiBcdWFjMDEgXHViYjM4XHVjNzkwXHVjNWY0XHVjNzQwIFx1YzcyMFx1YjlhY1x1YzIxOCBcdWQ1NThcdWIwOThcdWI5N2MgXHViMDk4XHVkMGMwXHViMGI0XHViYTcwLCBcdWIyZTRcdWM3NGMgXHVjMTM4IFx1ZDYxNVx1ZDBkYyBcdWM5MTEgXHVkNTU4XHViMDk4XHVjNzc0XHVhY2UwIFx1YWUzMFx1YzU3ZFx1YmQ4NFx1YzIxOFx1Yjg1YyBcdWQ0NWNcdWQ2MDRcdWI0MThcdWM5YzAgXHVjNTRhXHVjNzQ0IFx1YzIxOCBcdWM3ODhcdWIyZTQgKHcsIG5cdWFjZmMgZFx1YjI5NCBcdWM4MTVcdWMyMThcdWM3NzRcdWIyZTQ6IDAgJmxlOyB3LG4gJmx0OyAxMDAwLCAxICZsZTsgZCAmbHQ7IDEwMDApLjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPncsblwvZDogKHcgKiBkICsgbikgXC8gZFx1YzY0MCBcdWFjMTJcdWM3NzQgXHVhYzE5XHVjNzQwIFx1YjMwMFx1YmQ4NFx1YzIxODxcL2xpPlxyXG5cdDxsaT5uXC9kOiBcdWM4MTVcdWMyMThcdWJkODBcdWFjMDAgMFx1Yzc3OCBcdWM3MjBcdWI5YWNcdWMyMTg8XC9saT5cclxuXHQ8bGk+dzogXHVjMThjXHVjMjE4XHViZDgwXHVhYzAwIDBcdWM3NzggXHVjODE1XHVjMjE4PFwvbGk+XHJcbjxcL3VsPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWNkOWNcdWI4MjVcdWM3NDAgXHVkNjU0XHViYTc0XHVjNWQwIFx1YjA5OFx1YzYyOCBcdWIzMDBcdWI4NWMgXHVkMTRjXHVjMmE0XHVkMmI4IFx1YmM4OFx1ZDYzOFx1Yjk3YyBcdWQzZWNcdWQ1NjhcdWQ1NThcdWM1ZWMgXHVkNTY5XHVjNzQ0IFx1YWUzMFx1YzU3ZFx1YmQ4NFx1YzIxOFx1Yjg1YyBcdWQ0NWNcdWQ2MDRcdWQ1NThcdWM1ZWMgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBcdWI5Y2NcdWM1N2QgXHVkNTY5XHVjNzU4IFx1YzgxNVx1YzIxOFx1YmQ4MFx1YjA5OCBcdWMxOGNcdWMyMThcdWJkODBcdWFjMDAgXHVjNWM2XHViMmU0XHViYTc0IFx1YWMwMSBcdWJkODBcdWJkODRcdWM3NDQgXHVjMGRkXHViN2I1XHVkNTU4XHVjNWVjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gXHVkMmI5XHVjMjE4XHVkNTVjIFx1YWNiZFx1YzZiMFx1Yjg1YywgXHVjODE1XHVjMjE4XHViZDgwXHVjNjQwIFx1YzE4Y1x1YzIxOFx1YmQ4MFx1YWMwMCBcdWJhYThcdWI0NTAgXHVjNWM2XHViMmU0XHViYTc0IDBcdWM3NDQgXHVjZDljXHViODI1XHVkNTc0XHVjNTdjIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4ifSx7InByb2JsZW1faWQiOiI5MjE1IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiRnVuIFdpdGggRnJhY3Rpb25zIiwiZGVzY3JpcHRpb24iOiI8cD5BIHJhdGlvbmFsIG51bWJlciBjYW4gYmUgcmVwcmVzZW50ZWQgYXMgdGhlIHJhdGlvIG9mIHR3byBpbnRlZ2VycywgcmVmZXJyZWQgdG8gYXMgdGhlIG51bWVyYXRvciAobikgYW5kIHRoZSBkZW5vbWluYXRvciAoZCkgYW5kIHdyaXR0ZW4gblwvZC4gQSByYXRpb25hbCBudW1iZXImIzM5O3MgcmVwcmVzZW50YXRpb24gaXMgbm90IHVuaXF1ZS4gRm9yIGV4YW1wbGUgdGhlIHJhdGlvbmFsIG51bWJlcnMgMVwvMiBhbmQgMlwvNCBhcmUgZXF1aXZhbGVudC4gQSByYXRpb25hbCBudW1iZXIgcmVwcmVzZW50YXRpb24gaXMgZGVzY3JpYmVkIGFzICZxdW90O2luIGxvd2VzdCB0ZXJtcyZxdW90OyBpZiB0aGUgbnVtZXJhdG9yIGFuZCBkZW5vbWluYXRvciBoYXZlIG5vIGNvbW1vbiBmYWN0b3JzLiBUaHVzIDFcLzIgaXMgaW4gbG93ZXN0IHRlcm1zIGJ1dCAyXC80IGlzIG5vdC4gQSByYXRpb25hbCBudW1iZXIgY2FuIGJlIHJlZHVjZWQgdG8gbG93ZXN0IHRlcm1zIGJ5IGRpdmlkaW5nIGJ5IHRoZSBncmVhdGVzdCBjb21tb24gZGl2aXNvciBvZiBuIGFuZCBkLjxcL3A+XHJcblxyXG48cD5BZGRpdGlvbiBvZiByYXRpb25hbCBudW1iZXJzIGlzIGRlZmluZWQgYXMgZm9sbG93cy4gTm90ZSB0aGF0IHRoZSByaWdodCBoYW5kIHNpZGUgb2YgdGhpcyBlcXVhbGl0eSB3aWxsIG5vdCBuZWNlc3NhcmlseSBiZSBpbiBsb3dlc3QgdGVybXMuPFwvcD5cclxuXHJcbjxwPlxcW1xcZnJhY3tuXzF9e2RfMX0gKyBcXGZyYWN7bl8yfXtkXzJ9ID0gXFxmcmFje25fMWRfMiArIG5fMmRfMX17ZF8xZF8yfVxcXTxcL3A+XHJcblxyXG48cD5BIHJhdGlvbmFsIG51bWJlciBmb3Igd2hpY2ggdGhlIG51bWVyYXRvciBpcyBncmVhdGVyIHRoYW4gb3IgZXF1YWwgdG8gdGhlIGRlbm9taW5hdG9yIGNhbiBiZSBkaXNwbGF5ZWQgaW4gbWl4ZWQgZm9ybWF0LCB3aGljaCBpbmNsdWRlcyBhIHdob2xlIG51bWJlciBwYXJ0IGFuZCBhIGZyYWN0aW9uYWwgcGFydC4gRm9yIGV4YW1wbGUsICQ1IHt7MX1cXG92ZXJ7M319JCBpcyBhIG1peGVkIGZvcm1hdCByZXByZXNlbnRhdGlvbiBvZiB0aGUgcmF0aW9uYWwgbnVtYmVyIDE2XC8zLjxcL3A+XHJcblxyXG48cD5Zb3VyIHRhc2sgaXMgdG8gd3JpdGUgYSBwcm9ncmFtIHRoYXQgcmVhZHMgYSBzZXF1ZW5jZSBvZiByYXRpb25hbCBudW1iZXJzIGFuZCBkaXNwbGF5cyB0aGVpciBzdW0uPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5JbnB1dCB3aWxsIGNvbnNpc3Qgb2Ygc3BlY2lmaWNhdGlvbnMgZm9yIGEgc2VyaWVzIG9mIHRlc3RzLiBJbmZvcm1hdGlvbiBmb3IgZWFjaCB0ZXN0IGJlZ2lucyB3aXRoIGEgbGluZSBjb250YWluaW5nIGEgc2luZ2xlIGludGVnZXIgMSAmbHQ7PSBuICZsdDsgMTAwMCBpbmRpY2F0aW5nIGhvdyBtYW55IHZhbHVlcyBmb2xsb3cuIEEgY291bnQgb2YgemVybyB0ZXJtaW5hdGVzIHRoZSBpbnB1dC48XC9wPlxyXG5cclxuPHA+VGhlIG4gZm9sbG93aW5nIGxpbmVzIGVhY2ggY29udGFpbiBhIHNpbmdsZSBzdHJpbmcgd2l0aCBubyBlbWJlZGRlZCB3aGl0ZXNwYWNlIC4gRWFjaCBzdHJpbmcgcmVwcmVzZW50cyBhIHJhdGlvbmFsIG51bWJlciwgd2hpY2ggY291bGQgYmUgaW4gYW55IG9mIHRoZSBmb2xsb3dpbmcgZm9ybXMgYW5kIHdpbGwgbm90IG5lY2Vzc2FyaWx5IGJlIGluIGxvd2VzdCB0ZXJtcyAodywgbiwgYW5kIGQgYXJlIGludGVnZXJzOiAwICZsdDs9IHcsbiAmbHQ7IDEwMDAsIDEgJmx0Oz0gZCAmbHQ7IDEwMDApLjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPncsblwvZDogYSBtaXhlZCBudW1iZXIgZXF1aXZhbGVudCB0byB0aGUgcmF0aW9uYWwgbnVtYmVyICh3KmQgKyBuKSBcLyBkLjxcL2xpPlxyXG5cdDxsaT5uXC9kOiBhIHJhdGlvbmFsIG51bWJlciB3aXRoIGEgemVybyB3aG9sZSBudW1iZXIgcGFydDxcL2xpPlxyXG5cdDxsaT53OiBhIHdob2xlIG51bWJlciB3aXRoIGEgemVybyBmcmFjdGlvbmFsIHBhcnQ8XC9saT5cclxuPFwvdWw+XHJcbiIsIm91dHB1dCI6IjxwPk91dHB1dCBzaG91bGQgY29uc2lzdCBvZiBvbmUgbGluZSBmb3IgZWFjaCB0ZXN0IGNvbXByaXNpbmcgdGhlIHRlc3QgbnVtYmVyIChmb3JtYXR0ZWQgYXMgc2hvd24pIGZvbGxvd2VkIGJ5IGEgc2luZ2xlIHNwYWNlIGFuZCB0aGUgc3VtIG9mIHRoZSBpbnB1dCBudW1iZXIgc2VxdWVuY2UuIFRoZSBzdW0gc2hvdWxkIGJlIGRpc3BsYXllZCBpbiBsb3dlc3QgdGVybXMgdXNpbmcgbWl4ZWQgbnVtYmVyIGZvcm1hdC4gSWYgZWl0aGVyIHRoZSB3aG9sZSBudW1iZXIgcGFydCBvciB0aGUgZnJhY3Rpb25hbCBwYXJ0IGlzIHplcm8sIHRoYXQgcGFydCBzaG91bGQgYmUgb21pdHRlZC4gQXMgYSBzcGVjaWFsIGNhc2UsIGlmIGJvdGggcGFydHMgYXJlIHplcm8sIHRoZSB2YWx1ZSBzaG91bGQgYmUgZGlzcGxheWVkIGFzIGEgc2luZ2xlIDAuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCJ9XQ==

출처

ICPC > Regionals > South Pacific > South Pacific Region > Australian Programming Contest > AuPC 2013 C번

  • 잘못된 번역을 찾은 사람: jh05013
  • 문제를 번역한 사람: kipa00