Đàn kiến
Có một đàn kiến đang đứng trên 1 khúc gỗ có chiều dài D. Tọa độ của con kiến thứ \(i\) trên khúc gỗ là \(A[i]\). Con kiến sẽ bị rơi nếu nó đi tới đầu khúc gỗ hoặc cuối khúc gỗ. Biết rằng các con kiến di chuyển liên tục và có thể đi theo các hướng tùy ý, nếu 2 con kiến đi ngược hướng với nhau và gặp nhau thì chúng sẽ quay đầu và đi theo hướng ngược lại. Mỗi 1 giây những con kiến di chuyển được 1 đơn vị độ dài. Hỏi thời gian nhanh nhất và lâu nhất để con kiến đầu tiên và cuối cùng rơi xuống là bao lâu.
Input
- Dòng đầu chứa số nguyên \(T\) là số bộ test (\( 1 <= \)T\( <= 100\))
- Dòng thứ 2 là số nguyên \(D\) là chiều dài của khúc gỗ (\(1 <= D <= 10000000000\))
- Dòng thứ 3 là số nguyên \(N\) là số con kiến trên khúc gỗ (\(1 <= N <= 1000\))
- Dòng thứ 4 chứa \(N\) số nguyên, số thứ \(i\) là tọa độ của con kiến thứ \(i\) trên khúc gỗ (0 <= \(A[i] <= D\))
- Nếu có nhiều hơn 1 bộ test thì tiếp tục đọc giống dòng thứ 2 trở đi. Nhìn input và output để hiểu rõ hơn
Output
- Ứng với mỗi test case in ra thời gian lâu nhất có thể mà con kiến cuối cùng và con kiến đầu tiên sẽ rơi khỏi thanh gỗ
Example
Input
2 7 2 2 4 10 3 1 2 3
Output
5 2 9 1
Giải thích
Với test 1 thì con kiến 4 và 2 sẽ đi hướng vào nhau và gặp nhau ở vị trí 3 sau đó hai con kiến sẽ quay đầu và một con đi tiếp từ 3 lên 7 và một con đi từ 3 về 0 dẫn tới thời gian để 2 con kiến rơi là 4 và 5. Trường hợp tiếp theo con kiến ở vị trí 2 có thể đi thẳng về 0 và rơi xuống nên thời gian rơi ngắn nhất lúc này sẽ là 2 (nhỏ hơn 4 so với trường hợp trên). Nên đáp án là 5 và 2
Comments
sol() : 2 con kiến đâm đầu vào nhau ? không có gì thay đổi cả !! vì sao ? Vì 2 con kiến không phân biệt !
Bài này khó khắn quá :vvv
ở 2 tọa độ liền sát nhau thì ta quy ước chúng đi như nào ví dụ ở vị trí 2 và 3 chúng đi hướng vào nhau thì ta cho nó quay đầu luôn à vậy thì có khác gì chúng hướng ra ngoài từ ban đầu. mong tác giả nói nốt bộ test 2
thì làm nhưu bình thường bạn cho nó đi kiểu gì thì đi cứ ra ngắn nhất và dài nhất là được