Contest ôn HSG 9-10 #12

Bộ đề bài

Trở lại kỳ thi
# Bài tập Điểm Thời gian: Giới hạn bộ nhớ
1 Vòng tròn 30 (p) 1.0s 256M
2 Chạy trốn tình yêu 30 (p) 1.0s 256M
3 Quà Đài Loan 40 (p) 1.0s 512M

1. Vòng tròn

Điểm: 30 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: CIRCLE.INP Output: CIRCLE.OUT

Lâm là nam chính trong truyện TN; là một cậu bé thông minh, ham học. Hôm nay, Lâm xếp tất cả các ký tự chữ cái và chữ số để tạo thành một vòng quay - "Chiếc nón kì lạ". Cậu sắp theo thứ tự: bắt đầu là các chữ cái in thường từ a đến z, tiếp theo là các chữ cái in hoa từ A đến Z, và cuối cùng là các chữ số từ 0 đến 9.

Quy luật nối tiếp trên vòng quay như sau: ngay sau ký tự z là ký tự A, ngay sau ký tự Z là chữ số 0, và vì là vòng tròn khép kín nên ngay sau chữ số 9 sẽ quay trở lại ký tự a.

Lúc đầu, mũi tên của vòng quay đang chỉ vào vị trí của ký tự a. Lâm bắt đầu quay mũi tên theo chiều kim đồng hồ. Mỗi bước di chuyển, mũi tên sẽ nhích sang ký tự liền kề tiếp theo. Lâm muốn biết, sau đúng \(K\) bước di chuyển, mũi tên sẽ dừng lại ở ký tự nào?

Yêu cầu: Cho số nguyên không âm \(K\). Hãy in ra ký tự tại vị trí dừng lại của mũi tên.

Input

Đọc từ tệp văn bản CIRCLE.INP:

  • Một dòng duy nhất chứa số nguyên không âm \(K\).

Output

Ghi ra tệp văn bản CIRCLE.OUT:

  • Một ký tự duy nhất là kết quả của bài toán.

Example

Test 1

Input 
2
Output 
c
Note

Bắt đầu từ a. Sau 1 bước là b. Sau 2 bước là c.

Test 2

Input 
26
Output 
A
Note

Từ a đến z là 25 bước. Bước thứ 26 sẽ chuyển từ z sang A.

Scoring

  • Subtask 1 (\(30\%\) số điểm): \(K \le 100\).
  • Subtask 2 (\(30\%\) số điểm): \(K \le 10^8\).
  • Subtask 3 (\(40\%\) số điểm): \(K \le 10^{16}\).

2. Chạy trốn tình yêu

Điểm: 30 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: CHASE.INP Output: CHASE.OUT

Trong lúc đang rong ruổi khắp Hà Nội \(36\) phố phường, Hiếu đi lạc vào "Mê cung kì lạ". Mê cung gồm \(M\) căn phòng được đánh số từ \(0\) đến \(M-1\). Để rời khỏi mê cung, Hiếu phải thoát khỏi sự rượt đuổi của "Tình Yêu" - một thực thể bí ẩn trong mê cung.

Điều "kì lạ" trong mê cung này là việc di chuyển từ một phòng sang phòng tiếp theo được quy định hoàn toàn khác nhau đối với mỗi người. Với Hiếu, việc di chuyển được đặc trưng bởi một biến \(h\). Từ phòng \(x\) bất kỳ, phòng tiếp theo mà Hiếu đi tới sẽ là phòng \(f(x) = (x + h) \pmod{M}\). Với "Tình Yêu", từ phòng \(x\) nó chỉ có thể đi đến phòng \(g(x) = (x + t) \pmod{M}\).

Ban đầu (tại giây thứ \(0\)), Hiếu rơi vào phòng \(x_h\), còn "Tình Yêu" ở phòng \(x_t\). Cả hai bắt đầu di chuyển đồng thời. Gọi biến \(x_h, x_t\) lần lượt là vị trí phòng hiện tại của Hiếu và Tình Yêu.
Sau mỗi giây:

  • Từ phòng \(x_h\), Hiếu đi tới \(f(x_h)\) (tức gán \(x_h \leftarrow f(x_h)\)).
  • Trong khi đó, Tình Yêu sẽ đi hai bước liên tiếp từ phòng \(x_t\) sang phòng \(g(g(x_t))\) (tức gán \(x_t \leftarrow g(g(x_t))\)).

Nếu đến một thời điểm nào đó, Hiếu và Tình Yêu cùng bước vào một căn phòng thì cuộc rượt đuổi kết thúc. Ngược lại, công cuộc "Chạy trốn tình yêu" của Hiếu sẽ diễn ra vô tận.

Yêu cầu: Hãy tính thời điểm đầu tiên (số giây) mà Hiếu và Tình Yêu gặp nhau, hoặc xác định nếu điều này không bao giờ xảy ra.

Input

Đọc từ tệp văn bản CHASE.INP:

  • Một dòng duy nhất chứa 5 số nguyên \(M, x_h, x_t, h\) và \(t\) cách nhau một khoảng trắng (\(1 \le M \le 10^{18}\); \(0 \le x_h, x_t < M\); \(0 \le h, t < M\)).

Output

Ghi ra tệp văn bản CHASE.OUT:

  • Một số nguyên duy nhất là số giây trôi qua cho đến khi Hiếu và Tình Yêu chạm mặt nhau lần đầu tiên. Nếu họ không bao giờ gặp được nhau, in ra -1.

Example

Test 1

Input 
10 2 8 3 1
Output 
6
Note

Mê cung có 10 phòng.
Hiếu đi theo quy luật \(f(x) = (x + 3) \pmod{10}\).
Tình Yêu đi theo quy luật \(g(x) = (x + 1) \pmod{10}\), nhưng mỗi giây nhảy 2 bước.

Xuất phát tại giây thứ 0: Hiếu ở phòng 2, Tình Yêu ở phòng 8.

  • Giây thứ 1: Hiếu \(\to f(2)=5\). Tình Yêu \(\to g(g(8))=0\).
  • Giây thứ 2: Hiếu \(\to f(5)=8\). Tình Yêu \(\to g(g(0))=2\).
  • Giây thứ 3: Hiếu \(\to f(8)=1\). Tình Yêu \(\to g(g(2))=4\).
  • Giây thứ 4: Hiếu \(\to f(1)=4\). Tình Yêu \(\to g(g(4))=6\).
  • Giây thứ 5: Hiếu \(\to f(4)=7\). Tình Yêu \(\to g(g(6))=8\).
  • Giây thứ 6: Hiếu \(\to f(7)=0\). Tình Yêu \(\to g(g(8))=0\).

Vậy sau đúng 6 giây, cả hai gặp nhau ở phòng số 0.

Test 2

Input 
10 2 7 2 1
Output 
-1
Note

Mỗi giây Hiếu tiến tới 2 phòng (\(h=2\)). Tình Yêu tiến 2 bước (mỗi bước \(t=1\)) nên tổng cộng cũng tiến 2 phòng mỗi giây.
Khoảng cách giữa họ luôn không đổi là 5 phòng (trên vòng tròn). Do đó họ không bao giờ gặp nhau.

Scoring

  • Subtask 1 (\(30\%\) số điểm): \(M \le 10^6\).
  • Subtask 2 (\(30\%\) số điểm): \(M \le 10^9\).
  • Subtask 3 (\(40\%\) số điểm): \(M \le 10^{18}\).

3. Quà Đài Loan

Điểm: 40 (p) Thời gian: 1.0s Bộ nhớ: 512M Input: GIFT.INP Output: GIFT.OUT

Sau khi thi đấu xuất sắc và trở về từ kỳ thi ICPC APAC 2026 tại Đài Loan với tấm Huy Chương Đồng, Quang quyết định dạo quanh khu chợ đêm Đào Viên để mua quà lưu niệm cho các bạn trong đội tuyển.

Trong cửa hàng có \(N\) món đồ lưu niệm, món thứ \(i\) có khối lượng là \(W_i\) và mang lại lượng niềm vui (có thể đo đếm được ?!) là \(V_i\). Tiền thì không thành vấn đề, Quang dư sức mua hết cả \(N\) món đồ trong tiệm, nhưng vali của Quang chỉ có thể chứa được tổng khối lượng tối đa là \(M\).

Cửa hàng có một chương trình khuyến mãi cho những thí sinh có thành tích tốt tại ICPC APAC 2026: tặng ngay \(K\) thẻ "Nhân đôi niềm vui". Khi sử dụng một thẻ này lên một món đồ bất kỳ mà Quang mua, giá trị niềm vui \(V_i\) của món đó sẽ lập tức được tăng lên gấp đôi.

Tuy nhiên, mỗi món đồ chỉ được phép áp dụng thẻ nhiều nhất một lần. Thẻ này không làm thay đổi khối lượng \(W_i\) của món đồ. Quang có thể quyết định dùng hết, dùng một phần hoặc không dùng thẻ nào trong số \(K\) thẻ được tặng.

Yêu cầu: Hãy giúp Quang chọn các món đồ để cho vào vali và phân bổ \(K\) thẻ "Nhân đôi niềm vui" sao cho tổng khối lượng các món đồ không vượt quá \(M\), và tổng giá trị niềm vui mang về là lớn nhất có thể.

Input

Đọc từ tệp văn bản GIFT.INP:

  • Dòng đầu tiên chứa ba số nguyên không âm \(N, M, K\) (\(1 \le N \le 2000\); \(1 \le M \le 2000\); \(0 \le K \le 5\)).
  • \(N\) dòng tiếp theo, dòng thứ \(i\) chứa hai số nguyên dương \(W_i\) và \(V_i\) (\(1 \le W_i \le M\); \(1 \le V_i \le 10^7\)) lần lượt là khối lượng và giá trị niềm vui của món đồ thứ \(i\).

Output

Ghi ra tệp văn bản GIFT.OUT:

  • Một số nguyên duy nhất là tổng giá trị niềm vui lớn nhất mà Quang có thể đạt được.

Example

Test 1

Input 
3 5 1
4 10
3 8
2 12
Output 
32
Note

Quang có vali sức chứa \(M=5\) và \(K=1\) thẻ nhân đôi.
Quang quyết định chọn mua món 2 (\(W_2=3, V_2=8\)) và món 3 (\(W_3=2, V_3=12\)).
Quang dùng thẻ nhân đôi cho món 3 \(\implies\) Niềm vui món 3 thành \(12 \times 2 = 24\).
Tổng khối lượng: \(3 + 2 = 5 \le 5\) (Hợp lệ).
Tổng giá trị niềm vui: \(8 + 24 = 32\).

Test 2

Input 
4 10 2
4 10
3 8
5 12
6 20
Output 
60
Note

Quang có vali \(M=10\) và \(K=2\) thẻ.
Quang chọn mua món 1 (\(W_1=4, V_1=10\)) và món 4 (\(W_4=6, V_4=20\)).
Tổng khối lượng: \(4 + 6 = 10 \le 10\) (Hợp lệ).
Quang dùng cả 2 thẻ cho 2 món này \(\implies\) Giá trị món 1 thành 20, món 4 thành 40.
Tổng niềm vui: \(20 + 40 = 60\).

Scoring

  • Subtask 1 (\(20\%\) số điểm): \(N \le 20, M \le 100\).
  • Subtask 2 (\(30\%\) số điểm): \(K = 0\).
  • Subtask 3 (\(20\%\) số điểm): \(N \le 100, M \le 1000, K \le 2\).
  • Subtask 4 (\(30\%\) số điểm): Không có ràng buộc gì thêm.