Logo
(追記) (追記ここまで)

4933번 - 뉴턴의 사과 다국어

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

문제

두 바이너리 트리 A와 B는 다음과 같은 두 조건을 만족할 때 동등하다고 한다.

1. 두 트리가 비어있다. 또는,

2. 두 트리의 루트가 같다. 또:

(a) A의 왼쪽 서브 트리가 B의 왼쪽 서브 트리와 동등하고, A의 오른쪽 서브 트리가 B의 오른쪽 서브 트리와 동등하다. 또는,

(b) A의 왼쪽 서브 트리가 B의 오른쪽 서브 트리와 동등하고, A의 오른쪽 서브 트리가 B의 왼쪽 서브 트리와 동등하다.

예를 들어, 아래 왼쪽 3개 트리는 서로 동등하다. 하지만, 가장 오른쪽 트리와는 동등하지 않다.

두 바이너리 트리가 주어졌을 때, 동등한지 아닌지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 두 줄로 이루어져 있다. 각 줄은 비교해야 하는 트리의 정보이다.

각 트리의 정보는 포스트오더로 주어진다. 서브트리가 없는 경우에는 nil로 주어진다. 트리의 모든 데이터는 알파벳 대문자이다. 각 줄의 마지막은 end가 있다. 예를 들어, 문제 설명의 가장 왼쪽 그림을 포스트오더로 나타내면 다음과 같다.

nil nil nil G F nil nil C nil nil E nil D B A end

출력

각 테스트 케이스에 대해서, 두 트리가 동등하면 true를, 아니면 false를 출력한다.

제한

예제 입력 1 

2
nil nil nil G F nil nil C nil nil E nil D B A end
nil nil C nil nil E nil D B nil nil G nil F A end
nil nil nil E D nil nil C B nil nil nil G F A end
nil nil nil E C nil nil D B nil nil nil G F A end

예제 출력 1 

true
false

힌트

W3sicHJvYmxlbV9pZCI6IjQ5MzMiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWIyNzRcdWQxMzRcdWM3NTggXHVjMGFjXHVhY2ZjIiwiZGVzY3JpcHRpb24iOiI8cD5cclxuXHRcdWI0NTAgXHViYzE0XHVjNzc0XHViMTA4XHViOWFjIFx1ZDJiOFx1YjlhYyBBXHVjNjQwIEJcdWIyOTQgXHViMmU0XHVjNzRjXHVhY2ZjIFx1YWMxOVx1Yzc0MCBcdWI0NTAgXHVjODcwXHVhYzc0XHVjNzQ0IFx1YjljY1x1Yzg3MVx1ZDU2MCBcdWI1NGMgXHViM2Q5XHViNGYxXHVkNTU4XHViMmU0XHVhY2UwIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHJcblx0MS4gXHViNDUwIFx1ZDJiOFx1YjlhY1x1YWMwMCBcdWJlNDRcdWM1YjRcdWM3ODhcdWIyZTQuIFx1YjYxMFx1YjI5NCw8XC9wPlxyXG48cD5cclxuXHQyLiBcdWI0NTAgXHVkMmI4XHViOWFjXHVjNzU4IFx1YjhlOFx1ZDJiOFx1YWMwMCBcdWFjMTlcdWIyZTQuIFx1YjYxMDo8XC9wPlxyXG48cD4oYSkgQVx1Yzc1OCBcdWM2N2NcdWNhYmQgXHVjMTFjXHViZTBjIFx1ZDJiOFx1YjlhY1x1YWMwMCBCXHVjNzU4IFx1YzY3Y1x1Y2FiZCBcdWMxMWNcdWJlMGMgXHVkMmI4XHViOWFjXHVjNjQwIFx1YjNkOVx1YjRmMVx1ZDU1OFx1YWNlMCwgQVx1Yzc1OCBcdWM2MjRcdWI5NzhcdWNhYmQgXHVjMTFjXHViZTBjIFx1ZDJiOFx1YjlhY1x1YWMwMCBCXHVjNzU4IFx1YzYyNFx1Yjk3OFx1Y2FiZCBcdWMxMWNcdWJlMGMgXHVkMmI4XHViOWFjXHVjNjQwIFx1YjNkOVx1YjRmMVx1ZDU1OFx1YjJlNC4gXHViNjEwXHViMjk0LDxcL3A+XHJcbjxwPihiKSBBXHVjNzU4IFx1YzY3Y1x1Y2FiZCBcdWMxMWNcdWJlMGMgXHVkMmI4XHViOWFjXHVhYzAwIEJcdWM3NTggXHVjNjI0XHViOTc4XHVjYWJkIFx1YzExY1x1YmUwYyBcdWQyYjhcdWI5YWNcdWM2NDAgXHViM2Q5XHViNGYxXHVkNTU4XHVhY2UwLCBBXHVjNzU4IFx1YzYyNFx1Yjk3OFx1Y2FiZCBcdWMxMWNcdWJlMGMgXHVkMmI4XHViOWFjXHVhYzAwIEJcdWM3NTggXHVjNjdjXHVjYWJkIFx1YzExY1x1YmUwYyBcdWQyYjhcdWI5YWNcdWM2NDAgXHViM2Q5XHViNGYxXHVkNTU4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cclxuXHRcdWM2MDhcdWI5N2MgXHViNGU0XHVjNWI0LCBcdWM1NDRcdWI3OTggXHVjNjdjXHVjYWJkIDNcdWFjMWMgXHVkMmI4XHViOWFjXHViMjk0IFx1YzExY1x1Yjg1YyBcdWIzZDlcdWI0ZjFcdWQ1NThcdWIyZTQuIFx1ZDU1OFx1YzljMFx1YjljYywgXHVhYzAwXHVjN2E1IFx1YzYyNFx1Yjk3OFx1Y2FiZCBcdWQyYjhcdWI5YWNcdWM2NDBcdWIyOTQgXHViM2Q5XHViNGYxXHVkNTU4XHVjOWMwIFx1YzU0YVx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHJcblx0PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC90cmVlKDEpLnBuZ1wiIHN0eWxlPVwid2lkdGg6IDQ2N3B4OyBoZWlnaHQ6IDE1NHB4O1wiIFwvPjxcL3A+XHJcblxyXG48cD5cclxuXHRcdWI0NTAgXHViYzE0XHVjNzc0XHViMTA4XHViOWFjIFx1ZDJiOFx1YjlhY1x1YWMwMCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBcdWIzZDlcdWI0ZjFcdWQ1NWNcdWM5YzAgXHVjNTQ0XHViMmNjXHVjOWMwIFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiXHJcbjxwPlxyXG5cdFx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWFjMWNcdWMyMTggVFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViMjk0IFx1YjQ1MCBcdWM5MDRcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YjJlNC4gXHVhYzAxIFx1YzkwNFx1Yzc0MCBcdWJlNDRcdWFkNTBcdWQ1NzRcdWM1N2MgXHVkNTU4XHViMjk0IFx1ZDJiOFx1YjlhY1x1Yzc1OCBcdWM4MTVcdWJjZjRcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1YWMwMSBcdWQyYjhcdWI5YWNcdWM3NTggXHVjODE1XHViY2Y0XHViMjk0IFx1ZDNlY1x1YzJhNFx1ZDJiOFx1YzYyNFx1YjM1NFx1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YzExY1x1YmUwY1x1ZDJiOFx1YjlhY1x1YWMwMCBcdWM1YzZcdWIyOTQgXHVhY2JkXHVjNmIwXHVjNWQwXHViMjk0IG5pbFx1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1ZDJiOFx1YjlhY1x1Yzc1OCBcdWJhYThcdWI0ZTAgXHViMzcwXHVjNzc0XHVkMTMwXHViMjk0IFx1YzU0Y1x1ZDMwY1x1YmNiMyBcdWIzMDBcdWJiMzhcdWM3OTBcdWM3NzRcdWIyZTQuIFx1YWMwMSBcdWM5MDRcdWM3NTggXHViOWM4XHVjOWMwXHViOWM5XHVjNzQwIGVuZFx1YWMwMCBcdWM3ODhcdWIyZTQuIFx1YzYwOFx1Yjk3YyBcdWI0ZTRcdWM1YjQsIFx1YmIzOFx1YzgxYyBcdWMxMjRcdWJhODVcdWM3NTggXHVhYzAwXHVjN2E1IFx1YzY3Y1x1Y2FiZCBcdWFkZjhcdWI5YmNcdWM3NDQgXHVkM2VjXHVjMmE0XHVkMmI4XHVjNjI0XHViMzU0XHViODVjIFx1YjA5OFx1ZDBjMFx1YjBiNFx1YmE3NCBcdWIyZTRcdWM3NGNcdWFjZmMgXHVhYzE5XHViMmU0LjxcL3A+XHJcblxyXG48cD5cclxuXHRuaWwgbmlsIG5pbCBHIEYgbmlsIG5pbCBDIG5pbCBuaWwgRSBuaWwgRCBCIEEgZW5kPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHJcblx0XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM1ZDAgXHViMzAwXHVkNTc0XHVjMTFjLCBcdWI0NTAgXHVkMmI4XHViOWFjXHVhYzAwIFx1YjNkOVx1YjRmMVx1ZDU1OFx1YmE3NCB0cnVlXHViOTdjLCBcdWM1NDRcdWIyYzhcdWJhNzQgZmFsc2VcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IktvcmVhbiJ9LHsicHJvYmxlbV9pZCI6IjQ5MzMiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJOZXd0b25cdTIwMTlzIEFwcGxlIiwiZGVzY3JpcHRpb24iOiI8cD5Ud28gYmluYXJ5IHRyZWVzIChjYWxsZWQgQSBhbmQgQikgYXJlIGVxdWl2YWxlbnQgaWYgYW5kIG9ubHkgaWYgb25lIG9mIHRoZSBmb2xsb3dpbmcgdHdvIGNvbmRpdGlvbnMgaG9sZHM6PFwvcD5cclxuXHJcbjxvbD5cclxuXHQ8bGk+Qm90aCB0cmVlcyBhcmUgZW1wdHkuIE9yLDxcL2xpPlxyXG5cdDxsaT5UaGUgcm9vdCBub2RlcyBvZiBib3RoIHRyZWVzIGFyZSBlcXVhbCwgYW5kIGVpdGhlcjpcclxuXHQ8b2wgc3R5bGU9XCJsaXN0LXN0eWxlLXR5cGU6bG93ZXItYWxwaGFcIj5cclxuXHRcdDxsaT50aGUgbGVmdCBzdWJ0cmVlIG9mIEEgaXMgZXF1aXZhbGVudCB0byB0aGUgbGVmdCBzdWJ0cmVlIG9mIEIsIGFuZCB0aGUgcmlnaHQgc3VidHJlZSBvZiBBIGlzIGVxdWl2YWxlbnQgdG8gdGhlIHJpZ2h0IHN1YnRyZWUgb2YgQi4gT3IsPFwvbGk+XHJcblx0XHQ8bGk+dGhlIGxlZnQgc3VidHJlZSBvZiBBIGlzIGVxdWl2YWxlbnQgdG8gdGhlIHJpZ2h0IHN1YnRyZWUgb2YgQiwgYW5kIHRoZSByaWdodCBzdWJ0cmVlIG9mIEEgaXMgZXF1aXZhbGVudCB0byB0aGUgbGVmdCBzdWJ0cmVlIG9mIEIuPFwvbGk+XHJcblx0PFwvb2w+XHJcblx0PFwvbGk+XHJcbjxcL29sPlxyXG5cclxuPHA+Rm9yIGV4YW1wbGUsIHRoZSB0aHJlZSB0cmVlcyBvbiB0aGUgbGVmdCBvZiB0aGUgZm9sbG93aW5nIFx1ZmIwMWd1cmUgYXJlIGFsbCBlcXVpdmFsZW50IHRvIGVhY2ggb3RoZXIgYnV0IG5vbmUgaXMgZXF1aXZhbGVudCB0byB0aGUgcmlnaHQtbW9zdCB0cmVlLjxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL3RyZWUoMSkucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MTU0cHg7IHdpZHRoOjQ2N3B4XCIgXC8+PFwvcD5cclxuXHJcbjxwPldyaXRlIGEgcHJvZ3JhbSB0aGF0IGRldGVybWluZXMgaWYgdHdvIGdpdmVuIGJpbmFyeSB0cmVlcyBhcmUgZXF1aXZhbGVudCBvciBub3QuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5Zb3VyIHByb2dyYW0gd2lsbCBiZSB0ZXN0ZWQgb24gYSBudW1iZXIgb2YgdGVzdCBjYXNlcy4gVGhlIFx1ZmIwMXJzdCBsaW5lIG9mIHRoZSBpbnB1dCBjb250YWlucyBhbiBpbnRlZ2VyIEQgd2hpY2ggcmVwcmVzZW50cyB0aGUgbnVtYmVyIG9mIHRlc3QgY2FzZXMuIEVhY2ggdGVzdCBjYXNlIGlzIHNwZWNpXHVmYjAxZWQgb24gdHdvIGxpbmVzLiBUaGUgXHVmYjAxcnN0IGxpbmUgc3BlY2lcdWZiMDFlcyB0aGUgXHVmYjAxcnN0IHRyZWUsIHdpdGggdGhlIHNlY29uZCB0cmVlIHNwZWNpXHVmYjAxZWQgb24gdGhlIHNlY29uZCBsaW5lLiBFYWNoIHRyZWUgaXMgc3BlY2lcdWZiMDFlZCB1c2luZyBhIGxlZnQtdG8tcmlnaHQgcG9zdFx1ZmIwMXggbm90YXRpb24gd2hlcmUgZWFjaCBlbXB0eSBzdWJ0cmVlIGlzIGV4cGxpY2l0bHkgc3BlY2lcdWZiMDFlZCB1c2luZyB0aGUga2V5d29yZCBuaWwuIEFsbCBkYXRhIGluIHRoZSB0cmVlIGFyZSB1cHBlci1jYXNlIGxldHRlcnMuIFRoZSBlbmQgb2YgdGhlIGxpbmUgaXMgc3BlY2lcdWZiMDFlZCB1c2luZyB0aGUga2V5d29yZCBlbmQuIEZvciBleGFtcGxlLCB0aGUgdHJlZSBvbiB0aGUgbGVmdCBvZiB0aGUgXHVmYjAxZ3VyZSBpcyBzcGVjaVx1ZmIwMWVkIGFzOjxcL3A+XHJcblxyXG48cHJlPlxyXG5uaWwgbmlsIG5pbCBHIEYgbmlsIG5pbCBDIG5pbCBuaWwgRSBuaWwgRCBCIEEgZW5kPFwvcHJlPlxyXG4iLCJvdXRwdXQiOiI8cD5Gb3IgZWFjaCB0ZXN0IGNhc2UsIHByaW50IG9uIGEgc2VwYXJhdGUgbGluZSwgdGhlIHdvcmQgJnF1b3Q7dHJ1ZSZxdW90OyBpZiB0aGUgdHdvIHRyZWVzIGFyZSBlcXVpdmFsZW50LiBPdGhlcndpc2UgcHJpbnQgJnF1b3Q7ZmFsc2UmcXVvdDsuPFwvcD5cclxuXHJcbjxwPlRoZSB0d28gdGVzdCBjYXNlcyBpbiB0aGUgZm9sbG93aW5nIHNhbXBsZSBJXC9PIHJlcHJlc2VudCB0aGUgZm91ciB0cmVlcyBkcmF3biBvbiB0aGUgcHJldmlvdXMgcGFnZSAoZnJvbSBsZWZ0IHRvIHJpZ2h0KTxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2gifV0=

출처

ICPC > Regionals > Africa and Arab > Arab Collegiate Programming Contest > 2005 Arab Collegiate Programming Contest F번

(追記) (追記ここまで)

출처

대학교 대회

  • 사업자 등록 번호: 541-88-00682
  • 대표자명: 최백준
  • 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
  • 전화번호: 02-521-0487 (이메일로 연락 주세요)
  • 이메일: contacts@startlink.io
  • 통신판매신고번호: 제 2017-서울서초-2193 호

AltStyle によって変換されたページ (->オリジナル) /