Tìm kiếm nhị phân

5
3 4 7
5 5 5
1 13 2
2 4 7
1 5 4

2
1
1
4
2

Với test đầu n=3,m=4,k=7: nếu độ dài băng ghế tối đa cho phép là L thì mỗi hàng m ghế xếp được tối đa m - floor(m/(L+1)) người (xen kẽ khối L người liền nhau với 1 ghế trống để cắt mạch). Với L=1, mỗi hàng chỉ xếp được 4-2=2 người, 3 hàng tối đa 6 người < 7 nên không đủ chỗ. Với L=2, mỗi hàng xếp được 4-1=3 người, 3 hàng đủ 9 ≥ 7 chỗ, nên L=2 là giá trị nhỏ nhất khả thi, khớp kết quả in ra là 2.

8
5 3 10
2 1 11 3 7
10 1 5
17 8 12 11 7 11 21 13 10 8
3 4 5
3 4 2
8 12 25
10 7 5 13 8 9 12 7
2 3 3
5 2
9 7 9
2 10 5 1 3 7 6 2 3
1 8 10
9
5 5 6
1 4 2 6 4

3
0
1
4
0
3
1
2

Với test đầu (n=5,l=3,r=10,a=[2,1,11,3,7]): nên lấy số lá ÍT NHẤT để tổng vừa đạt ≥ l, vì lấy dư sẽ tốn lá cho các vòng sau. Vòng 1 lấy 2 lá đầu (2+1=3), tổng vừa đạt l=3 và ≤ r=10 nên thắng, con trỏ chuyển tới lá 11. Một lá 11 đã vượt r=10 nên chắc chắn thua, buộc bốc đúng 1 lá này để giữ tối đa lá còn lại. Hai lá cuối 3 và 7: lấy riêng lá 3 (tổng 3, trong [3,10]) là một vòng thắng, rồi lấy nốt lá 7 (tổng 7, trong [3,10]) cũng thắng. Tổng cộng 3 vòng thắng và 1 vòng thua, khớp đáp số 3.

4
1
1
6
101101
7
1110001
5
11111

1
8
18
6

1. Test 1

   Với test n=1, s='1': chỉ có một mô hình giá 1 và một ngày ghé duy nhất nên buộc mua với giá gốc 1, khớp kết quả 1.

2. Test 2

   Với test n=6, s='101101' (các ngày ghé là 1,3,4,6): mô hình 5 và 6 chỉ được bán từ ngày 5,6 nên bắt buộc gộp vào ngày 6, mua cùng lúc khiến mô hình 6 (đắt nhất) được miễn phí, chỉ tốn 5 đồng. Mô hình 4 phải mua ở ngày 4, ghép với mô hình 1 (rẻ nhất còn lại) để mô hình 4 được miễn phí, tốn 1 đồng. Mô hình 2 và 3 mua ở ngày 3, ghép đôi để mô hình 3 (đắt hơn) miễn phí, tốn 2 đồng. Tổng chi phí 5+1+2=8, khớp kết quả.

4
10 1 3
10
10
0
6
7
10 2 4
4 10
4 7
6
4
2
7
1000000000 1 1
1000000000
1000000000
99999999
6 1 3
6
5
2
6
5

0 6 7 
5 4 2 5 
99999999 
1 5 4 

Với test đầu (n=10, chỉ một biển báo tại vị trí 10 ở thời điểm 10, xuất phát ngầm định từ vị trí 0 tại thời điểm 0): xe đi đều trên đoạn 0→10 trong 10 đơn vị thời gian nên tốc độ là 1, tức thời điểm tới vị trí d chính bằng d. Với d=0 xe đang ở điểm xuất phát nên thời điểm là 0; d=6 xe tới lúc 6; d=7 xe tới lúc 7, khớp đúng dãy in ra '0 6 7'.

3
4
0 1 0 2
1 1 3
2
3 0
1
5
2 5 3 9 6
3 1 5 2

1
3
6

Với test đầu (cây gốc 1 có con 2,3; đỉnh 3 có con 4; a=[0,1,0,2]): không thể tác động ngay tại gốc vì đỉnh 3 đang bằng 0, giảm thêm sẽ âm. Thực hiện thao tác tại đỉnh 3 trước: a_3 tăng lên 1, a_4 (con duy nhất trong cây con của 3) giảm xuống 1, mảng thành [0,1,1,1]. Lúc này thực hiện thao tác tại gốc: a_1 tăng lên 1, còn a_2,a_3,a_4 đều giảm về 0 (vẫn hợp lệ vì không âm). Không thể tăng thêm nữa vì mọi đỉnh con đều đã bằng 0, nên giá trị gốc lớn nhất đạt được là 1, khớp kết quả.

2
4 5
BR BR GY GR
1 2
3 1
4 4
1 4
4 2
2 1
BG RY
1 2

1
4
0
3
2
-1

1. Test 1

   Với test đầu, thành phố 1 và 2 đều có cổng BR nên đi thẳng 1→2 tốn |1-2|=1, khớp giá trị đầu tiên.

2. Test 2

   Với truy vấn (3,1): thành phố 3 là GY và thành phố 1 là BR không chung màu nào nên phải trung chuyển; thành phố 4 là GR chung màu G với thành phố 3 và chung màu R với thành phố 1, cho quãng đường 3→4→1 với chi phí |3-4|+|4-1|=1+3=4, khớp giá trị thứ hai.

3. Test 3

   Ở test thứ hai chỉ có 2 thành phố với màu BG và RY hoàn toàn rời nhau, không có thành phố trung gian nào để nối nên không thể di chuyển được, trả về -1.

5
6 3
1 2 3 4 5 6
6 5
3 1 6 5 2 4
5 1
3 5 4 2 1
6 3
4 3 1 5 2 6
3 2
3 2 1

0
1
3 4
2
2 4
1 5
2
4 5
2 4
1
1 3

1. Test 1

   Ở test đầu p đã là hoán vị tăng dần 1..6 với x=3: chạy thuật toán nhị phân chuẩn, l hội tụ đúng về vị trí 3 (nơi chứa giá trị 3) nên không cần đổi chỗ nào, in ra 0.

2. Test 2

   Ở test thứ hai, p=[3,1,6,5,2,4], x=5: chạy thuật toán gốc sẽ hội tụ sai về vị trí 6 (giá trị 4). Đổi chỗ vị trí 3 và 4 (giá trị 6 và 5) biến mảng thành [3,1,5,6,2,4]; chạy lại thuật toán: m=4 có p_4=6>5 nên r=4, m=2 có p_2=1≤5 nên l=2, m=3 có p_3=5≤5 nên l=3, dừng ở l=3 với p_3=5=x, đúng yêu cầu chỉ bằng 1 phép đổi chỗ (3,4), khớp kết quả.