문제
당신이 한 버스 정거장에 아침 9시에 도착했다. 그리고 9시부터 9시 59분까지 그 곳에 있었다. 그 동안 노선이 다른 여러 버스들이 이 정거장에 섰는데, 당신은 그 버스들이 도착하는 시각을 주의 깊게 관찰하였다.
노선이 같은 버스는 9시 정각부터 9분까지 같은 시간 간격으로 규칙성 있게 도착한다. 버스를 관찰한 시간은 0부터 59분까지이다. 각 노선을 달리는 버스는 그 동안 적어도 두 번은 정거장에 서며, 시간은 정수 시간만을 계산한다. (최소 단위는 1분)
노선이 다르더라도 어떤 버스 노선의 시간 스케줄은 최초 도착 시간이나 시간 간격 중 하나 이상이 다른 노선의 스케줄과 일치할 수 있다. 그런 이유로, 같은 시각에 노선이 다른 버스가 두 대 이상 도착하면 그 시각은 온 버스 수만큼 중복 기록한다. 즉, 만약 최초 도착 시간과 오는 간격이 완전히 같은 두 노선이 있더라도 그 노선을 다니는 버스들이 온 시각은 구분되어 따로 입력 파일에 기록된다는 뜻이다.
버스가 도착한 시간 기록을 입력 받아서 이 간격대로 있을 수 있는 서로 다른 버스 노선들을 구해 이들의 시간 스케줄을 출력하는 프로그램을 작성하라. 그리고 찾아낸 버스 노선마다 그 노선의 첫 도착 시간과 다음 간격을 출력하라. 그러한 경우가 많다면, 버스 노선의 수가 가장 적은 경우를 찾아야 한다. (버스의 수는 25를 넘지 않는다)
출력
첫째 줄에 버스 노선의 최소 개수 X를 출력한다. 다음 X개의 줄에는 각 노선의 첫 도착 시각과 간격을 출력한다. 최적해가 여러 개인 경우에는 임의의 하나만 출력하면 되며, 출력 순서는 상관이 없다.
예제 출력 1
복사
3
0 13
3 12
5 8
힌트
0 13 ← 0 . . 13 . . 26 . . . 39 . . 52 . (5번)
3 12 ← . 3 . . 15 . . 27 . . 39 . 51 . . (5번)
5 8 ← . . 5 13 . 21 . . 29 37 . 45 . . 53 (7번)
W3sicHJvYmxlbV9pZCI6IjE5NzMiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWJjODRcdWMyYTQgXHViMTc4XHVjMTIwIiwiZGVzY3JpcHRpb24iOiI8cD5cdWIyZjlcdWMyZTBcdWM3NzQgXHVkNTVjIFx1YmM4NFx1YzJhNCBcdWM4MTVcdWFjNzBcdWM3YTVcdWM1ZDAgXHVjNTQ0XHVjZTY4IDlcdWMyZGNcdWM1ZDAgXHViM2M0XHVjYzI5XHVkNTg4XHViMmU0LiBcdWFkZjhcdWI5YWNcdWFjZTAgOVx1YzJkY1x1YmQ4MFx1ZDEzMCA5XHVjMmRjIDU5XHViZDg0XHVhZTRjXHVjOWMwIFx1YWRmOCBcdWFjZjNcdWM1ZDAgXHVjNzg4XHVjNWM4XHViMmU0LiBcdWFkZjggXHViM2Q5XHVjNTQ4IFx1YjE3OFx1YzEyMFx1Yzc3NCBcdWIyZTRcdWI5NzggXHVjNWVjXHViN2VjIFx1YmM4NFx1YzJhNFx1YjRlNFx1Yzc3NCBcdWM3NzQgXHVjODE1XHVhYzcwXHVjN2E1XHVjNWQwIFx1YzEzMFx1YjI5NFx1YjM3MCwgXHViMmY5XHVjMmUwXHVjNzQwIFx1YWRmOCBcdWJjODRcdWMyYTRcdWI0ZTRcdWM3NzQgXHViM2M0XHVjYzI5XHVkNTU4XHViMjk0IFx1YzJkY1x1YWMwMVx1Yzc0NCBcdWM4ZmNcdWM3NTggXHVhZTRhXHVhYzhjIFx1YWQwMFx1Y2MzMFx1ZDU1OFx1YzYwMFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViMTc4XHVjMTIwXHVjNzc0IFx1YWMxOVx1Yzc0MCBcdWJjODRcdWMyYTRcdWIyOTQgOVx1YzJkYyBcdWM4MTVcdWFjMDFcdWJkODBcdWQxMzAgOVx1YmQ4NFx1YWU0Y1x1YzljMCBcdWFjMTlcdWM3NDAgXHVjMmRjXHVhYzA0IFx1YWMwNFx1YWNhOVx1YzczY1x1Yjg1YyBcdWFkZGNcdWNlNTlcdWMxMzEgXHVjNzg4XHVhYzhjIFx1YjNjNFx1Y2MyOVx1ZDU1Y1x1YjJlNC4gXHViYzg0XHVjMmE0XHViOTdjIFx1YWQwMFx1Y2MzMFx1ZDU1YyBcdWMyZGNcdWFjMDRcdWM3NDAgMFx1YmQ4MFx1ZDEzMCA1OVx1YmQ4NFx1YWU0Y1x1YzljMFx1Yzc3NFx1YjJlNC4gXHVhYzAxIFx1YjE3OFx1YzEyMFx1Yzc0NCBcdWIyZWNcdWI5YWNcdWIyOTQgXHViYzg0XHVjMmE0XHViMjk0IFx1YWRmOCBcdWIzZDlcdWM1NDggXHVjODAxXHVjNWI0XHViM2M0IFx1YjQ1MCBcdWJjODhcdWM3NDAgXHVjODE1XHVhYzcwXHVjN2E1XHVjNWQwIFx1YzExY1x1YmE3MCwgXHVjMmRjXHVhYzA0XHVjNzQwIFx1YzgxNVx1YzIxOCBcdWMyZGNcdWFjMDRcdWI5Y2NcdWM3NDQgXHVhY2M0XHVjMGIwXHVkNTVjXHViMmU0LiAoXHVjZDVjXHVjMThjIFx1YjJlOFx1YzcwNFx1YjI5NCAxXHViZDg0KTxcL3A+XHJcblxyXG48cD5cdWIxNzhcdWMxMjBcdWM3NzQgXHViMmU0XHViOTc0XHViMzU0XHViNzdjXHViM2M0IFx1YzViNFx1YjVhNCBcdWJjODRcdWMyYTQgXHViMTc4XHVjMTIwXHVjNzU4IFx1YzJkY1x1YWMwNCBcdWMyYTRcdWNmMDBcdWM5MDRcdWM3NDAgXHVjZDVjXHVjZDA4IFx1YjNjNFx1Y2MyOSBcdWMyZGNcdWFjMDRcdWM3NzRcdWIwOTggXHVjMmRjXHVhYzA0IFx1YWMwNFx1YWNhOSBcdWM5MTEgXHVkNTU4XHViMDk4IFx1Yzc3NFx1YzBjMVx1Yzc3NCBcdWIyZTRcdWI5NzggXHViMTc4XHVjMTIwXHVjNzU4IFx1YzJhNFx1Y2YwMFx1YzkwNFx1YWNmYyBcdWM3N2NcdWNlNThcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHVhZGY4XHViN2YwIFx1Yzc3NFx1YzcyMFx1Yjg1YywgXHVhYzE5XHVjNzQwIFx1YzJkY1x1YWMwMVx1YzVkMCBcdWIxNzhcdWMxMjBcdWM3NzQgXHViMmU0XHViOTc4IFx1YmM4NFx1YzJhNFx1YWMwMCBcdWI0NTAgXHViMzAwIFx1Yzc3NFx1YzBjMSBcdWIzYzRcdWNjMjlcdWQ1NThcdWJhNzQgXHVhZGY4IFx1YzJkY1x1YWMwMVx1Yzc0MCBcdWM2MjggXHViYzg0XHVjMmE0IFx1YzIxOFx1YjljY1x1ZDA3YyBcdWM5MTFcdWJjZjUgXHVhZTMwXHViODVkXHVkNTVjXHViMmU0LiBcdWM5ODksIFx1YjljY1x1YzU3ZCBcdWNkNWNcdWNkMDggXHViM2M0XHVjYzI5IFx1YzJkY1x1YWMwNFx1YWNmYyBcdWM2MjRcdWIyOTQgXHVhYzA0XHVhY2E5XHVjNzc0IFx1YzY0NFx1YzgwNFx1ZDc4OCBcdWFjMTlcdWM3NDAgXHViNDUwIFx1YjE3OFx1YzEyMFx1Yzc3NCBcdWM3ODhcdWIzNTRcdWI3N2NcdWIzYzQgXHVhZGY4IFx1YjE3OFx1YzEyMFx1Yzc0NCBcdWIyZTRcdWIyYzhcdWIyOTQgXHViYzg0XHVjMmE0XHViNGU0XHVjNzc0IFx1YzYyOCBcdWMyZGNcdWFjMDFcdWM3NDAgXHVhZDZjXHViZDg0XHViNDE4XHVjNWI0IFx1YjUzMFx1Yjg1YyBcdWM3ODVcdWI4MjUgXHVkMzBjXHVjNzdjXHVjNWQwIFx1YWUzMFx1Yjg1ZFx1YjQxY1x1YjJlNFx1YjI5NCBcdWI3M2JcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YmM4NFx1YzJhNFx1YWMwMCBcdWIzYzRcdWNjMjlcdWQ1NWMgXHVjMmRjXHVhYzA0IFx1YWUzMFx1Yjg1ZFx1Yzc0NCBcdWM3ODVcdWI4MjUgXHViYzFiXHVjNTQ0XHVjMTFjIFx1Yzc3NCBcdWFjMDRcdWFjYTlcdWIzMDBcdWI4NWMgXHVjNzg4XHVjNzQ0IFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVjMTFjXHViODVjIFx1YjJlNFx1Yjk3OCBcdWJjODRcdWMyYTQgXHViMTc4XHVjMTIwXHViNGU0XHVjNzQ0IFx1YWQ2Y1x1ZDU3NCBcdWM3NzRcdWI0ZTRcdWM3NTggXHVjMmRjXHVhYzA0IFx1YzJhNFx1Y2YwMFx1YzkwNFx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1Yjc3Yy4gXHVhZGY4XHViOWFjXHVhY2UwIFx1Y2MzZVx1YzU0NFx1YjBiOCBcdWJjODRcdWMyYTQgXHViMTc4XHVjMTIwXHViOWM4XHViMmU0IFx1YWRmOCBcdWIxNzhcdWMxMjBcdWM3NTggXHVjY2FiIFx1YjNjNFx1Y2MyOSBcdWMyZGNcdWFjMDRcdWFjZmMgXHViMmU0XHVjNzRjIFx1YWMwNFx1YWNhOVx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NThcdWI3N2MuIFx1YWRmOFx1YjdlY1x1ZDU1YyBcdWFjYmRcdWM2YjBcdWFjMDAgXHViOWNlXHViMmU0XHViYTc0LCBcdWJjODRcdWMyYTQgXHViMTc4XHVjMTIwXHVjNzU4IFx1YzIxOFx1YWMwMCBcdWFjMDBcdWM3YTUgXHVjODAxXHVjNzQwIFx1YWNiZFx1YzZiMFx1Yjk3YyBcdWNjM2VcdWM1NDRcdWM1N2MgXHVkNTVjXHViMmU0LiAoXHViYzg0XHVjMmE0XHVjNzU4IFx1YzIxOFx1YjI5NCAyNVx1Yjk3YyBcdWIxMThcdWM5YzAgXHVjNTRhXHViMjk0XHViMmU0KTxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWJjODRcdWMyYTRcdWFjMDAgXHVjMTIwIFx1ZDY5Zlx1YzIxOCBuKDImbGU7biZsZTszMDApXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHViMmU0XHVjNzRjIFx1YzkwNFx1YzVkMFx1YjI5NCBcdWJjODRcdWMyYTRcdWFjMDAgXHVjNjI4IFx1YzJkY1x1YWMwMSBuXHVhYzFjXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVhYzAxXHVhYzAxXHVjNzU4IFx1YzJkY1x1YWMwMVx1Yzc0MCBcdWM4MTVcdWMyMThcdWI3N2MgXHVhYzAwXHVjODE1XHVkNTU4XHVjNzkwLiBcdWMyZGNcdWFjMDFcdWM3NDAgXHViZDg0IFx1YjJlOFx1YzcwNFx1YjljYyBcdWFlMzBcdWI4NWRcdWQ1NThcdWJhNzAsIDBcdWM3NzRcdWMwYzEgNTlcdWM3NzRcdWQ1NThcdWM3NTggXHVhYzEyXHVjNzQ0IFx1YWMxNlx1YjI5NFx1YjJlNC4gXHVjNzg1XHViODI1XHVjNzU4IFx1YzkxMVx1YWMwNFx1YzVkMFx1YjI5NCBcdWFjZjVcdWJjMzEgXHViMzAwXHVjMmUwIFx1YzVkNFx1ZDEzMFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzggXHVjMjE4XHViM2M0IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YmM4NFx1YzJhNCBcdWIxNzhcdWMxMjBcdWM3NTggXHVjZDVjXHVjMThjIFx1YWMxY1x1YzIxOCBYXHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gXHViMmU0XHVjNzRjIFhcdWFjMWNcdWM3NTggXHVjOTA0XHVjNWQwXHViMjk0IFx1YWMwMSBcdWIxNzhcdWMxMjBcdWM3NTggXHVjY2FiIFx1YjNjNFx1Y2MyOSBcdWMyZGNcdWFjMDFcdWFjZmMgXHVhYzA0XHVhY2E5XHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gXHVjZDVjXHVjODAxXHVkNTc0XHVhYzAwIFx1YzVlY1x1YjdlYyBcdWFjMWNcdWM3NzggXHVhY2JkXHVjNmIwXHVjNWQwXHViMjk0IFx1Yzc4NFx1Yzc1OFx1Yzc1OCBcdWQ1NThcdWIwOThcdWI5Y2MgXHVjZDljXHViODI1XHVkNTU4XHViYTc0IFx1YjQxOFx1YmE3MCwgXHVjZDljXHViODI1IFx1YzIxY1x1YzExY1x1YjI5NCBcdWMwYzFcdWFkMDBcdWM3NzQgXHVjNWM2XHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiI8cHJlPlxyXG4wIDEzICAgICZsYXJyOyAwIC4gLiAxMyAgLiAgLiAyNiAgLiAgLiAgLiAzOSAgLiAgLiA1MiAgLiAoNVx1YmM4OClcclxuMyAxMiAgICAmbGFycjsgLiAzIC4gIC4gMTUgIC4gIC4gMjcgIC4gIC4gMzkgIC4gNTEgIC4gIC4gKDVcdWJjODgpXHJcbjUgOCAgICAgJmxhcnI7IC4gLiA1IDEzICAuIDIxICAuICAuIDI5IDM3ICAuIDQ1ICAuICAuIDUzICg3XHViYzg4KTxcL3ByZT5cclxuIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIxOTczIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiVGhlIEJ1c2VzIiwiZGVzY3JpcHRpb24iOiI8cD5BIG1hbiBhcnJpdmVzIGF0IGEgYnVzIHN0b3AgYXQgMTI6MDAuIEhlIHJlbWFpbnMgdGhlcmUgZHVyaW5nIDEyOjAwLTEyOjU5LiBUaGUgYnVzIHN0b3AgaXMgdXNlZCBieSBhIG51bWJlciBvZiBidXMgcm91dGVzLiBUaGUgbWFuIG5vdGVzIHRoZSB0aW1lcyBvZiBhcnJpdmluZyBidXNlcy4gVGhlIHRpbWVzIHdoZW4gYnVzZXMgYXJyaXZlIGFyZSBnaXZlbi48XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5CdXNlcyBvbiB0aGUgc2FtZSByb3V0ZSBhcnJpdmUgYXQgcmVndWxhciBpbnRlcnZhbHMgZnJvbSAxMjowMCB0byAxMjo1OSB0aHJvdWdob3V0IHRoZSBlbnRpcmUgaG91ci48XC9saT5cclxuXHQ8bGk+VGltZXMgYXJlIGdpdmVuIGluIHdob2xlIG1pbnV0ZXMgZnJvbSAwIHRvIDU5LjxcL2xpPlxyXG5cdDxsaT5FYWNoIGJ1cyByb3V0ZSBzdG9wcyBhdCBsZWFzdCAyIHRpbWVzLjxcL2xpPlxyXG5cdDxsaT5UaGUgbnVtYmVyIG9mIGJ1cyByb3V0ZXMgaW4gdGhlIHRlc3QgZXhhbXBsZXMgd2lsbCBiZSAmbHQ7PTE3LjxcL2xpPlxyXG5cdDxsaT5CdXNlcyBmcm9tIGRpZmZlcmVudCByb3V0ZXMgbWF5IGFycml2ZSBhdCB0aGUgc2FtZSB0aW1lLjxcL2xpPlxyXG5cdDxsaT5TZXZlcmFsIGJ1cyByb3V0ZXMgY2FuIGhhdmUgdGhlIHNhbWUgdGltZSBvZiBmaXJzdCBhcnJpdmFsIGFuZFwvb3IgdGltZSBpbnRlcnZhbC4gSWYgdHdvIGJ1cyByb3V0ZXMgaGF2ZSB0aGUgc2FtZSBzdGFydGluZyB0aW1lIGFuZCBpbnRlcnZhbCwgdGhleSBhcmUgZGlzdGluY3QgYW5kIGFyZSBib3RoIHRvIGJlIHByZXNlbnRlZC48XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD5GaW5kIHRoZSBzY2hlZHVsZSB3aXRoIHRoZSBmZXdlc3QgbnVtYmVyIG9mIGJ1cyByb3V0ZXMgdGhhdCBtdXN0IHN0b3AgYXQgdGhlIGJ1cyBzdG9wIHRvIHNhdGlzZnkgdGhlIGlucHV0IGRhdGEuIEZvciBlYWNoIGJ1cyByb3V0ZSwgb3V0cHV0IHRoZSBzdGFydGluZyB0aW1lIGFuZCB0aGUgaW50ZXJ2YWwuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgaW5wdXQgY29udGFpbnMgYSBudW1iZXIgbiAobiZsdDs9MzAwKSB0ZWxsaW5nIGhvdyBtYW55IGFycml2aW5nIGJ1c2VzIGhhdmUgYmVlbiBub3RlZCwgZm9sbG93ZWQgYnkgdGhlIGFycml2YWwgdGltZXMgaW4gYXNjZW5kaW5nIG9yZGVyLjxcL3A+XHJcblxyXG48cD4mbmJzcDs8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Xcml0ZSBhIHRhYmxlIHRvIHRoZSBvdXRwdXQgd2l0aCBvbmUgbGluZSBmb3IgZWFjaCBidXMgcm91dGUuIEVhY2ggbGluZSBpbiB0aGUgZmlsZSBnaXZlcyB0aGUgdGltZSBvZiBhcnJpdmFsIGZvciB0aGUgZmlyc3QgYnVzIGFuZCB0aGUgdGltZSBpbnRlcnZhbCBpbiBtaW51dGVzLiBUaGUgb3JkZXIgb2YgdGhlIGJ1cyByb3V0ZXMgZG9lcyBub3QgbWF0dGVyLiBJZiB0aGVyZSBhcmUgc2V2ZXJhbCBzb2x1dGlvbnMsIG9ubHkgb25lIGlzIHJlcXVpcmVkLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==
