시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 256 MB79333122938.423%

문제

상근이는 올림픽을 매우 좋아하면서 싫어한다. 올림픽을 좋아하는 이유는 많은 스포츠 경기를 볼 수 있기 때문이고, 싫어하는 이유는 경기가 동시에 열리기 때문이다.

방금 올림픽이 열리는 장소에 도착을 했다. 하지만, 경기가 동시에 열리기 때문에, 상근이는 모든 경기를 실시간으로 볼 수 없다.

모든 경기의 시작 시간과 종료 시간, 그리고 날짜가 주어진다. 이때, 상근이가 볼 수 있는 경기의 최대 개수를 구하는 프로그램을 작성하시오. 상근이는 경기장에 시작 시간에 들어가며, 종료 시간에 나오게된다. 한 경기를 보던 중에 다른 경기를 보기 위해 경기장을 옮길 수 없다. 또, 경기장을 이동하는데 걸리는 시간은 없다. 마지막으로, 경기가 시작된 이후에는 경기장에 들어갈 수 없다.

입력

입력의 첫째 줄에는 테스트 케이스의 개수 n이 주어진다.

각 테스트 케이스의 첫째 줄에는 경기의 수  1 ≤ m ≤ 50000 이 주어진다. 다음 m개 줄에는 각 경기의 정보를 나타내는 세 정수 d, s, e가 주어진다. d는 경기의 날짜, s는 시작 시간, e는 종료 시간을 나타낸다. 시간은 hhmm형식으로 주어지며, 모든 경기는 시작한 날에 끝난다.

출력

각 테스트 케이스마다 "Scenario #i:"를 출력한다. 여기서 i는 테스트 케이스 번호이며 1부터 시작한다. 그 다음 줄에는 상근이가 참석할 수 있는 경기의 최대 개수를 출력한다. 문제에서도 설명했지만, 경기장을 이동하는데 걸리는 시간은 없다. 즉, 경기 A의 종료 시간이 B의 시작 시간과 같은 경우에 상근이는 A 이후에 바로 B로 이동할 수 있다. 각 테스트 케이스 사이에는 빈 줄을 하나 출력한다.

예제 입력 1

2
10
1 1220 1340
2 1155 1220
2 1220 1340
3 1220 1240
1 1200 1320
2 1250 1310
2 1330 1550
3 1030 1130
3 1130 1300
3 1240 1330
3
1 0500 2200
1 0000 0700
1 2000 2359

예제 출력 1

Scenario #1:
7

Scenario #2:
2
W3sicHJvYmxlbV9pZCI6Ijc1MDciLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM2MmNcdWI5YmNcdWQ1M2QgXHVhYzhjXHVjNzg0IiwiZGVzY3JpcHRpb24iOiI8cD5cdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgXHVjNjJjXHViOWJjXHVkNTNkXHVjNzQ0IFx1YjllNFx1YzZiMCBcdWM4OGJcdWM1NDRcdWQ1NThcdWJhNzRcdWMxMWMgXHVjMmViXHVjNWI0XHVkNTVjXHViMmU0LiBcdWM2MmNcdWI5YmNcdWQ1M2RcdWM3NDQgXHVjODhiXHVjNTQ0XHVkNTU4XHViMjk0IFx1Yzc3NFx1YzcyMFx1YjI5NCBcdWI5Y2VcdWM3NDAgXHVjMmE0XHVkM2VjXHVjZTIwIFx1YWNiZFx1YWUzMFx1Yjk3YyBcdWJjZmMgXHVjMjE4IFx1Yzc4OFx1YWUzMCBcdWI1NGNcdWJiMzhcdWM3NzRcdWFjZTAsIFx1YzJlYlx1YzViNFx1ZDU1OFx1YjI5NCBcdWM3NzRcdWM3MjBcdWIyOTQgXHVhY2JkXHVhZTMwXHVhYzAwIFx1YjNkOVx1YzJkY1x1YzVkMCBcdWM1ZjRcdWI5YWNcdWFlMzAgXHViNTRjXHViYjM4XHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWJjMjlcdWFlMDggXHVjNjJjXHViOWJjXHVkNTNkXHVjNzc0IFx1YzVmNFx1YjlhY1x1YjI5NCBcdWM3YTVcdWMxOGNcdWM1ZDAgXHViM2M0XHVjYzI5XHVjNzQ0IFx1ZDU4OFx1YjJlNC4gXHVkNTU4XHVjOWMwXHViOWNjLCBcdWFjYmRcdWFlMzBcdWFjMDAgXHViM2Q5XHVjMmRjXHVjNWQwIFx1YzVmNFx1YjlhY1x1YWUzMCBcdWI1NGNcdWJiMzhcdWM1ZDAsIFx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCBcdWJhYThcdWI0ZTAgXHVhY2JkXHVhZTMwXHViOTdjIFx1YzJlNFx1YzJkY1x1YWMwNFx1YzczY1x1Yjg1YyBcdWJjZmMgXHVjMjE4IFx1YzVjNlx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViYWE4XHViNGUwIFx1YWNiZFx1YWUzMFx1Yzc1OCBcdWMyZGNcdWM3OTEgXHVjMmRjXHVhYzA0XHVhY2ZjIFx1Yzg4NVx1YjhjYyBcdWMyZGNcdWFjMDQsIFx1YWRmOFx1YjlhY1x1YWNlMCBcdWIwYTBcdWM5ZGNcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWM3NzRcdWI1NGMsIFx1YzBjMVx1YWRmY1x1Yzc3NFx1YWMwMCBcdWJjZmMgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWFjYmRcdWFlMzBcdWM3NTggXHVjZDVjXHViMzAwIFx1YWMxY1x1YzIxOFx1Yjk3YyBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC4gXHVjMGMxXHVhZGZjXHVjNzc0XHViMjk0IFx1YWNiZFx1YWUzMFx1YzdhNVx1YzVkMCBcdWMyZGNcdWM3OTEgXHVjMmRjXHVhYzA0XHVjNWQwIFx1YjRlNFx1YzViNFx1YWMwMFx1YmE3MCwgXHVjODg1XHViOGNjIFx1YzJkY1x1YWMwNFx1YzVkMCBcdWIwOThcdWM2MjRcdWFjOGNcdWI0MWNcdWIyZTQuIFx1ZDU1YyBcdWFjYmRcdWFlMzBcdWI5N2MgXHViY2Y0XHViMzU4IFx1YzkxMVx1YzVkMCBcdWIyZTRcdWI5NzggXHVhY2JkXHVhZTMwXHViOTdjIFx1YmNmNFx1YWUzMCBcdWM3MDRcdWQ1NzQgXHVhY2JkXHVhZTMwXHVjN2E1XHVjNzQ0IFx1YzYyZVx1YWUzOCBcdWMyMTggXHVjNWM2XHViMmU0LiBcdWI2MTAsIFx1YWNiZFx1YWUzMFx1YzdhNVx1Yzc0NCBcdWM3NzRcdWIzZDlcdWQ1NThcdWIyOTRcdWIzNzAgXHVhYzc4XHViOWFjXHViMjk0IFx1YzJkY1x1YWMwNFx1Yzc0MCBcdWM1YzZcdWIyZTQuIFx1YjljOFx1YzljMFx1YjljOVx1YzczY1x1Yjg1YywgXHVhY2JkXHVhZTMwXHVhYzAwIFx1YzJkY1x1Yzc5MVx1YjQxYyBcdWM3NzRcdWQ2YzRcdWM1ZDBcdWIyOTQgXHVhY2JkXHVhZTMwXHVjN2E1XHVjNWQwIFx1YjRlNFx1YzViNFx1YWMwOCBcdWMyMTggXHVjNWM2XHViMmU0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjNzg1XHViODI1XHVjNzU4IFx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWFjMWNcdWMyMTggblx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVhY2JkXHVhZTMwXHVjNzU4IFx1YzIxOCAmbmJzcDsxICZsZTsgbSAmbGU7IDUwMDAwIFx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YjJlNFx1Yzc0YyBtXHVhYzFjIFx1YzkwNFx1YzVkMFx1YjI5NCBcdWFjMDEgXHVhY2JkXHVhZTMwXHVjNzU4IFx1YzgxNVx1YmNmNFx1Yjk3YyBcdWIwOThcdWQwYzBcdWIwYjRcdWIyOTQgXHVjMTM4IFx1YzgxNVx1YzIxOCBkLCBzLCBlXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gZFx1YjI5NCBcdWFjYmRcdWFlMzBcdWM3NTggXHViMGEwXHVjOWRjLCBzXHViMjk0IFx1YzJkY1x1Yzc5MSBcdWMyZGNcdWFjMDQsIGVcdWIyOTQgXHVjODg1XHViOGNjIFx1YzJkY1x1YWMwNFx1Yzc0NCBcdWIwOThcdWQwYzBcdWIwYjhcdWIyZTQuIFx1YzJkY1x1YWMwNFx1Yzc0MCBoaG1tXHVkNjE1XHVjMmRkXHVjNzNjXHViODVjIFx1YzhmY1x1YzViNFx1YzljMFx1YmE3MCwgXHViYWE4XHViNGUwIFx1YWNiZFx1YWUzMFx1YjI5NCBcdWMyZGNcdWM3OTFcdWQ1NWMgXHViMGEwXHVjNWQwIFx1YjA1ZFx1YjA5Y1x1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YjljOFx1YjJlNCAmcXVvdDtTY2VuYXJpbyAjaTomcXVvdDtcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBcdWM1ZWNcdWFlMzBcdWMxMWMgaVx1YjI5NCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0IFx1YmM4OFx1ZDYzOFx1Yzc3NFx1YmE3MCAxXHViZDgwXHVkMTMwIFx1YzJkY1x1Yzc5MVx1ZDU1Y1x1YjJlNC4gXHVhZGY4IFx1YjJlNFx1Yzc0YyBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVjMGMxXHVhZGZjXHVjNzc0XHVhYzAwIFx1Y2MzOFx1YzExZFx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMjk0IFx1YWNiZFx1YWUzMFx1Yzc1OCBcdWNkNWNcdWIzMDAgXHVhYzFjXHVjMjE4XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gXHViYjM4XHVjODFjXHVjNWQwXHVjMTFjXHViM2M0IFx1YzEyNFx1YmE4NVx1ZDU4OFx1YzljMFx1YjljYywgXHVhY2JkXHVhZTMwXHVjN2E1XHVjNzQ0IFx1Yzc3NFx1YjNkOVx1ZDU1OFx1YjI5NFx1YjM3MCBcdWFjNzhcdWI5YWNcdWIyOTQgXHVjMmRjXHVhYzA0XHVjNzQwIFx1YzVjNlx1YjJlNC4gXHVjOTg5LCBcdWFjYmRcdWFlMzAgQVx1Yzc1OCBcdWM4ODVcdWI4Y2MgXHVjMmRjXHVhYzA0XHVjNzc0IEJcdWM3NTggXHVjMmRjXHVjNzkxIFx1YzJkY1x1YWMwNFx1YWNmYyBcdWFjMTlcdWM3NDAgXHVhY2JkXHVjNmIwXHVjNWQwIFx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCBBIFx1Yzc3NFx1ZDZjNFx1YzVkMCBcdWJjMTRcdWI4NWMgQlx1Yjg1YyBcdWM3NzRcdWIzZDlcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTQgXHVjMGFjXHVjNzc0XHVjNWQwXHViMjk0IFx1YmU0OCBcdWM5MDRcdWM3NDQgXHVkNTU4XHViMDk4IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4ifSx7InByb2JsZW1faWQiOiI3NTA3IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiT2x5bXBpYyBHYW1lcyIsImRlc2NyaXB0aW9uIjoiPHA+TWlrZSBsb3ZlcyB0aGUgb2x5bXBpYyBnYW1lcy4gV2hhdCBoZSBoYXRlcyBhYm91dCBvbHltcGljIGdhbWVzICZuZGFzaDsgYmVzaWRlcyB0aGVtIHRha2luZyBwbGFjZSBvbmx5IG9uY2UgZXZlcnkgZm91ciB5ZWFycyAmbmRhc2g7IGlzIHRoYXQgdGhlIGluZGl2aWR1YWwgZXZlbnRzIGFyZSBzY2hlZHVsZWQgY29uY3VycmVudGx5LiBUaGF0IHdheSBpdCBpcyBuZXZlciBwb3NzaWJsZSB0byB3YXRjaCBhbGwgY29tcGV0aXRpb25zIGxpdmUuIE1pa2UgYWx3YXlzIHRyaWVzIHRvIHBsYW4gaGlzIHBlcnNvbmFsIHNjaGVkdWxlIGluIG9yZGVyIHRvIG1heGltaXplIHRoZSBudW1iZXIgb2YgZXZlbnRzIGhlIGNhbiBhdHRlbmQgdG8uIEhvd2V2ZXIsIGF0IHRoZSBlbmQgaGUgaXMgbmV2ZXIgc3VyZSB3aGV0aGVyIG9yIG5vdCBoaXMgc2NoZWR1bGUgYWN0dWFsbHkgaXMgb3B0aW1hbC4gSGVscCBoaW0hPFwvcD5cclxuXHJcbjxwPkdpdmVuIHRoZSBkYXlzIGFuZCB0aW1lcyBvbiB3aGljaCBldmVudHMgdGFrZSBwbGFjZSwgZGV0ZXJtaW5lIHRoZSBtYXhpbXVtIG51bWJlciBvZiBldmVudHMgTWlrZSBjYW4gd2F0Y2guIE1pa2UgbmV2ZXIgbGVhdmVzIGR1cmluZyBhbiBldmVudCwgc28gaXQgaXMgbm90IHBvc3NpYmxlIHRvIHBhcnRpYWxseSBhdHRlbmQgdG8gZXZlbnRzLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGlucHV0IHN0YXJ0cyB3aXRoIGEgbGluZSBjb250YWluaW5nIGEgc2luZ2xlIGludGVnZXIgbiwgdGhlIG51bWJlciBvZiB0ZXN0IGNhc2VzLiBFYWNoIHRlc3QgY2FzZSBzdGFydHMgd2l0aCBhIGxpbmUgY29udGFpbmluZyBhbiBpbnRlZ2VyIDEgJmxlOyBtICZsZTsgNTAwMDAgdGhhdCBzcGVjaWZpZXMgdGhlIG51bWJlciBvZiBkaWZmZXJlbnQgZXZlbnRzLiBUaGUgbmV4dCBtIGxpbmVzIGRlc2NyaWJlIG9uZSBldmVudCB3aXRoIHRocmVlIGludGVnZXJzIGQsIHMsIGUuIFRoZSBldmVudCB0YWtlcyBwbGFjZSBvbiBkYXkgZCBvZiB0aGUgb2x5bXBpY3MsIGl0IHN0YXJ0cyBhdCBzIGFuZCBpdCBlbmRzIGF0IGUsIHdoZXJlIHRoZSB0aW1lcyBhcmUgZ2l2ZW4gaW4gdGhlIGZvcm0gaGhtbS4gQWxsIGV2ZW50cyBhcmUgYXNzdW1lZCB0byBjb25jbHVkZSB0aGUgc2FtZSBkYXkgdGhleSBzdGFydGVkLjxcL3A+XHJcblxyXG48cD4mbmJzcDs8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5UaGUgb3V0cHV0IGZvciBldmVyeSB0ZXN0IGNhc2UgYmVnaW5zIHdpdGggYSBsaW5lIGNvbnRhaW5pbmcgJmxkcXVvO1NjZW5hcmlvICNpOiZyZHF1bzssIHdoZXJlIGkgaXMgdGhlIG51bWJlciBvZiB0aGUgdGVzdCBjYXNlIGNvdW50aW5nIGZyb20gMS4gVGhlbiwgb3V0cHV0IGEgc2luZ2xlIGxpbmUgY29udGFpbmluZyB0aGUgbnVtYmVyIG9mIGV2ZW50cyBNaWtlIGNhbiBhdHRlbmQgdG8gYXQgbW9zdC4gVGhlIHRpbWUgZm9yIGdldHRpbmcgZnJvbSBvbmUgZXZlbnQgdG8gYW5vdGhlciBjYW4gYmUgbmVnbGVjdGVkLiBFdmVudHMgc3RhcnRpbmcgYXQgdGltZSB0IGNhbiBiZSBzY2hlZHVsZWQgYWZ0ZXIgZXZlbnRzIGVuZGluZyBhdCB0IGFzIGxvbmcgYXMgdGhlcmUgYXJlIG5vIG90aGVyIGNvbmZsaWN0cy4gVGVybWluYXRlIGVhY2ggdGVzdCBjYXNlIHdpdGggYW4gZW1wdHkgbGluZS48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIn1d

출처

University > Tu-Darmstadt Programming Contest > TUD Contest 2008 5번

  • 잘못된 데이터를 찾은 사람: 3587jjh
  • 문제를 번역한 사람: baekjoon