LQDOJ Contest #1 Mid Autumn 2022 - Div 2

Trung thu đang đến gần, chú Ba muốn chuẩn bị thật nhiều bánh trung thu để tặng cho các em nhỏ ở vùng sâu vùng xa. Vì đường xá xa xôi nên chú Ba cần đóng gói cẩn thận rồi mới vận chuyển. Hiện tại chú có có \(n\) gói bánh, \(k\) vách ngăn và rất nhiều hộp. Biết rằng nếu đặt \(x\) \((x \ge 0)\) vách ngăn vào nó, ta sẽ nhận được một hộp được chia làm \(x+1\) phần.

Chú Ba không muốn hộp có quá nhiều vách ngăn nên chú giới hạn một hộp không được chia thành quá \(a\) phần. Mặt khác, chú cũng không muốn bỏ quá \(b\) gói bánh vào một phần của hộp. Vì số lượng bánh là khá nhiều nên chú muốn nhờ bạn giúp xác định số lượng hộp tối thiểu cần dùng để bỏ hết tất cả bánh trung thu vào hộp là bao nhiêu.

Input

• Một dòng duy nhất chứa bốn số nguyên \(a\), \(n\), \(k\) và \(b\) (\(2 \le a \le 1000\), \(1 \le n, k, b \le 1000\)).

Output

• In ra một số nguyên duy nhất là kết quả của bài toán.

Example

2 11 3 3

2

Cho số nguyên \(n\), hãy tìm một hoán vị đẹp độ dài \(n\).

Một hoán vị \(a\) gồm các số \(1, 2, \ldots, n\) được xem là đẹp khi các tổng \(a[i] + a[j]\) là phân biệt với mọi \(1 \leq i \leq j \leq n\) và \(i + j = n + 1\).

Input

• Một dòng duy nhất chứa số nguyên \(n\) (\(1 \leq n \leq 10 ^ 6\)).

Output

• Một dòng duy nhất chứa \(n\) số nguyên là hoán vị đẹp cần tìm cần tìm hoặc \(-1\) nếu không tồn tại.

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(n \leq 10\).
• Subtask \(2\) (\(80\%\) số điểm): Không có ràng buộc gì thêm.

Example

5

4 2 3 1 5

Cho \(n\) đoạn thẳng trên trục tọa độ OX. Đoạn thứ \(i\) là \([l_i, r_i]\) và che phủ các điểm \(j\) với \(l_i \leq j \leq r_i\).

Hãy bỏ đi ít nhất các đoạn sao cho với mọi điểm trên trục OX có tối đa \(k\) đoạn thẳng che phủ nó.

Input

• Dòng đầu tiên chứa hai số nguyên \(n\) và \(k\) (\(1 \leq k \leq n \leq 2 \cdot 10^5\)).
• Trong \(n\) dòng tiếp theo, dòng thứ \(i\) chứa hai số nguyên \(l_i\) và \(r_i\) (\(1 \leq l_i \leq r_i \leq 2 \cdot 10^5\)).

Output

• Dòng đầu tiên chứa số nguyên \(m\) là số lượng đoạn tối thiểu cần loại bỏ.
• Dòng tiếp theo chứa \(m\) số nguyên phân biệt \(p_1, p_2, p_3, \ldots, p_m\) (\(1 \leq p_i \leq n\)) là chỉ số của các đoạn bị loại bỏ theo bất kì thứ tự nào. Nếu có nhiều đáp án, hãy in một đáp án bất kì.

Scoring

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

Example

3 1
1 3 
1 2 
3 3 

1
1

Cho hai số nguyên \(n\) và \(x\). Hãy đếm số lượng dãy \(a\) độ dài \(n\), mỗi phần tử có giá trị trong khoảng \([1, n]\) và hàm sau có giá trị đúng:

binary_search(a, n, x)
    left = 1
    right = n
    while left <= right
        middle = (left + right) / 2
        if a[middle] == x then
            return true

        if a[middle] < x then
            left = middle + 1
        else
            right = middle - 1

    return false

Lưu ý rằng các phần tử của dãy được đánh chỉ số từ \(1\) và phép chia được thực hiện ở phần nguyên (làm tròn xuống).

Input

• Một dòng duy nhất chứa hai số nguyên \(n\) và \(x\) (\(1 \leq x \leq n \leq 10 ^ {12}\)).

Output

• Một dòng duy nhất chứa một số nguyên là số lượng dãy \(a\) thỏa mãn sau khi chia lấy dư cho \(10 ^ 9 + 7\).

Scoring

• Subtask 1 (20% số điểm): \(n \leq 7\).
• Subtask 2 (20% số điểm): \(n \leq 10 ^ 3\).
• Subtask 3 (30% số điểm): \(n \leq 10 ^ 6\).
• Subtask 4 (30% số điểm): Không có ràng buộc gì thêm.

Example

3 2

15

Cho một xâu \(s\) chỉ gồm các kí tự a, b, c và d. Bạn cần thực hiện \(q\) truy vấn thuộc một trong hai dạng sau:

• 1 i c: \(i\) là số nguyên \((1 \le i \le |s|)\), \(c\) là kí tự a, b, c hoặc d, có nghĩa là kí tự ở vị trí \(i\) của xâu \(s\) được thay thành kí tự \(c\).
• 2 l r t: \(l\), \(r\) là số nguyên \((1 \le l \le r \le |s|)\), \(t\) là một xâu chỉ chứa các kí tự a, b, c và d \((1 \le |t| \le 10)\), có nghĩa là nếu viết tiền tố của xâu \(ttt\dots\) (xâu chứa vô số xâu \(t\) được viết liên tiếp nhau) dưới xâu \(s\) từ vị trí \(l\) đến \(r\) thì số lượng vị trí mà kí tự của xâu \(s\) trùng với kí tự được viết dưới nó là bao nhiêu?

Input

• Dòng đầu tiên chứa xâu \(s\) \((1 \le |s| \le 10^5)\).
• Dòng tiếp theo chứa số nguyên \(q\) \((1 \le q \le 10^5)\).
• Trong \(q\) dòng tiếp theo, mỗi dòng chứa một trong hai dạng 1 i c hoặc 2 l r t.

Output

• Với mỗi truy vấn dạng 2 l r t, in ra một số nguyên là kết quả.

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(1 \le |s|, q \le 1000\).
• Subtask \(2\) (\(30\%\) số điểm): Tất cả các truy vấn dạng 2 l r t đều có \(|t| = 1\).
• Subtask \(3\) (\(50\%\) số điểm): Không ràng buộc gì thêm.

Example

abcdcdd
4
2 2 5 bc
2 3 7 cdc
1 5 a
2 3 7 cdc 

3
4
3

Trong mùa trung thu này, có một trò chơi được rất nhiều bạn trẻ ưa chuộng, trong đó có Jessie - một cao thủ gaming. Đó là trò chơi giải cứu công chúa. Với quyết tâm trở thành vua trò chơi thứ hai (sau Mutō Yūgi), Jessie quyết định sẽ đạt thành tích tốt nhất có thể trong trò chơi này. Trò chơi gồm \(n\) màn chơi và \(m\) cánh cổng. Cánh cổng thứ \(i\) đi từ màn \(v_{i}\) đến màn \(t_{i}\) \((v_{i} < t_{i})\) và được canh giữ bởi một con boss với điểm sức mạnh là \(l_{i}\). Công chúa bị nhốt tại một tòa lâu đài ở màn \(n\), để phá được tòa lâu đài và cứu công chúa ra, Jessie cần có điểm sức mạnh ít nhất là \(D\).

Jessie sẽ bắt đầu chơi từ màn \(1\) với điểm sức mạnh có sẵn là \(p\). Để vượt qua một cánh cổng đi từ màn \(v_{x}\) đến màn \(t_{x}\), Jessie buộc phải đối đầu với con boss canh giữ cánh cổng đó. Nếu điểm sức mạnh hiện tại của Jessie lớn hơn điểm của boss, Jessie sẽ đánh bại con boss và được tăng thêm \(\left\lfloor \dfrac{l_{x}}{2} \right\rfloor\) điểm sức mạnh (phép chia làm tròn xuống). Ngược lại, Jessie sẽ phải hiến tế và mất đi một nửa điểm sức mạnh của mình (phép chia làm tròn xuống) để con boss mở cánh cổng cho cô qua.

Bạn hãy giúp Jessie xác định xem liệu cô có thể giải cứu được công chúa không. Nếu được, Jessie cần biết điểm sức mạnh tối đa mà cô có thể đạt được là bao nhiêu.

Input

• Dòng đầu tiên chứa số nguyên \(t\) \((1 \leq t \leq 1000)\) thể hiện số test. Mỗi test có dạng:
• Dòng đầu tiên chứa bốn số nguyên \(n, m, p, D\) \((2 \leq n \leq 10^{6}, 1 \leq m \leq 2 \times n, 0 \leq p, D \leq 10^{9})\).
• \(m\) dòng sau, dòng thứ \(i\) chứa ba số nguyên \(l_{i}, v_{i}, t_{i}\) \((0 \leq l_{i} \leq 10^{9}, 1 \leq v_{i} < t_{i} \leq 10^{6})\).
• Tổng \(n\) trong tất cả các test không vượt quá \(10^{6}\).

Output

• Với mỗi test, in ra Impossible nếu không thể giải cứu công chúa. Ngược lại, in ra điểm sức mạnh tối đa đạt được.

Scoring

• Subtask \(1\) (\(15\%\) số điểm): \(n, m \leq 10\).
• Subtask \(2\) (\(15\%\) số điểm): Có \(n - 1\) cánh cổng, cánh cổng thứ \(i\) cho phép đi đến màn chơi \(i + 1\) sau khi hoàn thành màn chơi \(i\).
• Subtask \(3\) (\(70\%\) số điểm): Không có ràng buộc gì thêm.

Example

3
2 1 10 10
9 1 2
2 1 10 10
10 1 2
5 6 10 24
7 1 2
10 2 3
12 2 5
3 1 3
11 3 4
17 3 5

14
Impossible
26