시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 128 MB76627.143%

문제

당신이 한 버스 정거장에 아침 9시에 도착했다. 그리고 9시부터 9시 59분까지 그 곳에 있었다. 그 동안 노선이 다른 여러 버스들이 이 정거장에 섰는데, 당신은 그 버스들이 도착하는 시각을 주의 깊게 관찰하였다.

노선이 같은 버스는 9시 정각부터 9분까지 같은 시간 간격으로 규칙성 있게 도착한다. 버스를 관찰한 시간은 0부터 59분까지이다. 각 노선을 달리는 버스는 그 동안 적어도 두 번은 정거장에 서며, 시간은 정수 시간만을 계산한다. (최소 단위는 1분)

노선이 다르더라도 어떤 버스 노선의 시간 스케줄은 최초 도착 시간이나 시간 간격 중 하나 이상이 다른 노선의 스케줄과 일치할 수 있다. 그런 이유로, 같은 시각에 노선이 다른 버스가 두 대 이상 도착하면 그 시각은 온 버스 수만큼 중복 기록한다. 즉, 만약 최초 도착 시간과 오는 간격이 완전히 같은 두 노선이 있더라도 그 노선을 다니는 버스들이 온 시각은 구분되어 따로 입력 파일에 기록된다는 뜻이다.

버스가 도착한 시간 기록을 입력 받아서 이 간격대로 있을 수 있는 서로 다른 버스 노선들을 구해 이들의 시간 스케줄을 출력하는 프로그램을 작성하라. 그리고 찾아낸 버스 노선마다 그 노선의 첫 도착 시간과 다음 간격을 출력하라. 그러한 경우가 많다면, 버스 노선의 수가 가장 적은 경우를 찾아야 한다. (버스의 수는 25를 넘지 않는다)

입력

첫째 줄에 버스가 선 횟수 n(2 ≤ n ≤ 300)이 주어진다. 다음 줄에는 버스가 온 시각 n개가 주어진다. 각각의 시각은 정수라 가정하자. 시각은 분 단위만 기록하며, 0이상 59이하의 값을 갖는다. 입력의 중간에는 공백 대신 엔터가 주어질 수도 있다.

출력

첫째 줄에 버스 노선의 최소 개수 X를 출력한다. 다음 X개의 줄에는 각 노선의 첫 도착 시각과 간격을 출력한다. 최적해가 여러 개인 경우에는 임의의 하나만 출력하면 되며, 출력 순서는 상관이 없다.

예제 입력 1

17
0 3 5 13 13 15
21 26 27 29
37 39 39 45 51 52 53

예제 출력 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+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWJjODRcdWMyYTRcdWFjMDAgXHVjMTIwIFx1ZDY5Zlx1YzIxOCBuKDIgJmxlOyBuICZsZTsgMzAwKVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YjJlNFx1Yzc0YyBcdWM5MDRcdWM1ZDBcdWIyOTQgXHViYzg0XHVjMmE0XHVhYzAwIFx1YzYyOCBcdWMyZGNcdWFjMDEgblx1YWMxY1x1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YWMwMVx1YWMwMVx1Yzc1OCBcdWMyZGNcdWFjMDFcdWM3NDAgXHVjODE1XHVjMjE4XHViNzdjIFx1YWMwMFx1YzgxNVx1ZDU1OFx1Yzc5MC4gXHVjMmRjXHVhYzAxXHVjNzQwIFx1YmQ4NCBcdWIyZThcdWM3MDRcdWI5Y2MgXHVhZTMwXHViODVkXHVkNTU4XHViYTcwLCAwXHVjNzc0XHVjMGMxIDU5XHVjNzc0XHVkNTU4XHVjNzU4IFx1YWMxMlx1Yzc0NCBcdWFjMTZcdWIyOTRcdWIyZTQuIFx1Yzc4NVx1YjgyNVx1Yzc1OCBcdWM5MTFcdWFjMDRcdWM1ZDBcdWIyOTQgXHVhY2Y1XHViYzMxIFx1YjMwMFx1YzJlMCBcdWM1ZDRcdWQxMzBcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM4IFx1YzIxOFx1YjNjNCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWJjODRcdWMyYTQgXHViMTc4XHVjMTIwXHVjNzU4IFx1Y2Q1Y1x1YzE4YyBcdWFjMWNcdWMyMTggWFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIFx1YjJlNFx1Yzc0YyBYXHVhYzFjXHVjNzU4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWFjMDEgXHViMTc4XHVjMTIwXHVjNzU4IFx1Y2NhYiBcdWIzYzRcdWNjMjkgXHVjMmRjXHVhYzAxXHVhY2ZjIFx1YWMwNFx1YWNhOVx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIFx1Y2Q1Y1x1YzgwMVx1ZDU3NFx1YWMwMCBcdWM1ZWNcdWI3ZWMgXHVhYzFjXHVjNzc4IFx1YWNiZFx1YzZiMFx1YzVkMFx1YjI5NCBcdWM3ODRcdWM3NThcdWM3NTggXHVkNTU4XHViMDk4XHViOWNjIFx1Y2Q5Y1x1YjgyNVx1ZDU1OFx1YmE3NCBcdWI0MThcdWJhNzAsIFx1Y2Q5Y1x1YjgyNSBcdWMyMWNcdWMxMWNcdWIyOTQgXHVjMGMxXHVhZDAwXHVjNzc0IFx1YzVjNlx1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiPHByZT5cclxuMCAxMyAgICAmbGFycjsgMCAuIC4gMTMgIC4gIC4gMjYgIC4gIC4gIC4gMzkgIC4gIC4gNTIgIC4gKDVcdWJjODgpXHJcbjMgMTIgICAgJmxhcnI7IC4gMyAuICAuIDE1ICAuICAuIDI3ICAuICAuIDM5ICAuIDUxICAuICAuICg1XHViYzg4KVxyXG41IDggICAgICZsYXJyOyAuIC4gNSAxMyAgLiAyMSAgLiAgLiAyOSAzNyAgLiA0NSAgLiAgLiA1MyAoN1x1YmM4OCk8XC9wcmU+XHJcbiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIn0seyJwcm9ibGVtX2lkIjoiMTk3MyIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IlRoZSBCdXNlcyIsImRlc2NyaXB0aW9uIjoiPHA+QSBtYW4gYXJyaXZlcyBhdCBhIGJ1cyBzdG9wIGF0IDEyOjAwLiBIZSByZW1haW5zIHRoZXJlIGR1cmluZyAxMjowMC0xMjo1OS4gVGhlIGJ1cyBzdG9wIGlzIHVzZWQgYnkgYSBudW1iZXIgb2YgYnVzIHJvdXRlcy4gVGhlIG1hbiBub3RlcyB0aGUgdGltZXMgb2YgYXJyaXZpbmcgYnVzZXMuIFRoZSB0aW1lcyB3aGVuIGJ1c2VzIGFycml2ZSBhcmUgZ2l2ZW4uPFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+QnVzZXMgb24gdGhlIHNhbWUgcm91dGUgYXJyaXZlIGF0IHJlZ3VsYXIgaW50ZXJ2YWxzIGZyb20gMTI6MDAgdG8gMTI6NTkgdGhyb3VnaG91dCB0aGUgZW50aXJlIGhvdXIuPFwvbGk+XHJcblx0PGxpPlRpbWVzIGFyZSBnaXZlbiBpbiB3aG9sZSBtaW51dGVzIGZyb20gMCB0byA1OS48XC9saT5cclxuXHQ8bGk+RWFjaCBidXMgcm91dGUgc3RvcHMgYXQgbGVhc3QgMiB0aW1lcy48XC9saT5cclxuXHQ8bGk+VGhlIG51bWJlciBvZiBidXMgcm91dGVzIGluIHRoZSB0ZXN0IGV4YW1wbGVzIHdpbGwgYmUgJmx0Oz0xNy48XC9saT5cclxuXHQ8bGk+QnVzZXMgZnJvbSBkaWZmZXJlbnQgcm91dGVzIG1heSBhcnJpdmUgYXQgdGhlIHNhbWUgdGltZS48XC9saT5cclxuXHQ8bGk+U2V2ZXJhbCBidXMgcm91dGVzIGNhbiBoYXZlIHRoZSBzYW1lIHRpbWUgb2YgZmlyc3QgYXJyaXZhbCBhbmRcL29yIHRpbWUgaW50ZXJ2YWwuIElmIHR3byBidXMgcm91dGVzIGhhdmUgdGhlIHNhbWUgc3RhcnRpbmcgdGltZSBhbmQgaW50ZXJ2YWwsIHRoZXkgYXJlIGRpc3RpbmN0IGFuZCBhcmUgYm90aCB0byBiZSBwcmVzZW50ZWQuPFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+RmluZCB0aGUgc2NoZWR1bGUgd2l0aCB0aGUgZmV3ZXN0IG51bWJlciBvZiBidXMgcm91dGVzIHRoYXQgbXVzdCBzdG9wIGF0IHRoZSBidXMgc3RvcCB0byBzYXRpc2Z5IHRoZSBpbnB1dCBkYXRhLiBGb3IgZWFjaCBidXMgcm91dGUsIG91dHB1dCB0aGUgc3RhcnRpbmcgdGltZSBhbmQgdGhlIGludGVydmFsLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGlucHV0IGNvbnRhaW5zIGEgbnVtYmVyIG4gKG4mbHQ7PTMwMCkgdGVsbGluZyBob3cgbWFueSBhcnJpdmluZyBidXNlcyBoYXZlIGJlZW4gbm90ZWQsIGZvbGxvd2VkIGJ5IHRoZSBhcnJpdmFsIHRpbWVzIGluIGFzY2VuZGluZyBvcmRlci48XC9wPlxyXG5cclxuPHA+Jm5ic3A7PFwvcD5cclxuIiwib3V0cHV0IjoiPHA+V3JpdGUgYSB0YWJsZSB0byB0aGUgb3V0cHV0IHdpdGggb25lIGxpbmUgZm9yIGVhY2ggYnVzIHJvdXRlLiBFYWNoIGxpbmUgaW4gdGhlIGZpbGUgZ2l2ZXMgdGhlIHRpbWUgb2YgYXJyaXZhbCBmb3IgdGhlIGZpcnN0IGJ1cyBhbmQgdGhlIHRpbWUgaW50ZXJ2YWwgaW4gbWludXRlcy4gVGhlIG9yZGVyIG9mIHRoZSBidXMgcm91dGVzIGRvZXMgbm90IG1hdHRlci4gSWYgdGhlcmUgYXJlIHNldmVyYWwgc29sdXRpb25zLCBvbmx5IG9uZSBpcyByZXF1aXJlZC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIn1d

출처

Olympiad > International Olympiad in Informatics > IOI 1994 > Day 2 5번