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

문제

개미 여러 마리가 길이가 lcm인 막대 위에 있다. 각 개미의 이동 속도는 모두 일정하며, 1cm/s이다. 개미가 막대의 마지막까지 걸어간다면, 개미는 그 즉시 떨어지게 된다. 또, 두 개미가 만나게 된다면, 방향을 반대로 바꾸어 걸어가게 된다.

가장 처음에 막대 상에서 개미의 위치를 알고 있다. 하지만, 개미가 어느 방향으로 움직이는 지는 알 수가 없다. 이때, 모든 개미가 땅으로 떨어질 때까지 가능한 시간 중 가장 빠른 시간과 느린 시간을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스의 첫째 줄에는 막대의 길이와 개미의 수 n이 주어진다. 다음 n개 줄에는 숫자가 하나씩 주어지며, 이 숫자는 개미의 초기 위치를 나타낸다. 입력으로 주어지는 모든 수는 1,000,000보다 작거나 같으며, 공백으로 구분되어져 있다. 개미의 위치는 막대 왼쪽 끝에서부터 떨어진 거리이다.

출력

각 테스트 케이스에 대해서, 두 숫자를 출력한다. 첫 번째 숫자는 개미가 모두 땅으로 떨어지는 가능한 시간 중 가장 빠른 시간, 두 번째 숫자는 가장 늦은 시간이다.

제한

  • 1 ≤ n ≤ 100000
  • 1 ≤ l ≤ 1000000
  • 개미의 위치는 정수
  • 0 ≤ 개미의 위치 ≤ l

예제 입력 1

2
10 3
2
6
7
214 7
11
12
7
13
176
23
191

예제 출력 1

4 8
38 207
W3sicHJvYmxlbV9pZCI6IjQzMDciLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWFjMWNcdWJiZjgiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YWMxY1x1YmJmOCBcdWM1ZWNcdWI3ZWMgXHViOWM4XHViOWFjXHVhYzAwIFx1YWUzOFx1Yzc3NFx1YWMwMCBsY21cdWM3NzggXHViOWM5XHViMzAwIFx1YzcwNFx1YzVkMCBcdWM3ODhcdWIyZTQuIFx1YWMwMSBcdWFjMWNcdWJiZjhcdWM3NTggXHVjNzc0XHViM2Q5IFx1YzE4ZFx1YjNjNFx1YjI5NCBcdWJhYThcdWI0NTAgXHVjNzdjXHVjODE1XHVkNTU4XHViYTcwLCAxY21cL3NcdWM3NzRcdWIyZTQuIFx1YWMxY1x1YmJmOFx1YWMwMCBcdWI5YzlcdWIzMDBcdWM3NTggXHViOWM4XHVjOWMwXHViOWM5XHVhZTRjXHVjOWMwIFx1YWM3OFx1YzViNFx1YWMwNFx1YjJlNFx1YmE3NCwgXHVhYzFjXHViYmY4XHViMjk0IFx1YWRmOCBcdWM5ODlcdWMyZGMgXHViNWE4XHVjNWI0XHVjOWMwXHVhYzhjIFx1YjQxY1x1YjJlNC4gXHViNjEwLCBcdWI0NTAgXHVhYzFjXHViYmY4XHVhYzAwIFx1YjljY1x1YjA5OFx1YWM4YyBcdWI0MWNcdWIyZTRcdWJhNzQsIFx1YmMyOVx1ZDVhNVx1Yzc0NCBcdWJjMThcdWIzMDBcdWI4NWMgXHViYzE0XHVhZmI4XHVjNWI0IFx1YWM3OFx1YzViNFx1YWMwMFx1YWM4YyBcdWI0MWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWMwMFx1YzdhNSBcdWNjOThcdWM3NGNcdWM1ZDAgXHViOWM5XHViMzAwIFx1YzBjMVx1YzVkMFx1YzExYyBcdWFjMWNcdWJiZjhcdWM3NTggXHVjNzA0XHVjZTU4XHViOTdjIFx1YzU0Y1x1YWNlMCBcdWM3ODhcdWIyZTQuIFx1ZDU1OFx1YzljMFx1YjljYywgXHVhYzFjXHViYmY4XHVhYzAwIFx1YzViNFx1YjI5MCBcdWJjMjlcdWQ1YTVcdWM3M2NcdWI4NWMgXHVjNmMwXHVjOWMxXHVjNzc0XHViMjk0IFx1YzljMFx1YjI5NCBcdWM1NGMgXHVjMjE4XHVhYzAwIFx1YzVjNlx1YjJlNC4gXHVjNzc0XHViNTRjLCBcdWJhYThcdWI0ZTAgXHVhYzFjXHViYmY4XHVhYzAwIFx1YjU0NVx1YzczY1x1Yjg1YyBcdWI1YThcdWM1YjRcdWM5YzggXHViNTRjXHVhZTRjXHVjOWMwIFx1YWMwMFx1YjJhNVx1ZDU1YyBcdWMyZGNcdWFjMDQgXHVjOTExIFx1YWMwMFx1YzdhNSBcdWJlNjBcdWI5NzggXHVjMmRjXHVhYzA0XHVhY2ZjIFx1YjI5MFx1YjliMCBcdWMyZGNcdWFjMDRcdWM3NDQgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVhYzFjXHVjMjE4XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWI5YzlcdWIzMDBcdWM3NTggXHVhZTM4XHVjNzc0XHVjNjQwIFx1YWMxY1x1YmJmOFx1Yzc1OCBcdWMyMTggblx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YjJlNFx1Yzc0YyBuXHVhYzFjIFx1YzkwNFx1YzVkMFx1YjI5NCBcdWMyMmJcdWM3OTBcdWFjMDAgXHVkNTU4XHViMDk4XHVjNTI5IFx1YzhmY1x1YzViNFx1YzljMFx1YmE3MCwgXHVjNzc0IFx1YzIyYlx1Yzc5MFx1YjI5NCBcdWFjMWNcdWJiZjhcdWM3NTggXHVjZDA4XHVhZTMwIFx1YzcwNFx1Y2U1OFx1Yjk3YyBcdWIwOThcdWQwYzBcdWIwYjhcdWIyZTQuIFx1Yzc4NVx1YjgyNVx1YzczY1x1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzBcdWIyOTQgXHViYWE4XHViNGUwIFx1YzIxOFx1YjI5NCZuYnNwOzEsMDAwLDAwMFx1YmNmNFx1YjJlNCBcdWM3OTFcdWFjNzBcdWIwOTggXHVhYzE5XHVjNzNjXHViYTcwLCBcdWFjZjVcdWJjMzFcdWM3M2NcdWI4NWMgXHVhZDZjXHViZDg0XHViNDE4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YjJlNC4gXHVhYzFjXHViYmY4XHVjNzU4IFx1YzcwNFx1Y2U1OFx1YjI5NCBcdWI5YzlcdWIzMDAgXHVjNjdjXHVjYWJkIFx1YjA1ZFx1YzVkMFx1YzExY1x1YmQ4MFx1ZDEzMCBcdWI1YThcdWM1YjRcdWM5YzQgXHVhYzcwXHViOWFjXHVjNzc0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNWQwIFx1YjMwMFx1ZDU3NFx1YzExYywgXHViNDUwIFx1YzIyYlx1Yzc5MFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIFx1Y2NhYiBcdWJjODhcdWM5ZjggXHVjMjJiXHVjNzkwXHViMjk0IFx1YWMxY1x1YmJmOFx1YWMwMCBcdWJhYThcdWI0NTAgXHViNTQ1XHVjNzNjXHViODVjIFx1YjVhOFx1YzViNFx1YzljMFx1YjI5NCBcdWFjMDBcdWIyYTVcdWQ1NWMgXHVjMmRjXHVhYzA0IFx1YzkxMSBcdWFjMDBcdWM3YTUgXHViZTYwXHViOTc4IFx1YzJkY1x1YWMwNCwgXHViNDUwIFx1YmM4OFx1YzlmOCBcdWMyMmJcdWM3OTBcdWIyOTQgXHVhYzAwXHVjN2E1IFx1YjJhNlx1Yzc0MCBcdWMyZGNcdWFjMDRcdWM3NzRcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIiwibGltaXQiOiI8dWw+XHJcblx0PGxpPjEgJmxlOyBuICZsZTsgMTAwMDAwPFwvbGk+XHJcblx0PGxpPjEgJmxlOyBsICZsZTsgMTAwMDAwMDxcL2xpPlxyXG5cdDxsaT5cdWFjMWNcdWJiZjhcdWM3NTggXHVjNzA0XHVjZTU4XHViMjk0IFx1YzgxNVx1YzIxODxcL2xpPlxyXG5cdDxsaT4wICZsZTsgXHVhYzFjXHViYmY4XHVjNzU4IFx1YzcwNFx1Y2U1OCAmbGU7IGw8XC9saT5cclxuPFwvdWw+XHJcbiJ9LHsicHJvYmxlbV9pZCI6IjQzMDciLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJBbnRzIiwiZGVzY3JpcHRpb24iOiI8cD5BbiBhcm15IG9mIGFudHMgd2FsayBvbiBhIGhvcml6b250YWwgcG9sZSBvZiBsZW5ndGggbCBjbSwgZWFjaCB3aXRoIGEgY29uc3RhbnQgc3BlZWQgb2YgMSBjbVwvcy4gV2hlbiBhIHdhbGtpbmcgYW50IHJlYWNoZXMgYW4gZW5kIG9mIHRoZSBwb2xlLCBpdCBpbW1lZGlhdGVsbHkgZmFsbHMgb2ZmIGl0LiBXaGVuIHR3byBhbnRzIG1lZXQgdGhleSB0dXJuIGJhY2sgYW5kIHN0YXJ0IHdhbGtpbmcgaW4gb3Bwb3NpdGUgZGlyZWN0aW9ucy4gV2Uga25vdyB0aGUgb3JpZ2luYWwgcG9zaXRpb25zIG9mIGFudHMgb24gdGhlIHBvbGUsIHVuZm9ydHVuYXRlbHksIHdlIGRvIG5vdCBrbm93IHRoZSBkaXJlY3Rpb25zIGluIHdoaWNoIHRoZSBhbnRzIGFyZSB3YWxraW5nLiBZb3VyIHRhc2sgaXMgdG8gY29tcHV0ZSB0aGUgZWFybGllc3QgYW5kIHRoZSBsYXRlc3QgcG9zc2libGUgdGltZXMgbmVlZGVkIGZvciBhbGwgYW50cyB0byBmYWxsIG9mZiB0aGUgcG9sZS48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIGlucHV0IGNvbnRhaW5zIG9uZSBpbnRlZ2VyIGdpdmluZyB0aGUgbnVtYmVyIG9mIGNhc2VzIHRoYXQgZm9sbG93LiBUaGUgZGF0YSBmb3IgZWFjaCBjYXNlIHN0YXJ0IHdpdGggdHdvIGludGVnZXIgbnVtYmVyczogdGhlIGxlbmd0aCBvZiB0aGUgcG9sZSAoaW4gY20pIGFuZCBuLCB0aGUgbnVtYmVyIG9mIGFudHMgcmVzaWRpbmcgb24gdGhlIHBvbGUuIFRoZXNlIHR3byBudW1iZXJzIGFyZSBmb2xsb3dlZCBieSBuIGludGVnZXJzIGdpdmluZyB0aGUgcG9zaXRpb24gb2YgZWFjaCBhbnQgb24gdGhlIHBvbGUgYXMgdGhlIGRpc3RhbmNlIG1lYXN1cmVkIGZyb20gdGhlIGxlZnQgZW5kIG9mIHRoZSBwb2xlLCBpbiBubyBwYXJ0aWN1bGFyIG9yZGVyLiBBbGwgaW5wdXQgaW50ZWdlcnMgYXJlIG5vdCBiaWdnZXIgdGhhbiAxMDAwMDAwIGFuZCB0aGV5IGFyZSBzZXBhcmF0ZWQgYnkgd2hpdGVzcGFjZS48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Gb3IgZWFjaCBjYXNlIG9mIGlucHV0LCBvdXRwdXQgdHdvIG51bWJlcnMgc2VwYXJhdGVkIGJ5IGEgc2luZ2xlIHNwYWNlLiBUaGUgZmlyc3QgbnVtYmVyIGlzIHRoZSBlYXJsaWVzdCBwb3NzaWJsZSB0aW1lIHdoZW4gYWxsIGFudHMgZmFsbCBvZmYgdGhlIHBvbGUgKGlmIHRoZSBkaXJlY3Rpb25zIG9mIHRoZWlyIHdhbGtzIGFyZSBjaG9zZW4gYXBwcm9wcmlhdGVseSkgYW5kIHRoZSBzZWNvbmQgbnVtYmVyIGlzIHRoZSBsYXRlc3QgcG9zc2libGUgc3VjaCB0aW1lLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2gifV0=

출처

Contest > Waterloo's local Programming Contests > 19 September, 2004 B번