Vua trò chơi

Xem PDF

Điểm: 2000 (p) Thời gian: 2.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

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\(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

Test 1

Input
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
Output
14
Impossible
26
Note

Ở test thứ \(3\), để giải cứu công chúa, Jessie đã hoàn thành các màn chơi theo thứ tự \(1 \to 2 \to 3 \to 5\).


Bình luận


  • 5
    huyhau6a2 4:20 p.m. 11 Tháng 9, 2022

    Mình xin phép trình bày lời giải của bài toán này như sau:

    Gọi \(dp[i]\) là sức mạnh sau khi qua màn thứ \(i\)

    Mặc định \(dp[1]=p\)

    Chú ý sắp xếp các cặp \(v_i, t_i\) theo TTTĐ

    Với mỗi đường đi để từ màn \(l\) qua màn \(r\) với boss sức mạnh \(v\), xét 2 trường hợp như trong đề:

    • Nếu \(dp[l]<=v\) thì \(dp[r]=max(dp[r],dp[l]-dp[l]/2)\)

    • Ngược lại, \(dp[r]=max(dp[r],dp[l]+v/2)\)

    Chú ý các phép chia đều là làm tròn xuống như trong đề

    Sau khi duyệt hết các đường đi, ta xuất kết quả dựa trên \(dp[n]\), vậy là bài toán đã được giải quyết xong

    Có vấn đề gì các bạn cứ comment cho mình nha!