Đề bài C: Consecutive Card Game GSPVH tham gia một sự kiện trò chơi thẻ bài mang tên…
- User
Đề bài C: Consecutive Card Game
GSPVH tham gia một sự kiện trò chơi thẻ bài mang tên "Cards in a black box". Nếu thắng trò chơi, anh sẽ nhận được phần thưởng lớn như trúng độc đắc!
Luật chơi:
-
Khởi đầu:
- Người dẫn chương trình đặt vào hộp đen ( n ) lá bài, mỗi lá có một số nguyên ( v_1, v_2, ..., v_n ).
- Sau đó, người dẫn công bố một số nguyên dương ( k ).
-
Vòng khởi động:
- GSPVH chọn một số nguyên dương ( t_0 ).
- Người dẫn chương trình rút ngẫu nhiên ( t_0 ) lá bài từ hộp đen.
- GSPVH thắng nếu trong số các lá bài được rút ra có ( k ) số nguyên là các số nguyên liên tiếp, tức là tồn tại số nguyên ( x ) sao cho tất cả các số từ ( x ) đến ( x + k - 1 ) (bao gồm cả hai đầu) đều xuất hiện.
- Nếu thua, trò chơi kết thúc ngay lập tức.
-
Vòng chính:
- Nếu thắng vòng khởi động, GSPVH chơi thêm ( q ) vòng nữa. Ở mỗi vòng:
- Người dẫn công bố ba số nguyên ( l_i, r_i, c_i ).
- Các lá bài có giá trị từ ( l_i ) đến ( r_i ) bị loại bỏ khỏi hộp đen và thay thế bằng ( c_i ) lá bài mới có giá trị tương tự.
- GSPVH chọn số ( t_i ) (số lá bài được rút ra).
- Người dẫn chương trình rút ngẫu nhiên ( t_i ) lá bài từ hộp đen.
- GSPVH thắng nếu ( k ) số nguyên liên tiếp xuất hiện trong số các lá bài được rút ra.
- Nếu thắng vòng khởi động, GSPVH chơi thêm ( q ) vòng nữa. Ở mỗi vòng:
-
Lưu ý:
- Nếu GSPVH thua ở bất kỳ vòng nào, trò chơi kết thúc ngay lập tức.
- Nếu thắng, các lá bài đã rút sẽ được trả lại hộp đen.
Yêu cầu:
GSPVH muốn đảm bảo chiến thắng ở mỗi vòng và cần chọn ( t_i ) (số lá bài rút ra) nhỏ nhất để chắc chắn thắng. Hãy xác định giá trị ( t_0 ) cho vòng khởi động và ( t_1, t_2, ..., t_q ) cho ( q ) vòng chính.
Đầu vào:
- Dòng đầu tiên chứa ba số nguyên ( n, k, q ) (( 1 \leq n \leq 10^6, 1 \leq q \leq 10^5, 1 \leq k \leq 5 )).
- Dòng thứ hai chứa ( n ) số nguyên ( v_1, v_2, ..., v_n ) (( -10^9 \leq v_i \leq 10^9 )).
- ( q ) dòng tiếp theo, mỗi dòng chứa ba số ( l_i, r_i, c_i ) (( -10^9 \leq l_i \leq r_i \leq 10^9, 1 \leq c_i \leq 10^9 )).
Đầu ra:
In ( q+1 ) số nguyên, tương ứng với ( t_0 ) và ( t_1, t_2, ..., t_q ).
Ví dụ:
Đầu vào:
4 2 2 1 2 4 5 8 8 1 6 7 1Đầu ra:
3 4 5
Ghi chú:
- Trong ví dụ trên, ( k = 2 ), nghĩa là cần ( k = 2 ) số nguyên liên tiếp để thắng:
- Vòng khởi động: Rút 3 lá bài đảm bảo có ( 1, 2 ) hoặc ( 4, 5 ).
- Vòng 1: Hộp đen có các lá bài ( {1, 2, 4, 5, 8} ), cần rút 4 lá bài.
- Vòng 2: Hộp đen có các lá bài ( {1, 2, 4, 5, 6, 7, 8} ), cần rút 5 lá bài.
-
- Assistant
To solve the Consecutive Card Game problem, we need to efficiently determine the minimum number of cards GSPVH must draw to guarantee a win in each round, given the game's rules. The key insight is to compute the maximum number of cards that can be drawn without containing any sequence of ( k ) consecutive integers. The desired number of cards to draw, ( t_i ), is then one more than this maximum.
Step-by-Step Solution:
-
Understanding the Problem:
- Initial Setup: GSPVH starts with a set of unique card values. Each operation may add new cards by specifying a range ( [l_i, r_i] ).
- Winning Condition: To win, the drawn subset must contain at least ( k ) consecutive integers.
- Objective: For each round (initial and after each operation), determine the smallest ( t_i ) such that any subset of ( t_i ) cards contains ( k ) consecutive integers.
-
Maximizing Subset Without Winning:
- To find ( t_i ), first determine the maximum number of cards ( t_{\text{max}} ) that can be drawn without containing ( k ) consecutive integers.
- The formula for ( t_{\text{max}} ) for a run (a sequence of consecutive integers) of length ( m ) is: [ t_{\text{max}} = \sum (\text{run length} - \left\lfloor \frac{\text{run length}}{k} \right\rfloor) ]
- Then, ( t_i = t_{\text{max}} + 1 ).
-
Handling Operations:
- Runs Management: Maintain a list of current runs (sequences of consecutive integers).
- Merging Runs: When a new range ( [l_i, r_i] ) is added, merge it with existing runs that overlap or are adjacent to this range.
- Updating ( t_{\text{max}} ): Adjust the total sum based on the new merged runs.
-
Efficient Implementation:
- Data Structure: Use a sorted list to maintain the runs. This allows efficient searching and merging using binary search.
- Binary Search: Utilize the
bisectmodule to quickly find overlapping runs. - Dynamic Updates: After each operation, update the runs and recalculate ( t_i ) accordingly.
Final Implementation:
Below is the Python implementation that encapsulates the above logic. The code efficiently handles the initial setup and each operation, maintaining the runs and calculating the required ( t_i ) values.
import sys import threading import bisect from math import floor def main(): import sys import sys sys.setrecursionlimit(1 << 25) n, k, q = map(int, sys.stdin.readline().split()) v = list(map(int, sys.stdin.readline().split())) initial_set = sorted(set(v)) runs = [] total_sum = 0 if initial_set: current_start = initial_set[0] current_end = initial_set[0] for x in initial_set[1:]: if x == current_end +1: current_end = x else: m_i = current_end - current_start +1 sum_i = m_i - (m_i //k ) total_sum += sum_i runs.append([current_start, current_end]) current_start = x current_end = x # Add the last run m_i = current_end - current_start +1 sum_i = m_i - (m_i //k ) total_sum += sum_i runs.append([current_start, current_end]) # Now, runs is a sorted list of [start, end] # Function to find the first run that might overlap with [l, r] def find_first_run(l): # Find the first run with end >= l -1 # Using bisect to find the insertion point for [l, ] # We need to check runs where start <= r+1 and end >= l-1 # So find the first run with end >= l-1 left = 0 right = len(runs) while left < right: mid = (left + right)//2 if runs[mid][1] < l -1: left = mid +1 else: right = mid return left # Output t0 print(total_sum +1) for _ in range(q): l, r, c = map(int, sys.stdin.readline().split()) # Insert [l, r] into runs # Find all runs overlapping or adjacent to [l, r] idx = find_first_run(l) new_start = l new_end = r sum_old =0 remove_indices = [] while idx < len(runs): run = runs[idx] if run[0] > r +1: break # Overlapping or adjacent new_start = min(new_start, run[0]) new_end = max(new_end, run[1]) m_i = run[1] - run[0] +1 sum_i = m_i - (m_i //k ) sum_old += sum_i remove_indices.append(idx) idx +=1 # Remove the old runs for i in reversed(remove_indices): del runs[i] # Compute the new run's sum m_new = new_end - new_start +1 sum_new = m_new - (m_new //k ) total_sum = total_sum - sum_old + sum_new # Insert the new run at the correct position insert_pos = bisect.bisect_left(runs, [new_start, new_end]) runs.insert(insert_pos, [new_start, new_end]) # Output t_i print(total_sum +1) threading.Thread(target=main).start()Explanation of the Code:
-
Initialization:
- Reading Input: The code reads the initial number of cards, the required number of consecutive integers ( k ), and the number of operations ( q ).
- Initial Runs: It processes the initial set of card values, identifying contiguous runs of consecutive integers and calculating their contributions to the total sum.
-
Handling Operations:
- Finding Overlapping Runs: For each operation, the code identifies runs that overlap or are adjacent to the new range ( [l_i, r_i] ).
- Merging Runs: It merges these runs with the new range, updating the total sum accordingly by removing the old contributions and adding the new merged run's contribution.
- Inserting New Run: The new merged run is inserted back into the list of runs, maintaining the sorted order.
-
Output:
- Initial ( t_0 ): Before any operations, the code outputs ( t_0 = \text{total_sum} + 1 ).
- Subsequent ( t_i ): After each operation, it outputs the updated ( t_i ).
Performance Considerations:
- Efficiency: The use of binary search (
bisect) ensures that operations are handled in logarithmic time relative to the number of runs, making the solution efficient even for large inputs. - Threading: The use of threading allows the solution to handle deeper recursion limits and large input sizes without stack overflow issues.
Conclusion:
This solution effectively manages the runs of consecutive integers and updates them dynamically with each operation to compute the required ( t_i ) values. By leveraging efficient data structures and algorithms, it ensures that the solution scales well with large input sizes.
-