루미는 오랜만에 친구들과 모노폴리 게임을 하기로 했다. 그런데 루미는 트레이드에 약해서 번번이 진다. 분한 루미는 이를 갈며 트레이드 AI를 만들기로 마음먹었다. 다만 AI를 잘 알지는 못해서 이번에는 간단한 AI부터 만들어 보기로 했다.
루미의 모노폴리 맵에는 가지 색상마다 도시가 개씩, 모두 개의 도시가 있다. 플레이어는 도시를 사거나, 가진 도시를 담보로 은행에서 대출을 받거나, 다른 플레이어와 도시나 현금을 주고받는 트레이드를 할 수 있다.
트레이드는 루미와 상대 플레이어 두 사람 사이에서 이루어지며, 다음 규칙을 따른다.
- 각 플레이어는 내놓을 현금과 상대에게서 받아 올 도시를 제시한다.
- 트레이드가 성사되면 두 플레이어는 제시한 현금을 서로에게 건네고, 각자 제시한 도시를 상대에게서 받아 온다.
- 담보로 잡힌 도시는 트레이드 뒤에도 담보 상태가 유지된다.
- 플레이어는 소유하지 않은 도시를 담보로 잡을 수 없다.
- 가진 현금보다 많은 현금을 제시할 수 없고, 상대가 소유하지 않은 도시를 제시할 수 없다.
이 문제에서 "자신"은 루미, "상대"는 트레이드 상대 플레이어를 가리킨다.
트레이드 AI는 플레이어의 재산 가치를 에서 시작해 다음 순서로 계산한다.
- 도시 가치: 색상마다 그 색상의 도시를 몇 개 가졌는지 센다. 색상 의 도시를 개 가졌으면 를 더하고, 하나도 없으면 더하지 않는다.
- 현금 가치: 플레이어가 가진 현금의 , 즉 를 더한다.
트레이드 AI는 (트레이드 후 자신의 재산 가치 상대의 재산 가치)가 (트레이드 전 자신의 재산 가치 상대의 재산 가치) 이상이면 유리한 트레이드로 보고 수락하고 아니면 거절한다. 루미는 자신의 트레이드 AI를 믿기 때문에 AI의 판단을 그대로 따른다.
트레이드 상황이 주어질 때 루미가 트레이드를 수락할지 구해 보자.
입력은 줄로 이루어진다.
첫째 줄부터 개의 줄에 색상별 가치가 주어진다. 번째 줄에는 색상 의 도시를 개, 개, 개, 개 가졌을 때 그 색상의 가치 가 공백으로 구분되어 주어진다.
루미가 트레이드를 수락하면 YES, 거절하면 NO를 출력한다.
자신은 색상 의 번째 도시를, 상대는 색상 의 번째 도시를 가지고 있고, 트레이드로 이 두 도시를 맞바꾼다. 트레이드 전후 모두 두 사람은 색상 의 도시를 개씩 가지므로 도시 가치는 으로 같다. 현금 가치도 으로 같아서 재산 가치의 차는 트레이드 전후 모두 이다. 차가 같으면 수락하므로 답은 이다.
번째 줄에는 트레이드 전 두 플레이어가 소유한 도시가 삼진 문자열로 주어진다.
번째 줄에는 두 플레이어가 트레이드에서 제시한 도시가 삼진 문자열로 주어진다.
번째 줄에는 담보로 잡힌 도시가 이진 문자열로 주어진다.
세 문자열은 모두 길이가 이고, 왼쪽에서 번째 문자가 색상 의 번째 도시를 나타낸다.
1, 상대가 소유한 도시는 2, 아무도 소유하지 않은 도시는 0이다.1, 상대가 자신에게서 받아 가려는 도시는 2, 그 외는 0이다.1, 그 외는 0이다. 담보로 잡힌 도시의 주인은 번째 줄로 알 수 있다., 번째 줄에는 트레이드 전 자신과 상대가 가진 현금이 차례로 한 줄에 하나씩 주어진다.
, 번째 줄에는 자신과 상대가 이번 트레이드에서 제시한 현금이 차례로 한 줄에 하나씩 주어진다.
번째 줄에는 현금 가치의 비율 가 주어진다.
번째 줄에는 담보 페널티 가 주어진다.
YES자신은 담보로 잡힌 색상 의 도시 개를 상대에게 넘기고, 상대에게서 현금 을 받는다.
| 자신 | 상대 | 차 | |
|---|---|---|---|
| 트레이드 전 | |||
| 트레이드 후 |
색상 의 도시를 개 가졌으므로 도시 가치는 이다. 담보 페널티 는 도시와 함께 상대에게 넘어간다. 트레이드 후의 차가 더 작으므로 답은 NO이다.