시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 219 24 18 13.235%

문제

상근이는 집 옆에 나무 울타리를 만들고 있다. 나무 울타리는 직사각형 나무판을 땅에 꽂아서 만든다.

울타리를 만들다보니 점점 흥이 났고, 상근이는 울타리 계획을 까먹고 마구 나무판을 꽂았다. 울타리를 완성하고 보니 뿌듯해하면서 울타리를 본 상근이는 대혼란에 빠졌다. 나무판을 겹쳐서 꽂기도 했고, 심지어 울타리 중간에 구멍도 있었기 때문이었다.

예제를 그림으로 나타낸 것이다. 굵은 선이 스카이라인이다.

아직 상근이는 울타리를 보고 충격에 빠진 상태이다. 이미 완성된 울타리가 마음에 들었기 때문에, 똑같은 모양의 울타리를 더 적은 수의 나무판을 이용해서 만드려고 한다.

똑같은 모양의 울타리란 스카인라인이 같은 울타리를 말한다.

어떤 나무판자를 남겨야 똑같은 모양의 울타리가 되는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 상근이가 나무 울타리를 만드는데 사용한 나무판의 개수 N (1 ≤ N ≤ 100,000)이 주어진다.

다음 N개 줄에는 각 나무판의 정보 X, W, H가 주어진다. X는 상근이의 집에서부터 떨어진 거리, W와 H는 나무판의 너비와 높이이다. 모든 숫자는 109를 넘지 않는다.

나무판은 입력으로 주어진 순서대로 1번부터 N번이다.

출력

첫째 줄에 남아있는 나무판의 개수 B를 출력한다. 이때, B를 최소로 해야한다.

둘째 줄에는 어떤 나무판이 남아있는지 공백으로 구분해 출력한다. 정답이 여러 가지인 경우에는 아무거나 출력한다.

예제 입력 1

6
15 8 4
10 8 3
25 3 7
3 9 5
1 5 3
7 2 2

예제 출력 1

5
1 2 3 4 5
W3sicHJvYmxlbV9pZCI6IjMxMTkiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM2YjhcdWQwYzBcdWI5YWMiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCBcdWM5ZDEgXHVjNjA2XHVjNWQwIFx1YjA5OFx1YmIzNCBcdWM2YjhcdWQwYzBcdWI5YWNcdWI5N2MgXHViOWNjXHViNGU0XHVhY2UwIFx1Yzc4OFx1YjJlNC4gXHViMDk4XHViYjM0IFx1YzZiOFx1ZDBjMFx1YjlhY1x1YjI5NCBcdWM5YzFcdWMwYWNcdWFjMDFcdWQ2MTUgXHViMDk4XHViYjM0XHVkMzEwXHVjNzQ0IFx1YjU0NVx1YzVkMCBcdWFmNDJcdWM1NDRcdWMxMWMgXHViOWNjXHViNGUwXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM2YjhcdWQwYzBcdWI5YWNcdWI5N2MgXHViOWNjXHViNGU0XHViMmU0XHViY2Y0XHViMmM4IFx1YzgxMFx1YzgxMCBcdWQ3NjVcdWM3NzQgXHViMGFjXHVhY2UwLCBcdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgXHVjNmI4XHVkMGMwXHViOWFjIFx1YWNjNFx1ZDY4ZFx1Yzc0NCBcdWFlNGNcdWJhMzlcdWFjZTAgXHViOWM4XHVhZDZjIFx1YjA5OFx1YmIzNFx1ZDMxMFx1Yzc0NCBcdWFmNDJcdWM1NThcdWIyZTQuIFx1YzZiOFx1ZDBjMFx1YjlhY1x1Yjk3YyBcdWM2NDRcdWMxMzFcdWQ1NThcdWFjZTAgXHViY2Y0XHViMmM4IFx1YmZjY1x1YjRlZlx1ZDU3NFx1ZDU1OFx1YmE3NFx1YzExYyBcdWM2YjhcdWQwYzBcdWI5YWNcdWI5N2MgXHViY2Y4IFx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCBcdWIzMDBcdWQ2M2NcdWI3ODBcdWM1ZDAgXHViZTYwXHVjODRjXHViMmU0LiBcdWIwOThcdWJiMzRcdWQzMTBcdWM3NDQgXHVhY2I5XHVjY2QwXHVjMTFjIFx1YWY0Mlx1YWUzMFx1YjNjNCBcdWQ1ODhcdWFjZTAsIFx1YzJlY1x1YzljMFx1YzViNCBcdWM2YjhcdWQwYzBcdWI5YWMgXHVjOTExXHVhYzA0XHVjNWQwIFx1YWQ2Y1x1YmE0ZFx1YjNjNCBcdWM3ODhcdWM1YzhcdWFlMzAgXHViNTRjXHViYjM4XHVjNzc0XHVjNWM4XHViMmU0LjxcL3A+XHJcblxyXG48cCBzdHlsZT1cInRleHQtYWxpZ246Y2VudGVyXCI+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9za3lsaW5lLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjE2MnB4OyB3aWR0aDo1MTBweFwiIFwvPjxcL3A+XHJcblxyXG48cCBzdHlsZT1cInRleHQtYWxpZ246Y2VudGVyXCI+XHVjNjA4XHVjODFjXHViOTdjIFx1YWRmOFx1YjliY1x1YzczY1x1Yjg1YyBcdWIwOThcdWQwYzBcdWIwYjggXHVhYzgzXHVjNzc0XHViMmU0LiBcdWFkNzVcdWM3NDAgXHVjMTIwXHVjNzc0IFx1YzJhNFx1Y2U3NFx1Yzc3NFx1Yjc3Y1x1Yzc3OFx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNTQ0XHVjOWMxIFx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCBcdWM2YjhcdWQwYzBcdWI5YWNcdWI5N2MgXHViY2Y0XHVhY2UwIFx1Y2RhOVx1YWNhOVx1YzVkMCBcdWJlNjBcdWM5YzQgXHVjMGMxXHVkMGRjXHVjNzc0XHViMmU0LiBcdWM3NzRcdWJiZjggXHVjNjQ0XHVjMTMxXHViNDFjIFx1YzZiOFx1ZDBjMFx1YjlhY1x1YWMwMCBcdWI5YzhcdWM3NGNcdWM1ZDAgXHViNGU0XHVjNWM4XHVhZTMwIFx1YjU0Y1x1YmIzOFx1YzVkMCwgXHViNjExXHVhYzE5XHVjNzQwIFx1YmFhOFx1YzU5MVx1Yzc1OCBcdWM2YjhcdWQwYzBcdWI5YWNcdWI5N2MgXHViMzU0IFx1YzgwMVx1Yzc0MCBcdWMyMThcdWM3NTggXHViMDk4XHViYjM0XHVkMzEwXHVjNzQ0IFx1Yzc3NFx1YzZhOVx1ZDU3NFx1YzExYyBcdWI5Y2NcdWI0ZGNcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWI2MTFcdWFjMTlcdWM3NDAgXHViYWE4XHVjNTkxXHVjNzU4IFx1YzZiOFx1ZDBjMFx1YjlhY1x1Yjc4MCBcdWMyYTRcdWNlNzRcdWM3NzhcdWI3N2NcdWM3NzhcdWM3NzQgXHVhYzE5XHVjNzQwIFx1YzZiOFx1ZDBjMFx1YjlhY1x1Yjk3YyBcdWI5ZDBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzViNFx1YjVhNCBcdWIwOThcdWJiMzRcdWQzMTBcdWM3OTBcdWI5N2MgXHViMGE4XHVhY2E4XHVjNTdjIFx1YjYxMVx1YWMxOVx1Yzc0MCBcdWJhYThcdWM1OTFcdWM3NTggXHVjNmI4XHVkMGMwXHViOWFjXHVhYzAwIFx1YjQxOFx1YjI5NFx1YzljMCBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVjMGMxXHVhZGZjXHVjNzc0XHVhYzAwIFx1YjA5OFx1YmIzNCBcdWM2YjhcdWQwYzBcdWI5YWNcdWI5N2MgXHViOWNjXHViNGRjXHViMjk0XHViMzcwIFx1YzBhY1x1YzZhOVx1ZDU1YyBcdWIwOThcdWJiMzRcdWQzMTBcdWM3NTggXHVhYzFjXHVjMjE4IE4gKDEgJmxlOyBOICZsZTsgMTAwLDAwMClcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWIyZTRcdWM3NGMgTlx1YWMxYyBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVhYzAxIFx1YjA5OFx1YmIzNFx1ZDMxMFx1Yzc1OCBcdWM4MTVcdWJjZjQgWCwgVywgSFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFhcdWIyOTQgXHVjMGMxXHVhZGZjXHVjNzc0XHVjNzU4IFx1YzlkMVx1YzVkMFx1YzExY1x1YmQ4MFx1ZDEzMCZuYnNwO1x1YjVhOFx1YzViNFx1YzljNCBcdWFjNzBcdWI5YWMsIFdcdWM2NDAgSFx1YjI5NCBcdWIwOThcdWJiMzRcdWQzMTBcdWM3NTggXHViMTA4XHViZTQ0XHVjNjQwIFx1YjE5Mlx1Yzc3NFx1Yzc3NFx1YjJlNC4gXHViYWE4XHViNGUwIFx1YzIyYlx1Yzc5MFx1YjI5NCAxMDxzdXA+OTxcL3N1cD5cdWI5N2MgXHViMTE4XHVjOWMwIFx1YzU0YVx1YjI5NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViMDk4XHViYjM0XHVkMzEwXHVjNzQwIFx1Yzc4NVx1YjgyNVx1YzczY1x1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzQgXHVjMjFjXHVjMTFjXHViMzAwXHViODVjIDFcdWJjODhcdWJkODBcdWQxMzAgTlx1YmM4OFx1Yzc3NFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YjBhOFx1YzU0NFx1Yzc4OFx1YjI5NCBcdWIwOThcdWJiMzRcdWQzMTBcdWM3NTggXHVhYzFjXHVjMjE4IEJcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBcdWM3NzRcdWI1NGMsIEJcdWI5N2MgXHVjZDVjXHVjMThjXHViODVjIFx1ZDU3NFx1YzU3Y1x1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViNDU4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWM1YjRcdWI1YTQgXHViMDk4XHViYjM0XHVkMzEwXHVjNzc0IFx1YjBhOFx1YzU0NFx1Yzc4OFx1YjI5NFx1YzljMCBcdWFjZjVcdWJjMzFcdWM3M2NcdWI4NWMgXHVhZDZjXHViZDg0XHVkNTc0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gXHVjODE1XHViMmY1XHVjNzc0IFx1YzVlY1x1YjdlYyBcdWFjMDBcdWM5YzBcdWM3NzggXHVhY2JkXHVjNmIwXHVjNWQwXHViMjk0IFx1YzU0NFx1YmIzNFx1YWM3MFx1YjA5OCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMzExOSIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6Ik9HUkFEQSIsImRlc2NyaXB0aW9uIjoiPHA+TWlya28gYnVpbHQgYSB3b29kZW4gZmVuY2UgbmV4dCB0byBoaXMgaG91c2UuIEhlIGJ1aWx0IGhpcyBmZW5jZSBieSBzbGFtbWluZyByZWN0YW5ndWxhciB3b29kZW4gYm9hcmRzIGludG8gdGhlIGdyb3VuZC4gRm9yIGVhY2ggYm9hcmQgd2Uga25vdyBpdHMgaGVpZ2h0LCB3aWR0aCBhbmQgZGlzdGFuY2Ugb2YgaXRzIGxlZnQgZWRnZSBmcm9tIE1pcmtvJiMzOTtzIGhvdXNlLiZuYnNwOzxcL3A+XHJcblxyXG48cD5NaXJrbyB3YXMgcmVhbGx5IGVuam95aW5nIGJ1aWxkaW5nIGhpcyBmZW5jZSwgc28gbXVjaCB0aGF0IGhlIHN0b3BwZWQgcGF5aW5nIGF0dGVudGlvbiBhcyB0byBob3cgaGUgd2FzIGJ1aWxkaW5nIGl0ICZuZGFzaDsgbm93IHRoYXQgaGUgaXMgZG9uZSwgc29tZSBvZiB0aGUgYm9hcmRzIGFyZSBvdmVybGFwcGluZywgYW5kIHRoZXJlIGFyZSBob2xlcyBpbiB0aGUgZmVuY2UsIHRvdGFsIGNoYW9zISZuYnNwOzxcL3A+XHJcblxyXG48cD5NaXJrbyBpcyBub3cgbG9va2luZyBhdCBoaXMgZmVuY2UgYW5kIGlzIHNob2NrZWQgJm5kYXNoOyBoZSBjb3VsZCBoYXZlIGJ1aWx0IGEgZmVuY2UgdGhlIHNhbWUgZmVuY2UgKHdoZW4gbG9va2VkIGZyb20gdXAgZnJvbnQpIHVzaW5nIGZld2VyIGJvYXJkcy4gSWYgd2UgY29ubmVjdCB0aGUgdG9wIHNpZGVzIG9mIGFsbCBib2FyZHMgYXMgaW4gdGhlIGltYWdlIGJlbG93LCB3ZSBnZXQgdGhlIHNreWxpbmUgb2YgdGhlIGZlbmNlLiZuYnNwOzxcL3A+XHJcblxyXG48cCBzdHlsZT1cInRleHQtYWxpZ246IGNlbnRlcjtcIj48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL3NreWxpbmUucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MTYycHg7IHRleHQtYWxpZ246Y2VudGVyOyB3aWR0aDo1MTBweFwiIFwvPjxcL3A+XHJcblxyXG48cCBzdHlsZT1cInRleHQtYWxpZ246IGNlbnRlcjtcIj5UaGUgc2Vjb25kIGV4YW1wbGUgaW5wdXQuIFRoZSBza3lsaW5lIGlzIGRlcGljdGVkIGJ5IGEgYm9sZCBsaW5lLiZuYnNwOzxcL3A+XHJcblxyXG48cD5NaXJrbyBkZWNpZGVkIHRvIHJlbW92ZSBzb21lIG9mIHRoZSBib2FyZHMgZnJvbSB0aGUgZmVuY2Ugc28gdGhhdCB0aGUgc2t5bGluZSByZW1haW5zIHRoZSBzYW1lIGFuZCB0aGF0IGFzIGZldyBib2FyZHMgYXMgcG9zc2libGUgcmVtYWluIGluIHRoZSBmZW5jZS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+V3JpdGUgYSBwcm9ncmFtIHRoYXQgZGV0ZXJtaW5lcyB3aGljaCBib2FyZHMgc2hvdWxkIHJlbWFpbiBpbiB0aGUgZmVuY2UuJm5ic3A7PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBjb250YWlucyBhbiBpbnRlZ2VyIE4gKDEgJmxlOyBOICZsZTsgMTAwIDAwMCksIHRoZSBudW1iZXIgb2YgYm9hcmRzIGluaXRpYWxseSBpbiBNaXJrbyYjMzk7cyBmZW5jZS4gRWFjaCBvZiB0aGUgZm9sbG93aW5nIE4gbGluZXMgZGVzY3JpYmVzIG9uZSBib2FyZCB3aXRoIHRocmVlIGludGVnZXJzIFgsIFcgYW5kIEg7IHRoZXNlIGFyZSB0aGUgZGlzdGFuY2Ugb2YgdGhlIGxlZnQgZWRnZSBvZiB0aGUgYm9hcmQgZnJvbSBNaXJrbyYjMzk7cyBob3VzZSwgd2lkdGggYW5kIGhlaWdodCBvZiB0aGUgYm9hcmQsIHJlc3BlY3RpdmVseS4gTm8gdHdvIGJvYXJkcyB3aWxsIHNoYXJlIHRoZSBzYW1lIChYLCBXLCBIKSB0cmlwbGV0LiBBbGwgdGhlc2UgbnVtYmVycyB3aWxsIGJlIGF0IG1vc3QgYSBiaWxsaW9uICgxMDxzdXA+OTxcL3N1cD4pLiZuYnNwOzxcL3A+XHJcblxyXG48cD5Cb2FyZHMgYXJlIG51bWJlcmVkIDEgdG8gTi4mbmJzcDs8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5PbiB0aGUgZmlyc3QgbGluZSBvdXRwdXQgQiwgdGhlIHNtYWxsZXN0IG51bWJlciBvZiBib2FyZHMgdGhhdCBuZWVkIHRvIHJlbWFpbiBmb3IgdGhlIHNreWxpbmUgdG8gc3RheSB0aGUgc2FtZS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+T24gdGhlIHNlY29uZCBsaW5lIG91dHB1dCBCIGludGVnZXJzIHNlcGFyYXRlZCBieSBzcGFjZXMsIHRoZSBudW1iZXJzIG9mIGJvYXJkcyB0aGF0IHNob3VsZCByZW1haW4gaW4gdGhlIGZlbmNlLiBUaGlzIHBhcnQgb2YgdGhlIG91dHB1dCBpcyBub3QgbmVjZXNzYXJpbHkgdW5pcXVlLiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==

출처

Olympiad > Croatian Highschool Competitions in Informatics > 2009 > Final Exam #1 1번