2025 THT bảng B - Buổi 30

Dãy số \(a\) gồm \(n\) số nguyên \(a_{1}, a_{2}, \ldots, a_{n}\) được gọi là có thứ tự tăng dần nếu \(a_{1} \leq a_{2} \leq \ldots \leq a_{n}\). Với mỗi dãy tăng dần luôn tìm được giá trị \(t = a_{i + 1} - a_{i}\) \((1 \leq i \leq n - 1)\) thỏa mãn \(t \geq 0\).

Yêu cầu: Xác định xem dãy \(a\) gồm \(n\) phần tử có thứ tự tăng dần hay không. Trong trường hợp dãy đã tăng dần thì hãy tìm giá trị \(t = a_{i + 1} - a_{i}\) \((1 \leq i \leq n - 1)\) thỏa mãn \(t > 0\) và \(t\) nhỏ nhất.

Input

• Dòng đầu ghi số nguyên dương \(n\) \((1 \leq n \leq 10^{5})\) là số lượng phần tử của dãy \(a\).
• Dòng thứ hai ghi \(n\) số nguyên \(a_{1}, a_{2}, \ldots, a_{n}\) \((|a_{i}| \leq 10^{9})\) là các phần tử của dãy \(a\).

Output

• In ra một số nguyên theo quy ước sau đây:
  • In ra \(-1\) nếu dãy không có thứ tự tăng dần.
  • In ra \(0\) nếu dãy đã có thứ tự tăng dần nhưng không có giá trị \(t\) như yêu cầu.
  • In ra giá trị \(t\) theo yêu cầu nếu ngược lại hai trường hợp trên.

Example

7
1 1 2 2 4 6 8

1

5
6 6 6 6 6

0

6
1 8 9 2 3 4

-1

Tháp là một chồng gồm các đĩa đồng trục đặt lên nhau sao cho đĩa nhỏ luôn nằm trên đĩa lớn. Để có được hình dạng cân đối, đường kính các đĩa phải thỏa mãn một số ràng buộc cụ thể. Tháp được gọi là tháp ước số nếu mọi đĩa của tháp đều thỏa mãn ràng buộc: \textit{Đường kính các đĩa đều là số nguyên dương và đường kính đĩa ở trên là ước số của đường kính nằm ngay dưới nó.}

Tháp ước được gọi là tháp đầy đủ nếu không thể chèn được thêm đĩa vào giữa hai đĩa bất kỳ của tháp mà vẫn thỏa mãn tính chất tháp ước số. Như vậy, với mỗi cặp số nguyên dương \((a, b)\) mà \(a\) là ước của \(b\) thì một tháp đầy đủ của \((a, b)\) là một chồng đĩa mà đường kính của chúng là dãy số nguyên dương \(x_{0}, x_{1}, \ldots, x_{k}\) sao cho: \(x_{0} = a, x_{k} = b\); với \(i = 0, 1, 2, \ldots, k - 1\) thỏa mãn \(x_{i}\) là ước của \(x_{i + 1}\) đồng thời không tồn tại số \(y\) nào thỏa mãn \(x_{i} < y < x_{i + 1}\) mà \(x_{i}\) là ước của \(y\) và \(y\) là ước của \(x_{i + 1}\).
\begin{center}
\includegraphics[width=0.5\textwidth]{contest02/problem2/images/image1.png}
\end{center}
Ví dụ: cặp \((3, 36)\) thì dãy \((3, 9, 18, 36)\) là một tháp đầy đủ; nhưng dãy \((3, 12, 36)\) chưa đủ điều kiện trở thành tháp đầy đủ vì có thể chèn \(6\) vào giữa \(3\) và \(12\) để trở thành dãy \((3, 6, 12, 36)\).

Chiều cao của tháp là số lượng đĩa có trong tháp, trọng số của tháp là tổng đường kính của các đĩa trong tháp: \(x_{0} + x_{1} + \ldots + x_{k}\). Chẳng hạn, cặp số \((3, 36)\), chúng ta có thể tìm được được các tháp đầy đủ là: \((3, 9, 18, 36), (3, 6, 12, 36), (3, 6, 18, 36)\) đều có chiều cao tương ứng là \(4\) và trọng lượng lần lượt là \(66, 57, 63\).

Yêu cầu: Cho cặp \((a, b)\) tìm chiều cao và trọng số của của tháp đầy đủ có trọng số nhỏ nhất.

Input

• Dòng đầu tiên chứa hai số nguyên dương \(a\) và \(b\) \((1 \leq a, b \leq 10^{12})\).

Output

• Ghi số \(-1\) nếu không thể tìm được tháp đầy đủ tương ứng với cặp \((a, b)\).
• Trong trường hợp ngược lại ghi ra chiều cao và trọng số của tháp đầy đủ có trọng số nhỏ nhất.

Example

3 36

4 57

Trên trục số có \(n\) đoạn thẳng và \(m\) điểm. Đoạn thẳng thứ \(i\) \((1 \leq i \leq n)\) được xác định bằng cặp số nguyên \((a_{i}, b_{i})\). Điểm nguyên thứ \(j\) \((1 \leq j \leq m)\) có tọa độ \(p_{j}\). Điểm thứ \(j\) thuộc về đoạn thẳng thứ \(i\) nếu \(a_{i} \leq p_{j} \leq b_{i}\).

Yêu cầu: xác định số lượng các đoạn thẳng có chứa ít nhất \(2\) điểm trong số \(m\) điểm đã cho.

Input

• Dòng đầu chứa hai số nguyên dương \(n\) và \(m\) \((1 \leq n, m \leq 10^{5})\) lần lượt là số đoạn thẳng và số điểm.
• \(n\) dòng tiếp theo, dòng thứ \(i\) ghi hai số nguyên \(a_{i}\) và \(b_{i}\) \((-10^{9} \leq a_{i} \leq b_{i} \leq 10^{9})\) là tọa độ điểm đầu và cuối đoạn thẳng thứ \(i\).
• Dòng cuối cùng ghi \(m\) số nguyên \(p_{1}, p_{2}, \ldots, p_{m}\) \((-10^{9} < p_{i} < 10^{9})\) là tọa độ của các điểm.

Output

• Một số tự nhiên duy nhất là số lượng các đoạn thẳng chứa ít nhất \(2\) điểm trong số \(m\) điểm đã cho.

Scoring

• Subtask \(1\) (\(50\%\) số điểm): \(n, m \leq 1000\).
• Subtask \(2\) (\(50\%\) số điểm): không có ràng buộc gì thêm.

Example

3 4
-5 15
0 20
50 60
-10 3 12 18

2

Trong một đại hội thể thao, nhằm tạo không khí giao lưu thân mật giữa các thí sinh. Ban tổ chức quyết định xếp tất cả các thí sinh thành một hàng dài và tổ chức trò chơi bắt tay. Tại một thời điểm, mỗi thí sinh có thể đang quay mặt sang trái hoặc sang phải. Tuần tự, những thí sinh đang đứng đối mặt nhau trong hàng sẽ bắt tay nhau, rồi quay mặt sang hướng đối diện (từ trái sang phải, hoặc từ phải sang trái). Thời gian cho một lượt bắt tay và quay mặt là \(1\) giây. Những thí sinh không thể bắt tay với ai trong lượt đó sẽ đứng yên không thay đổi hướng quay mặt. Trò chơi cứ thế tiếp tục từng lượt bắt tay và quay mặt cho đến khi không thể thực hiện thêm lượt nào nữa (do không còn thí sinh nào đứng đối mặt nhau).

Yêu cầu: tính tổng thời gian diễn ra các lượt bắt tay và số lượng cái bắt tay được thực hiện cho đến khi trò chơi kết thúc.

Input

• Gồm một dòng duy nhất chứa một chuỗi mô tả hướng quay mặt của các thí sinh trong hàng khi bắt đầu trò chơi: ký tự L cho biết hướng quay mặt sang trái, R là quay sang phải. Chuỗi này có độ dài tối đa \(10^{5}\) ký tự.

Output

• Ghi hai số nguyên cho biết tổng thời gian diễn ra lượt bắt tay và số lượng các bắt tay được thực hiện cho đến khi trò chơi kết thúc.

Scoring

• Subtask \(1\) (\(30\%\) số điểm): trong xâu chỉ có \(1\) ký tự R.
• Subtask \(2\) (\(30\%\) số điểm): trong xâu chỉ có \(2\) ký tự R.
• Subtask \(3\) (\(40\%\) số điểm): không có ràng buộc gì thêm.

Example

RLLRLRR

3 4