Đàn kiến

Submit solution
Points: 1 (partial)
Time limit: 1.0s
Memory limit: 10M
Author:
lqtuantk19
Problem type
Allowed languages
Ada, Assembly, Awk, C, C++, C11, CLANG, CLANGX, Classical, COBOL, Coffee, CSC, D lang, DART, F95, FORTH, Fortrn, GAS32, GO, Haskell, Itercal, Java, kotlin, LEAN, LISP, LUA, MONOVB, Nasm, OCAML, Pascal, Perl, php, PIKE, prolog, Pypy, Python, Ruby 2, RUST, Scala, SCM, SED, SWIFT, TCL, TUR, V8JS, VB, ZIG

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


  • 1
    No_Limit  commented on Jan. 9, 2023, 4:55 p.m.

    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 !


  • 0
    No_Limit  commented on Jan. 9, 2023, 4:54 p.m. ← edited

    Bài này khó khắn quá :vvv


  • 0
    Binh_CNTT2_K59  commented on Jan. 14, 2019, 7:20 a.m. ← edited

    ở 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


    • 0
      enoughtodie99  commented on Feb. 26, 2019, 1:18 a.m.

      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