Informatica Online Judge

  Greedy Gift Givers(욕심쟁이 기부자들) [0250 / 00FA]

Time Limit(Test case) : 1000(ms)
Number of users who solved : 100   Total Tried : 239


The Champion of this Problem (C++) : gs18060 - ms / 584byte
My Best Submission (C++) : N/A

[]

Background

서로다른 이름을 가진 NP명(2~10 명)의 친구들로 이루어진 한무리의 친구들을 선물로 돈을 주고 받기로 결정했다. 각각의 친구는 다른 친구들 모두에게 혹은 일부에게 선물을 주거나 주지 않을 수 있다. 마찬가지로, 다른 친구들 전부 혹은 일부로부터 선물을 받거나 받지 못할 수도 있다. 이 문제에서 여러분의 목표는 각각의 사람이 다른 친구들로부터 받는 것보다 얼마나 더 많이 돈을 주는지 추론하는 것이다.


선물하는 기본적인 방법은 여러분들이 기대하는 것보다 잠재적으로 조금 다르다. 각각의 사람들은 선물할 일정 금액의 돈을 따로 떼어내어 선물을 받게될 사람들을 위해 똑같이 나눕니다. 분수로는 돈을 나눌 수 없기 때문에, 돈 3을 2명에게 나눠주려면 각 학생은 돈 1개씩 받고 1개가 남습니다. -- 1개가 남으면 주는 사람의 잔고로 남게 된다.

어떤 그룹이건 간에, 몇 사람은 다른 사람들보다 더 많이 선물해서(아니면 적어도 좀더 많은 사람을 아는 것일 수도 있다) 몇 사람은 다른 사람들 보다 돈을 많이 가지게 된다.


14문자 이내의 이름를 가진 친구들 집합, 각 친구들이 선물로 사용하는 돈, 누구 누구에게 선물을 해야하는지에 대한 리스트 가 주어진다. 주어진 그룹에서 얼마나 많은(적은) 사람이 그들이 받는 돈보다 더 많이 주는지 결정하여라.

Input

첫 번째 줄에는 NP가 입력된다. (2~10)
두번째 줄 부터 NP+1번째 줄까지 각 줄은 그룹의 멤버 이름이 입력된다.

NP+2번째 줄부터 마지막줄까지에서 첫 번째 데이터는 선물을 하게 될 사람의 이름, 두번째 라인은 2개의 정수가 공백으로 구분되는데, 첫 값은 돈, 두번째 값은 선물을 받을 사람의 수이다.

그 다음 줄에는 선물을 받을 사람의 리스트가 입력된다.

Output

출력은 NP개위 줄로 구성되며, 각 줄은 사람의 이름과 최종적으로 그 사람이 최종 금액(마지막돈-처음돈)을 출력한다. 이름은 입력된 순서대로 출력되어야 한다.

선물하는 모든 값은 정수이다. 각 사람은 돈을 받는 사람들에게 제약조건(정수값으로 나누어 주어야 한다.)을 지키는 최대로 줄수 있는 돈을 똑같이 나누어 준다. 나누고 나머지로 남은 돈은 나눠주지 않는다.

IO Example

입력
5
dave
laura
owen
vick
amr
dave
200 3
laura
owen
vick
owen
500 1
dave
amr
150 2
vick
owen
laura
0 2
amr
vick
vick
0 0


출력
dave 302
laura 66
owen -359
vick 141
amr -150


번역 및 테스트 - 전현석

출처 : USACO (http://ace.delos.com)

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]