[Học thêm HSG9] Ngày 6/8/2024

Maka đang mắc phải hội chứng khó đọc (Dyslexia) và các chuyên gia tâm lý cho rằng việc chuyển đổi các câu nói thành các xâu nhị phân sẽ giúp cô dễ hiểu hơn. Để kiểm chứng sự hiệu quả của phương pháp này, các bác sĩ đã tạo ra một chiếc máy giúp chuyển các dạng âm thanh thành dạng xâu nhị phân. Với sự mong đợi của họ, chiếc máy không những chuyển được các câu nói của các chuyên gia thành xâu nhị phân mà còn đưa các loại âm thanh nhiễu động từ bên ngoài khiến nội dung của xâu nhị phân trở nên khó hiểu với Maka. Cụ thể, xâu ban đầu là \(k\) (\(0 <= |k| <= 2000\)) thì các âm thanh nhiễu động có dạng là các ký tự nằm bên phải hay bên trái xâu k (2 phần này có số ký tự giống nhau). Họ còn nhận ra rằng các ký tự nhiễu khi nó có vị trí đối xứng với nhau qua xâu gốc thì sẽ khác nhau (các ký tự nhiễu có thể là "0" hoặc "1").

Ví dụ: Cho xâu ban đầu là xâu 1101 thì máy có thể trả về xâu 111010, 011011, 10110110, 01110101 hay thậm chí là 10001110101110.

Các chuyên gia không muốn sửa lỗi đó lắm nên đưa cho Maka sử dụng luôn. Maka rất "tứk dận" và nhờ bạn (bạn thân bất đắc dĩ của Maka) cứu cô ấy trong việc này. Bạn mặc dù không muốn giúp cô ấy lắm nhưng thôi... đều là con người cả mà, sống 🐕 thì không được. Bạn được biết rằng các chuyên gia tâm lý thường sẽ nói chuyện ngắn gọn vì họ không muốn tốn thời gian cho lắm nên hãy giúp bạn ấy tìm độ dài xâu nhị phân ban đầu ngắn nhất có thể có được khi biết máy trả về một xâu nào đó nhé.

Input

• Dòng đầu tiên chứa số nguyên \(t(t ≤ 100)\) là số lượng testcase.
• Dòng đầu tiên của mỗi testcase chứa số nguyên \(n\) \((1 ≤ n ≤ 2000)\) là độ dài của xâu kết quả.
• Dòng thứ 2 của mỗi testcase chứa xâu \(s\) là xâu kết quả.

Output

• Dòng thứ \(i\) in ra độ dài xâu nhị phân ban đầu ngắn nhất có thể có được đối với xâu kết quả trong testcase thứ \(i\).

9
3
100
4
0111
5
10101
6
101010
7
1010110
1
1
2
10
2
11
10
1011011010

1
2
5
0
3
1
0
2
4

//sinh test lại bài này
Opal đang rất khó chịu vì những con 🦟 ở bên ngoài màn anh ấy. Anh ấy không thể ngủ được nên anh ấy quyết định dùng cái vợt 🦟 ngàn năm có 1 của anh ấy. Có \(n\) con 🦟 xếp thành 1 hàng ngang, con 🦟 ở vị trí thứ \(i\) có độ nhỏ là \(a_i\) (\(a_i\) càng lớn thì con 🦟 càng nhỏ). Đáng buồn thay, cái vợt này có lỗ rất vừa khít với một số con 🦟, những con 🦟 có độ nhỏ lớn hơn \(k\) có thể sẽ bay lọt qua lỗ này. Opal chỉ có thể dùng cái vượt 🦟 ngàn năm có 1 này 1 lần và vì anh thích đập nát nên không muốn con 🦟 nào bay lọt qua lỗ cả. Hãy giúp Opal tìm số con 🦟 liên tiếp lớn nhất có thể đập được nhé!

Input

• Dòng đầu tiên chứa 2 số nguyên \(n, k\) \((n ≤ 500000; k ≤ 1000000)\).
• \(n\) dòng tiếp theo, là \(n\) số nguyên \(a_i\) \((a_i ≤ 1000000)\)

Output

• Dòng đầu tiên in ra chỉ số bắt đầu và chỉ số kết thúc của các con 🦟 được đập (nếu có nhiều dãy có cùng độ dài, in ra dãy có số chỉ bắt đầu nhỏ nhất).

9 3
6 5 1 2 3 2 1 4 5

3 7

Ông thầy Cucukaka khó tính của bạn được phân công ra đề cho một kỳ kiểm tra định kỳ sắp tới ở trường. Vốn dĩ, tổ trưởng chuyên môn đã ấn định độ khó cho các bài tập sao cho bài tập thứ i không được có mức độ khó quá \(b_i\). Tuy nhiên, do ông thầy này rất thích hành học sinh nên ông đã cho một số bài còn khó hơn chỉ tiêu đề ra! Các giáo viên khác trong ban ra đề quyết định điều chỉnh độ khó cho các câu hỏi, nhưng họ không còn đủ thời gian để thay đổi hết tất cả các câu hỏi trong đề. Vậy nên họ đã quyết định sửa đổi các bài tập như sau: Họ tạo thêm 1 bài tập khác đưa vào đề thi rồi loại bỏ bài tập khó nhất trong đề. Là một người trong ban ra đề, hãy tìm số bài tập ít nhất cần làm để đề thi có thể thỏa mãn điều kiện do tổ trưởng tổ chuyên môn đưa ra!

Input

• Dòng đầu tiên chứa số nguyên \(t\) \((t ≤ 100)\) là số lượng testcase.
• Dòng đầu tiên của mỗi testcase chứa số nguyên \(n\) \((1 ≤ n ≤ 100)\) là số lượng bài tập trong đề thi.
• Dòng thứ 2 của mỗi testcase chứa \(n\) số nguyên \(a_i\) là độ khó của vấn đề thứ \(i\) mà ông thầy đưa ra \((1 ≤ a_1 ≤ a_2 ≤ ... ≤ a_n ≤ 10^9)\).
• Dòng thứ 3 của mỗi testcase chứa \(n\) số nguyên \(b_i\) là điều kiện của vấn đề thứ \(i\) do tổ tưởng chuyên môn đề ra \((1 ≤ b_1 ≤ b_2 ≤ ... ≤ b_n ≤ 10^9)\).

Output

• Dòng thứ \(i\) in ra số bài tập ít nhất đối với testcase thứ \(i\).

2
6
1000 1400 2000 2000 2200 2700
800 1200 1500 1800 2200 3000
6
4 5 6 7 8 9
1 2 3 4 5 6

2
3

Hồ cá của bạn حسن دردير đã bị đám trẻ con nghịch cho hết nước một cách thần kỳ. Những chú cá đang khó thở và cần được cấp nước ngay lập tức. Khổ nỗi, bể cá có một hệ thống đường ống rất phức tạp đã bị hỏng, làm địa hình trong bể cá trông khó chịu vô cùng. Ở đáy bể có \(n\) ống nước hình lập phương thẳng đứng được xếp thẳng hàng với nhau và không có lỗ hổng giữa chúng, ống nước thứ \(i\) có độ cao là \(a_i\). Để cứu những chú cá của mình, حسن دردير cần phải đổ nước vào hồ cá sao cho chiều cao mặt nước so với đáy bể (\(h\)) là lớn nhất có thể. Số lượng khối nước cần bơm vào sao cho mực nước có chiều cao là \(h\) được tính như sau: Với mỗi phần bể thứ \(i\), nếu phần đó có ống nước cao hơn hoặc bằng chiều cao của mặt nước thì không cần thêm khối nước nào, nếu phần ống nước thấp hơn chiều cao mặt nước thì số lượng nước cần bơm thêm vào là \(h - a_i\).
Ví dụ với hệ thống ống nước \(a\) \(=\) [\(3,1,2,4,6,2,5\)] và \(h = 4\), thì lượng nước cần bơm thêm là \(w\) = 8 khối nước.

Rất tiếc, số lượng nước có sẵn trong nhà حسن دردير là có hạn, chỉ có sẵn \(x\) khối nước mà thôi. Hãy tìm chiều cao lớn nhất \(h\) có thể đạt được.

Input

• Dòng đầu tiên chứa số nguyên \(t\) \((t ≤ 100)\) là số lượng testcase.
• Dòng đầu tiên của mỗi testcase chứa 2 số nguyên \(n, x\) \((1 ≤ n ≤ 200000; 1 ≤ x ≤ 10^9)\) lần lượt là số lượng ống và số khối nước có sẵn.
• Dòng thứ 2 của mỗi testcase chứa \(n\) số nguyên \(a_i\) \((1 ≤ a_i ≤ 10^9)\) là chiều cao của ống nước thứ \(i\).

Output

• Dòng thứ \(i\) in ra chiều cao \(h\) cao nhất có thể đối với testcase thứ \(i\).

5
7 9
3 1 2 4 6 2 5
3 10
1 1 1
4 1
1 4 3 4
6 1984
2 6 5 9 1 8
1 1000000000
1

4
4
2
335
1000000001

Bạn Ngủ đang gặp vấn đề về giấc ngủ (hay khó ngủ). Bạn Ngủ thường khó vào giấc, cảm thấy không thể thư giãn dù rất mệt mỏi. Dù đã thử nhiều cách như đọc sách, nghe nhạc nhẹ, hay uống sữa ấm trước khi ngủ nhưng tình trạng vẫn không cải thiện. Sau một hồi tìm hiểu trên Internet, bạn Ngủ đã nhận ra rằng cách tốt nhất để ngủ được là thuốc ngủ(?).
Có \(n\) loại thuốc ngủ, thuốc ngủ thứ \(i\) có tác dụng gây ngủ là \(a_i\) và tác dụng gây khó chịu là \(b_i\).
Cặp thuốc ngủ \(i\) và \(j\) (\(i < j\)) được gọi là cặp thuốc ngủ đỉnh cao nếu \(a_i + a_j > b_i + b_j\) (tức là sự khó chịu khi dùng ít hơn tác dụng gây ngủ).

Nhiệm vụ của bạn là giúp bạn Ngủ tìm số lượng cặp thuốc ngủ đỉnh cao để giúp Ngủ dễ ngủ hơn nhé!

Input

• Dòng đầu tiên chứa số nguyên \(n\) \((1 ≤ n ≤ 100000)\) là số lượng thuốc ngủ.
• Dòng thứ 2 chứa \(n\) số nguyên \(a_i\) \((1 ≤ a_i ≤ 10^9)\) là độ gây ngủ của viên thuốc thứ \(i\).
• Dòng thứ 3 chứa \(n\) số nguyên \(b_i\) \((1 ≤ b_i ≤ 10^9)\) là độ gây khó chịu của viên thuốc thứ \(i\).

Output

• In ra 1 số nguyên là số lượng cặp thuốc ngủ đỉnh cao.

5
4 8 2 6 2
4 5 4 1 3

7