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

문제

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

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

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

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

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

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

입력

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

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

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

출력

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

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

예제 입력 1

5
10 11 30
19 1 20
15 9 10
7 7 20
3 12 40

예제 출력 1

3
1 3 5

예제 입력 2

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

예제 출력 2

5
1 2 3 4 5
W3sicHJvYmxlbV9pZCI6IjMxMTkiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM2YjhcdWQwYzBcdWI5YWMiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCBcdWM5ZDEgXHVjNjA2XHVjNWQwIFx1YjA5OFx1YmIzNCBcdWM2YjhcdWQwYzBcdWI5YWNcdWI5N2MgXHViOWNjXHViNGU0XHVhY2UwIFx1Yzc4OFx1YjJlNC4gXHViMDk4XHViYjM0IFx1YzZiOFx1ZDBjMFx1YjlhY1x1YjI5NCBcdWM5YzFcdWMwYWNcdWFjMDFcdWQ2MTUgXHViMDk4XHViYjM0XHVkMzEwXHVjNzQ0IFx1YjU0NVx1YzVkMCBcdWFmNDJcdWM1NDRcdWMxMWMgXHViOWNjXHViNGUwXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM2YjhcdWQwYzBcdWI5YWNcdWI5N2MgXHViOWNjXHViNGU0XHViMmU0XHViY2Y0XHViMmM4IFx1YzgxMFx1YzgxMCBcdWQ3NjVcdWM3NzQgXHViMGFjXHVhY2UwLCBcdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgXHVjNmI4XHVkMGMwXHViOWFjIFx1YWNjNFx1ZDY4ZFx1Yzc0NCBcdWFlNGNcdWJhMzlcdWFjZTAgXHViOWM4XHVhZDZjIFx1YjA5OFx1YmIzNFx1ZDMxMFx1Yzc0NCBcdWFmNDJcdWM1NThcdWIyZTQuIFx1YzZiOFx1ZDBjMFx1YjlhY1x1Yjk3YyBcdWM2NDRcdWMxMzFcdWQ1NWMgXHVkNmM0IFx1YmZjY1x1YjRlZlx1ZDU3NFx1ZDU1OFx1YmE3NFx1YzExYyBcdWM2YjhcdWQwYzBcdWI5YWNcdWI5N2MgXHViY2Y4IFx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCBcdWIzMDBcdWQ2M2NcdWI3ODBcdWM1ZDAgXHViZTYwXHVjODRjXHViMmU0LiBcdWIwOThcdWJiMzRcdWQzMTBcdWM3NDQgXHVhY2I5XHVjY2QwXHVjMTFjIFx1YWY0Mlx1YWUzMFx1YjNjNCBcdWQ1ODhcdWFjZTAsIFx1YzJlY1x1YzljMFx1YzViNCBcdWM2YjhcdWQwYzBcdWI5YWMgXHVjOTExXHVhYzA0XHVjNWQwIFx1YWQ2Y1x1YmE0ZFx1YjNjNCBcdWM3ODhcdWM1YzhcdWFlMzAgXHViNTRjXHViYjM4XHVjNzc0XHVjNWM4XHViMmU0LjxcL3A+XHJcblxyXG48cCBzdHlsZT1cInRleHQtYWxpZ246Y2VudGVyXCI+PGltZyBhbHQ9XCJcIiBzcmM9XCJodHRwczpcL1wvdXBsb2FkLmFjbWljcGMubmV0XC83YTlmZmQ1Ni1hZTFiLTRkOTYtODE5Yi0zMGY1ZjY5ZTU5MmZcLy1cL3ByZXZpZXdcL1wiIHN0eWxlPVwiaGVpZ2h0OiAxNDhweDsgd2lkdGg6IDQ4N3B4O1wiIFwvPjxcL3A+XHJcblxyXG48cCBzdHlsZT1cInRleHQtYWxpZ246Y2VudGVyXCI+XHVjNjA4XHVjODFjXHViOTdjIFx1YWRmOFx1YjliY1x1YzczY1x1Yjg1YyBcdWIwOThcdWQwYzBcdWIwYjggXHVhYzgzXHVjNzc0XHViMmU0LiBcdWFkNzVcdWM3NDAgXHVjMTIwXHVjNzc0IFx1YzJhNFx1Y2U3NFx1Yzc3NFx1Yjc3Y1x1Yzc3OFx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNTQ0XHVjOWMxIFx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCBcdWM2YjhcdWQwYzBcdWI5YWNcdWI5N2MgXHViY2Y0XHVhY2UwIFx1Y2RhOVx1YWNhOVx1YzVkMCBcdWJlNjBcdWM5YzQgXHVjMGMxXHVkMGRjXHVjNzc0XHViMmU0LiBcdWM3NzRcdWJiZjggXHVjNjQ0XHVjMTMxXHViNDFjIFx1YzZiOFx1ZDBjMFx1YjlhY1x1YWMwMCBcdWI5YzhcdWM3NGNcdWM1ZDAgXHViNGU0XHVjNWM4XHVhZTMwIFx1YjU0Y1x1YmIzOFx1YzVkMCwgXHViNjExXHVhYzE5XHVjNzQwIFx1YmFhOFx1YzU5MVx1Yzc1OCBcdWM2YjhcdWQwYzBcdWI5YWNcdWI5N2MgXHViMzU0IFx1YzgwMVx1Yzc0MCBcdWMyMThcdWM3NTggXHViMDk4XHViYjM0XHVkMzEwXHVjNzQ0IFx1Yzc3NFx1YzZhOVx1ZDU3NFx1YzExYyBcdWI5Y2NcdWI0ZTRcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWI2MTFcdWFjMTlcdWM3NDAgXHViYWE4XHVjNTkxXHVjNzU4IFx1YzZiOFx1ZDBjMFx1YjlhY1x1Yjc4MCBcdWMyYTRcdWNlNzRcdWM3NzRcdWI3N2NcdWM3NzhcdWM3NzQgXHVhYzE5XHVjNzQwIFx1YzZiOFx1ZDBjMFx1YjlhY1x1Yjk3YyBcdWI5ZDBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzViNFx1YjVhNCBcdWIwOThcdWJiMzRcdWQzMTBcdWM3OTBcdWI5N2MgXHViMGE4XHVhY2E4XHVjNTdjIFx1YjYxMVx1YWMxOVx1Yzc0MCBcdWJhYThcdWM1OTFcdWM3NTggXHVjNmI4XHVkMGMwXHViOWFjXHVhYzAwIFx1YjQxOFx1YjI5NFx1YzljMCBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVjMGMxXHVhZGZjXHVjNzc0XHVhYzAwIFx1YjA5OFx1YmIzNCBcdWM2YjhcdWQwYzBcdWI5YWNcdWI5N2MgXHViOWNjXHViNGRjXHViMjk0XHViMzcwIFx1YzBhY1x1YzZhOVx1ZDU1YyBcdWIwOThcdWJiMzRcdWQzMTBcdWM3NTggXHVhYzFjXHVjMjE4IE4gKDEgJmxlOyBOICZsZTsgMTAwLDAwMClcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWIyZTRcdWM3NGMgTlx1YWMxYyBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVhYzAxIFx1YjA5OFx1YmIzNFx1ZDMxMFx1Yzc1OCBcdWM4MTVcdWJjZjQgWCwgVywgSFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFhcdWIyOTQgXHVjMGMxXHVhZGZjXHVjNzc0XHVjNzU4IFx1YzlkMVx1YzVkMFx1YzExY1x1YmQ4MFx1ZDEzMCZuYnNwO1x1YjVhOFx1YzViNFx1YzljNCBcdWFjNzBcdWI5YWMsIFdcdWM2NDAgSFx1YjI5NCBcdWIwOThcdWJiMzRcdWQzMTBcdWM3NTggXHViMTA4XHViZTQ0XHVjNjQwIFx1YjE5Mlx1Yzc3NFx1Yzc3NFx1YjJlNC4gXHViYWE4XHViNGUwIFx1YzIxOFx1YjI5NCAxMDxzdXA+OTxcL3N1cD5cdWI5N2MgXHViMTE4XHVjOWMwIFx1YzU0YVx1YjI5NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViMDk4XHViYjM0XHVkMzEwXHVjNzQwIFx1Yzc4NVx1YjgyNVx1YzczY1x1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzQgXHVjMjFjXHVjMTFjXHViMzAwXHViODVjIDFcdWJjODhcdWJkODBcdWQxMzAgTlx1YmM4OFx1Yzc3NFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YjBhOFx1YzU0NFx1Yzc4OFx1YjI5NCBcdWIwOThcdWJiMzRcdWQzMTBcdWM3NTggXHVhYzFjXHVjMjE4IEJcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBcdWM3NzRcdWI1NGMsIEJcdWI5N2MgXHVjZDVjXHVjMThjXHViODVjIFx1ZDU3NFx1YzU3Y1x1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViNDU4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWM1YjRcdWI1YTQgXHViMDk4XHViYjM0XHVkMzEwXHVjNzc0IFx1YjBhOFx1YzU0NFx1Yzc4OFx1YjI5NFx1YzljMCBcdWFjZjVcdWJjMzFcdWM3M2NcdWI4NWMgXHVhZDZjXHViZDg0XHVkNTc0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gXHVjODE1XHViMmY1XHVjNzc0IFx1YzVlY1x1YjdlYyBcdWFjMDBcdWM5YzBcdWM3NzggXHVhY2JkXHVjNmIwXHVjNWQwXHViMjk0IFx1YzU0NFx1YmIzNFx1YWM3MFx1YjA5OCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIn0seyJwcm9ibGVtX2lkIjoiMzExOSIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6Ik9HUkFEQSIsImRlc2NyaXB0aW9uIjoiPHA+TWlya28gYnVpbHQgYSB3b29kZW4gZmVuY2UgbmV4dCB0byBoaXMgaG91c2UuIEhlIGJ1aWx0IGhpcyBmZW5jZSBieSBzbGFtbWluZyByZWN0YW5ndWxhciB3b29kZW4gYm9hcmRzIGludG8gdGhlIGdyb3VuZC4gRm9yIGVhY2ggYm9hcmQgd2Uga25vdyBpdHMgaGVpZ2h0LCB3aWR0aCBhbmQgZGlzdGFuY2Ugb2YgaXRzIGxlZnQgZWRnZSBmcm9tIE1pcmtvJiMzOTtzIGhvdXNlLiZuYnNwOzxcL3A+XHJcblxyXG48cD5NaXJrbyB3YXMgcmVhbGx5IGVuam95aW5nIGJ1aWxkaW5nIGhpcyBmZW5jZSwgc28gbXVjaCB0aGF0IGhlIHN0b3BwZWQgcGF5aW5nIGF0dGVudGlvbiBhcyB0byBob3cgaGUgd2FzIGJ1aWxkaW5nIGl0ICZuZGFzaDsgbm93IHRoYXQgaGUgaXMgZG9uZSwgc29tZSBvZiB0aGUgYm9hcmRzIGFyZSBvdmVybGFwcGluZywgYW5kIHRoZXJlIGFyZSBob2xlcyBpbiB0aGUgZmVuY2UsIHRvdGFsIGNoYW9zISZuYnNwOzxcL3A+XHJcblxyXG48cD5NaXJrbyBpcyBub3cgbG9va2luZyBhdCBoaXMgZmVuY2UgYW5kIGlzIHNob2NrZWQgJm5kYXNoOyBoZSBjb3VsZCBoYXZlIGJ1aWx0IGEgZmVuY2UgdGhlIHNhbWUgZmVuY2UgKHdoZW4gbG9va2VkIGZyb20gdXAgZnJvbnQpIHVzaW5nIGZld2VyIGJvYXJkcy4gSWYgd2UgY29ubmVjdCB0aGUgdG9wIHNpZGVzIG9mIGFsbCBib2FyZHMgYXMgaW4gdGhlIGltYWdlIGJlbG93LCB3ZSBnZXQgdGhlIHNreWxpbmUgb2YgdGhlIGZlbmNlLiZuYnNwOzxcL3A+XHJcblxyXG48cCBzdHlsZT1cInRleHQtYWxpZ246IGNlbnRlcjtcIj48aW1nIGFsdD1cIlwiIHNyYz1cImh0dHBzOlwvXC91cGxvYWQuYWNtaWNwYy5uZXRcLzdhOWZmZDU2LWFlMWItNGQ5Ni04MTliLTMwZjVmNjllNTkyZlwvLVwvcHJldmlld1wvXCIgc3R5bGU9XCJoZWlnaHQ6IDE0OHB4OyB3aWR0aDogNDg3cHg7XCIgXC8+PFwvcD5cclxuXHJcbjxwIHN0eWxlPVwidGV4dC1hbGlnbjogY2VudGVyO1wiPlRoZSBzZWNvbmQgZXhhbXBsZSBpbnB1dC4gVGhlIHNreWxpbmUgaXMgZGVwaWN0ZWQgYnkgYSBib2xkIGxpbmUuJm5ic3A7PFwvcD5cclxuXHJcbjxwPk1pcmtvIGRlY2lkZWQgdG8gcmVtb3ZlIHNvbWUgb2YgdGhlIGJvYXJkcyBmcm9tIHRoZSBmZW5jZSBzbyB0aGF0IHRoZSBza3lsaW5lIHJlbWFpbnMgdGhlIHNhbWUgYW5kIHRoYXQgYXMgZmV3IGJvYXJkcyBhcyBwb3NzaWJsZSByZW1haW4gaW4gdGhlIGZlbmNlLiZuYnNwOzxcL3A+XHJcblxyXG48cD5Xcml0ZSBhIHByb2dyYW0gdGhhdCBkZXRlcm1pbmVzIHdoaWNoIGJvYXJkcyBzaG91bGQgcmVtYWluIGluIHRoZSBmZW5jZS4mbmJzcDs8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIGNvbnRhaW5zIGFuIGludGVnZXIgTiAoMSAmbGU7IE4gJmxlOyAxMDAgMDAwKSwgdGhlIG51bWJlciBvZiBib2FyZHMgaW5pdGlhbGx5IGluIE1pcmtvJiMzOTtzIGZlbmNlLiBFYWNoIG9mIHRoZSBmb2xsb3dpbmcgTiBsaW5lcyBkZXNjcmliZXMgb25lIGJvYXJkIHdpdGggdGhyZWUgaW50ZWdlcnMgWCwgVyBhbmQgSDsgdGhlc2UgYXJlIHRoZSBkaXN0YW5jZSBvZiB0aGUgbGVmdCBlZGdlIG9mIHRoZSBib2FyZCBmcm9tIE1pcmtvJiMzOTtzIGhvdXNlLCB3aWR0aCBhbmQgaGVpZ2h0IG9mIHRoZSBib2FyZCwgcmVzcGVjdGl2ZWx5LiBObyB0d28gYm9hcmRzIHdpbGwgc2hhcmUgdGhlIHNhbWUgKFgsIFcsIEgpIHRyaXBsZXQuIEFsbCB0aGVzZSBudW1iZXJzIHdpbGwgYmUgYXQgbW9zdCBhIGJpbGxpb24gKDEwPHN1cD45PFwvc3VwPikuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkJvYXJkcyBhcmUgbnVtYmVyZWQgMSB0byBOLiZuYnNwOzxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPk9uIHRoZSBmaXJzdCBsaW5lIG91dHB1dCBCLCB0aGUgc21hbGxlc3QgbnVtYmVyIG9mIGJvYXJkcyB0aGF0IG5lZWQgdG8gcmVtYWluIGZvciB0aGUgc2t5bGluZSB0byBzdGF5IHRoZSBzYW1lLiZuYnNwOzxcL3A+XHJcblxyXG48cD5PbiB0aGUgc2Vjb25kIGxpbmUgb3V0cHV0IEIgaW50ZWdlcnMgc2VwYXJhdGVkIGJ5IHNwYWNlcywgdGhlIG51bWJlcnMgb2YgYm9hcmRzIHRoYXQgc2hvdWxkIHJlbWFpbiBpbiB0aGUgZmVuY2UuIFRoaXMgcGFydCBvZiB0aGUgb3V0cHV0IGlzIG5vdCBuZWNlc3NhcmlseSB1bmlxdWUuJm5ic3A7PFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCJ9XQ==

출처

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