시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 17 9 6 42.857%

문제

어드벤처 게임을 하던 중, 1부터 n까지의 번호가 붙은 방을 지나가야 하는 마법의 미로를 마주쳤다. 각 방 안에는 번호가 붙은 문이 있을 수 있고, 각 문은 해당하는 번호의 방으로 통한다. 방 안에는 레프리콘이나 트롤이 있을 수도 있다.

레프리콘이 있는 방에 들어가면 레프리콘은 모험가의 소지금이 일정 양 이하로 떨어지지 않게 채워준다. 레프리콘은 모험가의 소지금이 일정량 미만일 때에는 그만한 양이 되도록 금화를 채워주고, 소지금이 일정량 이상일 때에는 그대로 둔다. 트롤이 있는 방에 들어가면 일정량의 통행료를 지불해야만 지나갈 수 있다.

모험가는 소지금이 0인 상태에서 출발한다. 과연 모험가는 1번방에서 출발해서 n번방에 도착할 수 있을까? n번방에 트롤이 있는 경우에도 통행료를 지불해야만 미로를 통과할 수 있다.

입력

입력은 여러 개의 미로로 주어진다. 각 미로의 첫 줄에는 미로의 방 수를 나타내는 정수 n(1 ≤ n ≤ 1000)이 주어진다. 다음 n 줄에는 각 방의 정보가 주어진다. 각 방의 정보는 방의 내용물을 나타내는 알파벳 하나(E: 빈 방, L: 레프리콘, T: 트롤)와 그 방의 레프리콘이나 트롤이 정해놓은 금액(빈 방일 경우 0이고, 금액은 500보다 작거나 같은 자연수), 그리고 그 방에서 다른 방으로 갈 수 있는 문의 번호들로 이루어진다. 각 줄은 0으로 끝난다. 미로의 방 수가 0개인 입력이 들어오면 입력을 종료한다.

출력

출력은 각 미로마다 한 줄씩으로 이루어진다. 각 줄에는 1번방에서 출구까지 갈 수 있는지를 "Yes" 또는 "No"로 출력한다.

예제 입력 1

3
E 0 2 0
L 10 3 0
T 15 1 2 0
4
E 0 2 3 0
L 201 2 3 0
L 10 4 0
T 15 2 3 1 0
0

예제 출력 1

No
Yes
W3sicHJvYmxlbV9pZCI6IjIzMTAiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM1YjRcdWI0ZGNcdWJjYTRcdWNjOTggXHVhYzhjXHVjNzg0IiwiZGVzY3JpcHRpb24iOiI8cD5cdWM1YjRcdWI0ZGNcdWJjYTRcdWNjOTggXHVhYzhjXHVjNzg0XHVjNzQ0IFx1ZDU1OFx1YjM1OCBcdWM5MTEsIDFcdWJkODBcdWQxMzAgblx1YWU0Y1x1YzljMFx1Yzc1OCBcdWJjODhcdWQ2MzhcdWFjMDAgXHViZDk5XHVjNzQwIFx1YmMyOVx1Yzc0NCBcdWM5YzBcdWIwOThcdWFjMDBcdWM1N2MgXHVkNTU4XHViMjk0IFx1YjljOFx1YmM5NVx1Yzc1OCBcdWJiZjhcdWI4NWNcdWI5N2MgXHViOWM4XHVjOGZjXHVjY2U0XHViMmU0LiBcdWFjMDEgXHViYzI5IFx1YzU0OFx1YzVkMFx1YjI5NCBcdWJjODhcdWQ2MzhcdWFjMDAgXHViZDk5XHVjNzQwIFx1YmIzOFx1Yzc3NCBcdWM3ODhcdWM3NDQgXHVjMjE4IFx1Yzc4OFx1YWNlMCwgXHVhYzAxIFx1YmIzOFx1Yzc0MCBcdWQ1NzRcdWIyZjlcdWQ1NThcdWIyOTQgXHViYzg4XHVkNjM4XHVjNzU4IFx1YmMyOVx1YzczY1x1Yjg1YyBcdWQxYjVcdWQ1NWNcdWIyZTQuIFx1YmMyOSBcdWM1NDhcdWM1ZDBcdWIyOTQgXHViODA4XHVkNTA0XHViOWFjXHVjZjU4XHVjNzc0XHViMDk4IFx1ZDJiOFx1Yjg2NFx1Yzc3NCBcdWM3ODhcdWM3NDQgXHVjMjE4XHViM2M0IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViODA4XHVkNTA0XHViOWFjXHVjZjU4XHVjNzc0IFx1Yzc4OFx1YjI5NCBcdWJjMjlcdWM1ZDAgXHViNGU0XHVjNWI0XHVhYzAwXHViYTc0IFx1YjgwOFx1ZDUwNFx1YjlhY1x1Y2Y1OFx1Yzc0MCBcdWJhYThcdWQ1ZDhcdWFjMDBcdWM3NTggXHVjMThjXHVjOWMwXHVhZTA4XHVjNzc0IFx1Yzc3Y1x1YzgxNSBcdWM1OTEgXHVjNzc0XHVkNTU4XHViODVjIFx1YjVhOFx1YzViNFx1YzljMFx1YzljMCBcdWM1NGFcdWFjOGMgXHVjYzQ0XHVjNmNjXHVjOTAwXHViMmU0LiBcdWI4MDhcdWQ1MDRcdWI5YWNcdWNmNThcdWM3NDAgXHViYWE4XHVkNWQ4XHVhYzAwXHVjNzU4IFx1YzE4Y1x1YzljMFx1YWUwOFx1Yzc3NCBcdWM3N2NcdWM4MTVcdWI3YzkgXHViYmY4XHViOWNjXHVjNzdjIFx1YjU0Y1x1YzVkMFx1YjI5NCBcdWFkZjhcdWI5Y2NcdWQ1NWMgXHVjNTkxXHVjNzc0IFx1YjQxOFx1YjNjNFx1Yjg1ZCBcdWFlMDhcdWQ2NTRcdWI5N2MgXHVjYzQ0XHVjNmNjXHVjOGZjXHVhY2UwLCBcdWMxOGNcdWM5YzBcdWFlMDhcdWM3NzQgXHVjNzdjXHVjODE1XHViN2M5IFx1Yzc3NFx1YzBjMVx1Yzc3YyBcdWI1NGNcdWM1ZDBcdWIyOTQgXHVhZGY4XHViMzAwXHViODVjIFx1YjQ1NFx1YjJlNC4gXHVkMmI4XHViODY0XHVjNzc0IFx1Yzc4OFx1YjI5NCBcdWJjMjlcdWM1ZDAgXHViNGU0XHVjNWI0XHVhYzAwXHViYTc0IFx1Yzc3Y1x1YzgxNVx1YjdjOVx1Yzc1OCBcdWQxYjVcdWQ1ODlcdWI4Y2NcdWI5N2MgXHVjOWMwXHViZDg4XHVkNTc0XHVjNTdjXHViOWNjIFx1YzljMFx1YjA5OFx1YWMwOCBcdWMyMTggXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWJhYThcdWQ1ZDhcdWFjMDBcdWIyOTQgXHVjMThjXHVjOWMwXHVhZTA4XHVjNzc0IDBcdWM3NzggXHVjMGMxXHVkMGRjXHVjNWQwXHVjMTFjIFx1Y2Q5Y1x1YmMxY1x1ZDU1Y1x1YjJlNC4gXHVhY2ZjXHVjNWYwIFx1YmFhOFx1ZDVkOFx1YWMwMFx1YjI5NCAxXHViYzg4XHViYzI5XHVjNWQwXHVjMTFjIFx1Y2Q5Y1x1YmMxY1x1ZDU3NFx1YzExYyBuXHViYzg4XHViYzI5XHVjNWQwIFx1YjNjNFx1Y2MyOVx1ZDU2MCBcdWMyMTggXHVjNzg4XHVjNzQ0XHVhZTRjPyBuXHViYzg4XHViYzI5XHVjNWQwIFx1ZDJiOFx1Yjg2NFx1Yzc3NCBcdWM3ODhcdWIyOTQgXHVhY2JkXHVjNmIwXHVjNWQwXHViM2M0IFx1ZDFiNVx1ZDU4OVx1YjhjY1x1Yjk3YyBcdWM5YzBcdWJkODhcdWQ1NzRcdWM1N2NcdWI5Y2MgXHViYmY4XHViODVjXHViOTdjIFx1ZDFiNVx1YWNmY1x1ZDU2MCBcdWMyMTggXHVjNzg4XHViMmU0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjNzg1XHViODI1XHVjNzQwIFx1YzVlY1x1YjdlYyBcdWFjMWNcdWM3NTggXHViYmY4XHViODVjXHViODVjIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVhYzAxIFx1YmJmOFx1Yjg1Y1x1Yzc1OCBcdWNjYWIgXHVjOTA0XHVjNWQwXHViMjk0IFx1YmJmOFx1Yjg1Y1x1Yzc1OCBcdWJjMjkgXHVjMjE4XHViOTdjIFx1YjA5OFx1ZDBjMFx1YjBiNFx1YjI5NCBcdWM4MTVcdWMyMTggbigxICZsZTsgbiAmbGU7IDEwMDApXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHViMmU0XHVjNzRjIG4gXHVjOTA0XHVjNWQwXHViMjk0IFx1YWMwMSBcdWJjMjlcdWM3NTggXHVjODE1XHViY2Y0XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVhYzAxIFx1YmMyOVx1Yzc1OCBcdWM4MTVcdWJjZjRcdWIyOTQgXHViYzI5XHVjNzU4IFx1YjBiNFx1YzZhOVx1YmIzY1x1Yzc0NCBcdWIwOThcdWQwYzBcdWIwYjRcdWIyOTQgXHVjNTRjXHVkMzBjXHViY2IzIFx1ZDU1OFx1YjA5OChFOiBcdWJlNDggXHViYzI5LCBMOiBcdWI4MDhcdWQ1MDRcdWI5YWNcdWNmNTgsIFQ6IFx1ZDJiOFx1Yjg2NClcdWM2NDAgXHVhZGY4IFx1YmMyOVx1Yzc1OCBcdWI4MDhcdWQ1MDRcdWI5YWNcdWNmNThcdWM3NzRcdWIwOTggXHVkMmI4XHViODY0XHVjNzc0IFx1YzgxNVx1ZDU3NFx1YjE5M1x1Yzc0MCBcdWFlMDhcdWM1NjEoXHViZTQ4IFx1YmMyOVx1Yzc3YyBcdWFjYmRcdWM2YjAgMFx1Yzc3NFx1YWNlMCwgXHVhZTA4XHVjNTYxXHVjNzQwIDUwMFx1YmNmNFx1YjJlNCBcdWM3OTFcdWFjNzBcdWIwOTggXHVhYzE5XHVjNzQwIFx1Yzc5MFx1YzVmMFx1YzIxOCksIFx1YWRmOFx1YjlhY1x1YWNlMCBcdWFkZjggXHViYzI5XHVjNWQwXHVjMTFjIFx1YjJlNFx1Yjk3OCBcdWJjMjlcdWM3M2NcdWI4NWMgXHVhYzA4IFx1YzIxOCBcdWM3ODhcdWIyOTQgXHViYjM4XHVjNzU4IFx1YmM4OFx1ZDYzOFx1YjRlNFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YWMwMSBcdWM5MDRcdWM3NDAgMFx1YzczY1x1Yjg1YyBcdWIwNWRcdWIwOWNcdWIyZTQuIFx1YmJmOFx1Yjg1Y1x1Yzc1OCBcdWJjMjkgXHVjMjE4XHVhYzAwIDBcdWFjMWNcdWM3NzggXHVjNzg1XHViODI1XHVjNzc0IFx1YjRlNFx1YzViNFx1YzYyNFx1YmE3NCBcdWM3ODVcdWI4MjVcdWM3NDQgXHVjODg1XHViOGNjXHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1Y2Q5Y1x1YjgyNVx1Yzc0MCBcdWFjMDEgXHViYmY4XHViODVjXHViOWM4XHViMmU0IFx1ZDU1YyBcdWM5MDRcdWM1MjlcdWM3M2NcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjOWM0XHViMmU0LiBcdWFjMDEgXHVjOTA0XHVjNWQwXHViMjk0IDFcdWJjODhcdWJjMjlcdWM1ZDBcdWMxMWMgXHVjZDljXHVhZDZjXHVhZTRjXHVjOWMwIFx1YWMwOCBcdWMyMTggXHVjNzg4XHViMjk0XHVjOWMwXHViOTdjICZxdW90O1llcyZxdW90OyBcdWI2MTBcdWIyOTQgJnF1b3Q7Tm8mcXVvdDtcdWI4NWMgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjIzMTAiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJBZHZlbnR1cmUgR2FtZSIsImRlc2NyaXB0aW9uIjoiPHA+UGFydCBvZiBhbiBhZHZlbnR1cmUgZ2FtZSByZXF1aXJlcyB0aGUgYWR2ZW50dXJlciB0byBtYWtlIGhlciB3YXkgdGhyb3VnaCBhIG1hZ2ljYWwgbWF6ZSBvZiBudW1iZXJlZCByb29tcy4gRWFjaCByb29tIGhhcyBhIHNldCBvZiBudW1iZXJlZCBkb29ycyB0aGF0IGxlYWQgdG8gdGhlIGluZGljYXRlZCByb29tcy4gQWRkaXRpb25hbGx5LCBlYWNoIHJvb20gbWlnaHQgY29udGFpbiBlaXRoZXIgYSBsZXByZWNoYXVuIG9yIGEgdHJvbGwuPFwvcD5cclxuXHJcbjxwPldoZW5ldmVyIHRoZSBhZHZlbnR1cmVyIHZpc2l0cyBhIHJvb20gY29udGFpbmluZyBhIGxlcHJlY2hhdW4sIHRoZSBsZXByZWNoYXVuIHdpbGwgZW5zdXJlIHRoYXQgc2hlIGxlYXZlcyB3aXRoIGF0IGxlYXN0IGEgY2VydGFpbiBudW1iZXIgb2YgZ29sZCBwaWVjZXMgKEdQKSBpbiBoZXIgc2Fjay4gVGhhdCBpcywgaWYgc2hlIGFycml2ZXMgd2l0aCBmZXdlciBHUCB0aGFuIHRoZSBwcmVzY3JpYmVkIGFtb3VudCwgdGhlbiB0aGUgbGVwcmVjaGF1biB3aWxsICZsZHF1bzt0b3AgaGVyIHVwJnJkcXVvOyB0byB0aGF0IGFtb3VudDsgaG93ZXZlciwgaWYgc2hlIGFycml2ZXMgd2l0aCB0aGUgcHJlc2NyaWJlZCBhbW91bnQgb3IgbW9yZSwgdGhlbiBoZXIgc3VwcGx5IG9mIEdQIHdpbGwgcmVtYWluIHVuY2hhbmdlZC4gRWFjaCB0aW1lIHRoZSBhZHZlbnR1cmVyIHZpc2l0cyBhIHJvb20gY29udGFpbmluZyBhIHRyb2xsLCB0aGUgdHJvbGwgd2lsbCBkZW1hbmQgYSB0b2xsIG9mIGEgY2VydGFpbiBudW1iZXIgb2YgZ29sZCBwaWVjZXMgd2hpY2ggbXVzdCBiZSBwYWlkIGJlZm9yZSBjb250aW51aW5nLjxcL3A+XHJcblxyXG48cD5UaGUgYWR2ZW50dXJlciBiZWdpbnMgd2l0aCAwIEdQIGFuZCB0aGUgcHJvYmxlbSBpcyB0byBkZXRlcm1pbmUgd2hldGhlciB0aGUgYWR2ZW50dXJlciBjYW4gbWFrZSBoZXIgd2F5IGZyb20gcm9vbSAxIHRvIHRoZSBoaWdoZXN0IG51bWJlcmVkIHJvb20uIElmIHRoZSBoaWdoZXN0IG51bWJlcmVkIHJvb20gY29udGFpbnMgYSB0cm9sbCwgdGhlIGFkdmVudHVyZXIgbXVzdCBhbHNvIGJlIGFibGUgdG8gcGF5IHRoZSB0b2xsIG9uIGFycml2YWwuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5JbnB1dCB3aWxsIGNvbnNpc3Qgb2YgYSBzZXF1ZW5jZSBvZiBtYXplcy4gRWFjaCBtYXplIHdpbGwgYmVnaW4gd2l0aCBhIGxpbmUgY29udGFpbmluZyBhbiBpbnRlZ2VyIHNwZWNpZnlpbmcgdGhlIG51bWJlciBvZiByb29tcyBpbiB0aGUgbWF6ZSAobiwgMSAmbGU7IG4gJmxlOyAxMDAwKS4gVGhpcyB3aWxsIGJlIGZvbGxvd2VkIGJ5IG4gbGluZXMgc3BlY2lmeWluZyB0aGUgcm9vbXMgaW4gYXNjZW5kaW5nIG9yZGVyLiBFYWNoIGxpbmUgd2lsbCBzcGVjaWZ5IHRoZSBjb250ZW50cyBvZiB0aGUgcm9vbSAoZW1wdHkgKEUpLCBhIGxlcHJlY2hhdW4gKEwpIG9yIGEgdHJvbGwgKFQpKSwgZm9sbG93ZWQgYnkgYSBudW1iZXIgc3BlY2lmeWluZyB0aGUgbnVtYmVyIG9mIEdQIHRoYXQgdGhlIGxlcHJlY2hhdW4gd2lsbCB0b3AgdXAgdG8sIG9yIHRoYXQgdGhlIHRyb2xsIHdpbGwgcmVxdWlyZSBmcm9tIHRoZSBhZHZlbnR1cmVyLiAoRm9yIGVtcHR5IHJvb21zIHRoaXMgYW1vdW50IGlzIDAuKSBUaGUgcmVzdCBvZiB0aGUgbGluZSBjb25zaXN0cyBvZiBhIGxpc3Qgb2YgMSBvciBtb3JlIG51bWJlcnMgaW4gdGhlIHJhbmdlIDEuLm4gYW5kIHRlcm1pbmF0ZWQgYnkgYSB6ZXJvICgwKSwgcmVwcmVzZW50aW5nIHRoZSBudW1iZXJzIG9uIHRoZSBkb29ycyBvZiB0aGF0IHJvb20uIFRoZSBzZXF1ZW5jZSBvZiBtYXplcyBpcyB0ZXJtaW5hdGVkIGJ5IGEgbGluZSBjb250YWluaW5nIGEgc2luZ2xlIHplcm8gKDApLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPk91dHB1dCB3aWxsIGNvbnNpc3Qgb2YgYSBzZXF1ZW5jZSBvZiBsaW5lcywgb25lIGZvciBlYWNoIG1hemUgJm1kYXNoOyBlaXRoZXIgJmxkcXVvO1llcyZyZHF1bzsgb3IgJmxkcXVvO05vJnJkcXVvOyBpbmRpY2F0aW5nIHdoZXRoZXIgaXQgaXMgcG9zc2libGUgdG8gcmVhY2ggdGhlIGZpbmFsIHJvb20gZnJvbSB0aGUgZmlyc3Qgb25lLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==

출처

ACM-ICPC > Regionals > South Pacific > South Pacific Region > New Zealand Programming Contest > NZPC 2005 O번