시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 202 20 16 12.500%

문제

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

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

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

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

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

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

입력

첫째 줄에 상근이가 나무 울타리를 만드는데 사용한 나무판의 개수 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+XHViMDk4XHViYjM0XHVkMzEwXHVjNzQwIFx1Yzc4NVx1YjgyNVx1YzczY1x1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzQgXHVjMjFjXHVjMTFjXHViMzAwXHViODVjIDFcdWJjODhcdWJkODBcdWQxMzAgTlx1YmM4OFx1Yzc3NFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YjBhOFx1YzU0NFx1Yzc4OFx1YjI5NCBcdWIwOThcdWJiMzRcdWQzMTBcdWM3NTggXHVhYzFjXHVjMjE4IEJcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBcdWM3NzQgXHViNTRjLCBCXHViOTdjIFx1Y2Q1Y1x1YzE4Y1x1Yjg1YyBcdWQ1NzRcdWM1N2NcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjQ1OFx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVjNWI0XHViNWE0IFx1YjA5OFx1YmIzNFx1ZDMxMFx1Yzc3NCBcdWIwYThcdWM1NDRcdWM3ODhcdWIyOTRcdWM5YzAgXHVhY2Y1XHViYzMxXHVjNzNjXHViODVjIFx1YWQ2Y1x1YmQ4NFx1ZDU3NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIFx1YzgxNVx1YjJmNVx1Yzc3NCBcdWM1ZWNcdWI3ZWMgXHVhYzAwXHVjOWMwXHVjNzc4IFx1YWNiZFx1YzZiMFx1YzVkMFx1YjI5NCBcdWM1NDRcdWJiMzRcdWFjNzBcdWIwOTggXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjMxMTkiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJPR1JBREEiLCJkZXNjcmlwdGlvbiI6IjxwPk1pcmtvIGJ1aWx0IGEgd29vZGVuIGZlbmNlIG5leHQgdG8gaGlzIGhvdXNlLiBIZSBidWlsdCBoaXMgZmVuY2UgYnkgc2xhbW1pbmcgcmVjdGFuZ3VsYXIgd29vZGVuIGJvYXJkcyBpbnRvIHRoZSBncm91bmQuIEZvciBlYWNoIGJvYXJkIHdlIGtub3cgaXRzIGhlaWdodCwgd2lkdGggYW5kIGRpc3RhbmNlIG9mIGl0cyBsZWZ0IGVkZ2UgZnJvbSBNaXJrbyYjMzk7cyBob3VzZS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+TWlya28gd2FzIHJlYWxseSBlbmpveWluZyBidWlsZGluZyBoaXMgZmVuY2UsIHNvIG11Y2ggdGhhdCBoZSBzdG9wcGVkIHBheWluZyBhdHRlbnRpb24gYXMgdG8gaG93IGhlIHdhcyBidWlsZGluZyBpdCAmbmRhc2g7IG5vdyB0aGF0IGhlIGlzIGRvbmUsIHNvbWUgb2YgdGhlIGJvYXJkcyBhcmUgb3ZlcmxhcHBpbmcsIGFuZCB0aGVyZSBhcmUgaG9sZXMgaW4gdGhlIGZlbmNlLCB0b3RhbCBjaGFvcyEmbmJzcDs8XC9wPlxyXG5cclxuPHA+TWlya28gaXMgbm93IGxvb2tpbmcgYXQgaGlzIGZlbmNlIGFuZCBpcyBzaG9ja2VkICZuZGFzaDsgaGUgY291bGQgaGF2ZSBidWlsdCBhIGZlbmNlIHRoZSBzYW1lIGZlbmNlICh3aGVuIGxvb2tlZCBmcm9tIHVwIGZyb250KSB1c2luZyBmZXdlciBib2FyZHMuIElmIHdlIGNvbm5lY3QgdGhlIHRvcCBzaWRlcyBvZiBhbGwgYm9hcmRzIGFzIGluIHRoZSBpbWFnZSBiZWxvdywgd2UgZ2V0IHRoZSBza3lsaW5lIG9mIHRoZSBmZW5jZS4mbmJzcDs8XC9wPlxyXG5cclxuPHAgc3R5bGU9XCJ0ZXh0LWFsaWduOiBjZW50ZXI7XCI+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9za3lsaW5lLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjE2MnB4OyB0ZXh0LWFsaWduOmNlbnRlcjsgd2lkdGg6NTEwcHhcIiBcLz48XC9wPlxyXG5cclxuPHAgc3R5bGU9XCJ0ZXh0LWFsaWduOiBjZW50ZXI7XCI+VGhlIHNlY29uZCBleGFtcGxlIGlucHV0LiBUaGUgc2t5bGluZSBpcyBkZXBpY3RlZCBieSBhIGJvbGQgbGluZS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+TWlya28gZGVjaWRlZCB0byByZW1vdmUgc29tZSBvZiB0aGUgYm9hcmRzIGZyb20gdGhlIGZlbmNlIHNvIHRoYXQgdGhlIHNreWxpbmUgcmVtYWlucyB0aGUgc2FtZSBhbmQgdGhhdCBhcyBmZXcgYm9hcmRzIGFzIHBvc3NpYmxlIHJlbWFpbiBpbiB0aGUgZmVuY2UuJm5ic3A7PFwvcD5cclxuXHJcbjxwPldyaXRlIGEgcHJvZ3JhbSB0aGF0IGRldGVybWluZXMgd2hpY2ggYm9hcmRzIHNob3VsZCByZW1haW4gaW4gdGhlIGZlbmNlLiZuYnNwOzxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgY29udGFpbnMgYW4gaW50ZWdlciBOICgxICZsZTsgTiAmbGU7IDEwMCAwMDApLCB0aGUgbnVtYmVyIG9mIGJvYXJkcyBpbml0aWFsbHkgaW4gTWlya28mIzM5O3MgZmVuY2UuIEVhY2ggb2YgdGhlIGZvbGxvd2luZyBOIGxpbmVzIGRlc2NyaWJlcyBvbmUgYm9hcmQgd2l0aCB0aHJlZSBpbnRlZ2VycyBYLCBXIGFuZCBIOyB0aGVzZSBhcmUgdGhlIGRpc3RhbmNlIG9mIHRoZSBsZWZ0IGVkZ2Ugb2YgdGhlIGJvYXJkIGZyb20gTWlya28mIzM5O3MgaG91c2UsIHdpZHRoIGFuZCBoZWlnaHQgb2YgdGhlIGJvYXJkLCByZXNwZWN0aXZlbHkuIE5vIHR3byBib2FyZHMgd2lsbCBzaGFyZSB0aGUgc2FtZSAoWCwgVywgSCkgdHJpcGxldC4gQWxsIHRoZXNlIG51bWJlcnMgd2lsbCBiZSBhdCBtb3N0IGEgYmlsbGlvbiAoMTA8c3VwPjk8XC9zdXA+KS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+Qm9hcmRzIGFyZSBudW1iZXJlZCAxIHRvIE4uJm5ic3A7PFwvcD5cclxuIiwib3V0cHV0IjoiPHA+T24gdGhlIGZpcnN0IGxpbmUgb3V0cHV0IEIsIHRoZSBzbWFsbGVzdCBudW1iZXIgb2YgYm9hcmRzIHRoYXQgbmVlZCB0byByZW1haW4gZm9yIHRoZSBza3lsaW5lIHRvIHN0YXkgdGhlIHNhbWUuJm5ic3A7PFwvcD5cclxuXHJcbjxwPk9uIHRoZSBzZWNvbmQgbGluZSBvdXRwdXQgQiBpbnRlZ2VycyBzZXBhcmF0ZWQgYnkgc3BhY2VzLCB0aGUgbnVtYmVycyBvZiBib2FyZHMgdGhhdCBzaG91bGQgcmVtYWluIGluIHRoZSBmZW5jZS4gVGhpcyBwYXJ0IG9mIHRoZSBvdXRwdXQgaXMgbm90IG5lY2Vzc2FyaWx5IHVuaXF1ZS4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=

출처

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