Chung kết Olympic Tin học Miền Trung - Tây Nguyên 2026 - Bảng Siêu Cúp

Bạn đang tham gia trò chơi “đoán số hay, rinh lộc ngay” với cơ hội nhận về giải thưởng vô cùng hấp dẫn. Để trở thành người thắng cuộc, bạn cần vượt qua tất cả \(P\) vòng chơi. Ở mỗi vòng chơi, chương trình có một con số bí mật \(V\) và bạn cần tìm ra ẩn số này. Trước khi trò chơi bắt đầu, ban tổ chức thông báo một số nguyên \(D\) và cho bạn gợi ý: Ẩn số cần tìm \(V\) trong tất cả \(P\) vòng chơi đều là một số nguyên không nhỏ hơn \(1\) và không lớn hơn \(D\). Mỗi vòng chơi gồm một số lượt đoán số. Mỗi lượt đoán số diễn ra như sau: Bạn dự đoán một số nguyên \(H \in [1, 10^9]\). Ngay sau đó, ban tổ chức sẽ cho bạn biết các thông tin sau:

• Số \(H\) bạn đưa ra có trùng khớp với ẩn số \(V\) của chương trình hay không.
• Nếu không trùng khớp, bạn sẽ nhận được thông báo một giá trị \(X\) được xác định theo quy tắc sau:
  • Đặt \(X = \max(0, 1 - \frac{|V - H|}{V})\)
  • Làm tròn giá trị \(X\) tới chính xác ba chữ số ở phần thập phân.

Bạn được coi là chiến thắng một vòng chơi nếu tìm ra ẩn số của chương trình sau không quá \(69\) lượt đoán số. Vượt qua cả \(P\) vòng chơi, bạn sẽ nhận được giải thưởng từ chương trình. Số lượt dự đoán số càng ít, giải thưởng của bạn càng lớn.

Tương tác

Đầu tiên, chương trình của bạn đọc hai số nguyên \(P\) và \(D\) (\(1 \le P \le 1000; 1 \le D \le 10^9\)) lần lượt là số vòng chơi và giới hạn \(D\) được thông báo trước khi trò chơi bắt đầu.

Tiếp theo, mỗi lượt đoán số diễn ra như sau:

• Trước tiên, bạn in ra số nguyên \(H\) (\(1 \le H \le 10^9\)) là con số bạn dự đoán.
• Sau đó, bạn đọc vào một số nguyên \(R\) (\(R \in \{-1, 0, 1\}\)) thể hiện phản hồi từ chương trình, cụ thể như sau:
  • \(R = 1\): giá trị \(H\) trùng khớp với ẩn số \(V\) cần tìm và bạn đã chiến thắng vòng chơi. Khi đó, chương trình của bạn cần chuyển sang vòng chơi tiếp theo, hoặc kết thúc ngay nếu đây là vòng chơi cuối cùng.
  • \(R = -1\): giá trị \(H\) bạn đưa ra không hợp lệ, hoặc bạn đã đoán vượt quá số lần cho phép. Khi đó, chương trình của bạn cần kết thúc ngay.
  • \(R = 0\): giá trị \(H\) chưa trùng khớp với ẩn số cần tìm. Khi đó, bạn đọc vào một số thực \(X\) được tính theo quy tắc ở trên.

Lưu ý: Sau khi bạn in ra một số nguyên, bạn cần in ra ký tự xuống dòng và thực hiện thao tác flush luồng ra chuẩn bằng cách gọi các lệnh sau:

• fflush(stdout) hoặc cout.flush() trong C++;
• System.out.flush() trong Java;
• stdout.flush() trong Python;

Chấm điểm

Nếu bạn không chiến thắng toàn bộ \(P\) vòng chơi, bạn được \(0\) điểm.
Ngược lại, gọi \(Q\) là số lượt đoán số nhiều nhất bạn cần sử dụng trong một vòng chơi, số điểm của bạn được tính như sau:

• Nếu \(Q \le 25\), bạn được \(100\%\) số điểm của test.
• Nếu \(25 < Q \le 36\), bạn được \(((36 - Q)^2 \cdot 0.3 + (36 - Q) \cdot 1.7 + 45)\%\) số điểm của test.
• Nếu \(36 < Q \le 69\), bạn được \(((96 - Q)^2 \cdot 0.01 + 9)\%\) số điểm của test.

Scoring

• Subtask \(1\) (\(4\%\) số điểm): \(D = 20\).
• Subtask \(2\) (\(8\%\) số điểm): \(D = 100\).
• Subtask \(3\) (\(8\%\) số điểm): \(D = 1000\).
• Subtask \(4\) (\(16\%\) số điểm): \(D = 10^6\).
• Subtask \(5\) (\(28\%\) số điểm): \(D = 5 \cdot 10^8\).
• Subtask \(6\) (\(36\%\) số điểm): \(D = 10^9\).

Example

Nhằm bồi dưỡng tài năng công nghệ thông tin và thử nghiệm nền tảng trực tuyến mới, Việt đứng ra tổ chức một kỳ thi lập trình với những quy chế tính điểm đặc biệt. Thể lệ của kỳ thi được quy định chi tiết như sau:

• Kỳ thi diễn ra trong vòng \(T\) phút, bao gồm \(N\) bài toán. Hệ số điểm cơ bản của toàn bộ kỳ thi là \(S\).
• Bài toán thứ \(i\) có hệ số điểm riêng của bài là \(P_i\). Điểm số tối đa mà một thí sinh có thể đạt được cho bài toán này là \(\Sigma_i = S \cdot P_i\).
• Hệ thống áp dụng cơ chế giảm điểm theo thời gian. Cụ thể, nếu thí sinh hoàn thành bài toán thứ \(i\) tại thời điểm \(t_i\) (\(1 \le t_i \le T\), tính bằng phút kể từ lúc kỳ thi bắt đầu), điểm số nhận được cho bài toán đó sẽ là \(\Sigma_i - t_i \cdot P_i\). Nói cách khác, sau mỗi một phút trôi qua, số điểm khả thi của bài toán thứ \(i\) sẽ bị trừ đi một lượng bằng đúng \(P_i\).

Hàn là một thí sinh tham gia kỳ thi này. Với kinh nghiệm thi đấu phong phú, sau khi đọc toàn bộ đề, Hàn ước lượng được chính xác năng lực của bản thân đối với từng bài toán:

• Hàn thi đấu với độ tập trung cao độ: mỗi khi bắt tay vào giải một bài toán, cậu sẽ làm liền mạch cho đến khi hoàn thành bài đó rồi mới chuyển sang bài khác, không có khoảng nghỉ và không giải song song nhiều bài cùng lúc.
• Hàn cần đúng \(a_i\) phút để hoàn thành trọn vẹn bài toán thứ \(i\). Vì thế, nếu cậu làm các bài trước đó trong vòng \(t\) phút và bắt đầu giải bài \(i\), cậu sẽ hoàn thành tại thời điểm \(t + a_i\).

Yêu cầu: Với giới hạn thời gian \(T\) phút của kỳ thi, hãy giúp Hàn xây dựng chiến thuật: chọn ra một tập các bài toán và sắp xếp thứ tự giải chúng sao cho tổng số điểm giành được là lớn nhất có thể.

Input

• Dòng đầu tiên chứa ba số nguyên \(N, T\), và \(S\) (\(1 \le N \le 5 \cdot 10^5; 1 \le T \le 2000; 1 \le S \le 10^9\)) lần lượt là số lượng bài toán, thời lượng kỳ thi và hệ số điểm cơ bản.
• Dòng thứ hai chứa \(N\) số nguyên dương \(a_1, a_2, \dots, a_N\) (\(a_i \le T\) với mọi \(1 \le i \le N\)), trong đó \(a_i\) là thời gian Hàn cần để hoàn thành bài toán thứ \(i\).
• Dòng thứ ba chứa \(N\) số nguyên dương \(P_1, P_2, \dots, P_N\) (\(P_i \le T\) với mọi \(1 \le i \le N\)), trong đó \(P_i\) là hệ số điểm của bài toán thứ \(i\).

Output

• Dòng đầu tiên in ra hai số nguyên \(k\) và \(X\), lần lượt là số bài toán Hàn lựa chọn để giải và tổng số điểm tối đa đạt được.
• Dòng thứ hai in ra \(k\) số nguyên phân biệt \(p_1, p_2, \dots, p_k\) (\(1 \le p_i \le N\)) thể hiện thứ tự các bài toán mà Hàn sẽ thực hiện. Trong trường hợp \(k = 0\), thí sinh bỏ trống dòng này.
• Trong trường hợp có nhiều chiến thuật khác nhau cùng đạt được số điểm tối đa, bạn được phép in ra một phương án bất kỳ.

Example

6 120 250
1 2 3 8 10 13
2 4 5 9 11 14

6 10298
1 2 3 4 5 6

Scoring

• Subtask \(1\) (\(12\) điểm): \(P_i = P_1\) với mọi \(i\).
• Subtask \(2\) (\(15\) điểm): \(N \le 20\).
• Subtask \(3\) (\(21\) điểm): \(a_1 + a_2 + \dots + a_n \le T \le S\).
• Subtask \(4\) (\(25\) điểm): \(N \le 5000\).
• Subtask \(5\) (\(27\) điểm): Không có ràng buộc nào thêm.

Lưu ý: Kết quả chấm các Subtask 1, 3 và 5 sẽ được ẩn đi trong quá trình thi.

Trong câu lạc bộ nghệ thuật của trường, đạo diễn đang dàn dựng một tiết mục đôi mang tên Vòng Xoay. Điểm nhấn của tiết mục là một dải lụa sân khấu có độ dài đúng bằng \(1\) mét, được buộc vào tay của cả hai người và luôn được giữ căng trong suốt màn biểu diễn để tạo nên các đường chuyển động mềm mại, chính xác.

Biên đạo của tiết mục quy định rằng tại mọi thời điểm luôn có đúng một người giữ vai trò người trụ, còn người kia là người xoay hoạt động như sau:

• Người trụ đứng yên tại chỗ để giữ điểm tựa cho động tác.
• Người xoay chuyển động liên tục theo chiều kim đồng hồ quanh người trụ với tốc độ góc \(90^\circ\) mỗi giây.
• Vì dải lụa luôn căng và có độ dài đúng bằng \(1\) mét, khoảng cách giữa hai người luôn bằng \(1\) mét tại mọi thời điểm.

Việt và Hàn là hai diễn viên chính của buổi biểu diễn. Trên mặt phẳng tọa độ, ban đầu Việt đứng tại \((0, 0)\) còn Hàn đứng tại \((1, 0)\). Khi màn biểu diễn bắt đầu, Việt là người xoay, còn Hàn là người trụ.

Để tiết mục trở nên hấp dẫn hơn, đạo diễn chèn vào kịch bản một số thời điểm đổi vai. Tại một thời điểm đổi vai:

• Người đang là người xoay lập tức trở thành người trụ.
• Người đang là người trụ lập tức trở thành người xoay.

Việc đổi vai diễn ra tức thời và không tốn thời gian. Toàn bộ tiết mục kéo dài đúng \(T\) giây.

Quá trình hoàn thiện tiết mục diễn ra qua \(N\) buổi tập. Ở buổi tập thứ \(i\), đạo diễn bổ sung thêm đúng một mốc đổi vai mới vào kịch bản như sau:

• Ở buổi tập thứ \(1\), kịch bản có một lần đổi vai tại thời điểm \(b_1\).
• Ở buổi tập thứ \(2\), kịch bản có các lần đổi vai tại các thời điểm \(b_1, b_2\).
• ...
• Ở buổi tập thứ \(i\), kịch bản có các lần đổi vai tại các thời điểm \(b_1, b_2, \dots, b_i\).

Lưu ý:

• Trong mỗi buổi tập, các thời điểm đổi vai là đôi một khác nhau.
• Dãy \(b_1, b_2, \dots, b_N\) trong input biểu diễn thứ tự các mốc được thêm vào qua từng buổi tập mà không phải thứ tự thời gian xuất hiện trên sân khấu. Vì vậy, trong trường hợp tổng quát, không đảm bảo là \(b_1 < b_2 < \dots < b_N\).
• Nếu có một lần đổi vai tại thời điểm \(t\), thì việc đổi vai xảy ra đúng tại thời điểm đó.
• Nói cách khác, chuyển động trong khoảng thời gian từ \(k - 1\) đến \(k\) vẫn sử dụng vai trò trước khi đổi; còn chuyển động sau thời điểm \(k\) sử dụng vai trò sau khi đổi.
• Ví dụ, nếu trong \(3\) giây đầu không có lần đổi vai nào, thì vị trí của Việt lần lượt sau \(1, 2, 3\) giây là \((1, 1), (2, 0), (1, -1)\).

Yêu cầu: Với mỗi buổi tập, hãy xác định tọa độ cuối cùng của Việt sau đúng \(T\) giây nếu biểu diễn theo kịch bản của buổi tập đó.

Input

• Dòng đầu tiên chứa hai số nguyên dương \(N\) và \(T\) (\(1 \le N \le 10^5, N + 1 \le T \le 5 \cdot 10^5\)).
• Dòng thứ \(i\) trong số \(N\) dòng tiếp theo chứa một số nguyên \(b_i\) (\(1 \le b_i \le T - 1\)).

Output

• Ghi ra \(N\) dòng: Dòng thứ \(i\), in hai số nguyên \(x\) và \(y\) là tọa độ của Việt sau đúng \(T\) giây trong kịch bản của buổi tập thứ \(i\).

Example

2 6
3
2

1 -1
3 1

Subtask

• Subtask \(1\) (\(20\) điểm): \(N \le 2000, T \le 2000\).
• Subtask \(2\) (\(20\) điểm): \(b_1 < b_2 < \dots < b_N\).
• Subtask \(3\) (\(30\) điểm): \(T \le 5 \cdot 10^4\).
• Subtask \(4\) (\(30\) điểm): Không có ràng buộc nào thêm.

Trong một tiết học đặc biệt tại phòng lab An ninh mạng của trường VH, thầy giáo tổ chức trò chơi "Cấu hình tối ưu". Thầy giáo đã thiết lập một mạng lưới giả lập gồm \(N\) nút mạng và \(M\) kết nối vô hướng. Nhiệm vụ của học sinh là tham gia lập trình điều khiển một robot ảo mang tên ClawdBot di chuyển và thu hoạch điểm trên mạng lưới này nhằm đạt được điểm số đánh giá cao nhất.

Quá trình thu hoạch điểm yêu cầu học sinh cung cấp cho hệ thống hai thông tin: (1) bản đồ cấu hình chế độ hoạt động của các nút và (2) tuyến đường di chuyển của robot. Cụ thể, học sinh cần thiết lập như sau:

1. Cấu hình mạng: Học sinh cài đặt chế độ hoạt động của \(N\) nút trên mạng lưới. Mỗi nút phải được gán một trong hai chế độ: 0 (Cực âm - Cathode) hoặc 1 (Cực dương - Anode).
2. Điều khiển ClawdBot: Học sinh chọn một nút bất kỳ làm điểm xuất phát và lập trình cho ClawdBot di chuyển liên tiếp qua tối đa \(K\) kết nối (bước đi).

Khi ClawdBot di chuyển giữa hai nút \(u\) và \(v\), hệ thống tính điểm được quy định như sau:

• Nếu \(u\) và \(v\) được cấu hình khác chế độ, ClawdBot khai thác cạnh \((u, v)\) thành công và đem lại \(B_{u,v}\) điểm thưởng.
• Nếu \(u\) và \(v\) được cấu hình cùng chế độ, hệ thống sẽ đánh dấu bước di chuyển này là bất thường và tính phạt \(P_{u,v}\) điểm.

Lưu ý: Việc kiểm tra và tính điểm thưởng/phạt này chỉ diễn ra một lần duy nhất trên mỗi cạnh. Nếu robot đi qua một kết nối từ lần thứ hai trở đi, điểm số của học sinh không bị ảnh hưởng.

Yêu cầu: Hãy tìm một phương án cấu hình cho \(N\) nút và một lộ trình di chuyển (có độ dài không quá \(K\)) cho robot ClawdBot sao cho tổng số điểm thu được là lớn nhất.

Đây là một bài output-only (chỉ nộp kết quả đầu ra). Thí sinh tải bộ dữ liệu đầu vào tại đây: ALTPATH_input-only.zip

Input

Sau khi giải nén, bạn có các file đầu vào được đặt tên là test01.inp, test02.inp, ..., mỗi file mô tả một test theo định dạng sau:

• Dòng đầu tiên chứa ba số nguyên dương \(N, M, K\) (\(2 \le N \le 1000\); \(1 \le M \le 50000\); \(1 \le K \le 10000\)).
• Mỗi dòng trong số \(M\) dòng tiếp theo chứa 4 số nguyên \(u, v, B_{u,v}, P_{u,v}\) mô tả một kết nối giữa nút \(u\) và nút \(v\), cùng với điểm thưởng \(B_{u,v}\) và điểm phạt \(P_{u,v}\) (\(1 \le u, v \le N, u \neq v; 0 \le B_{u,v}, P_{u,v} \le 10^6\)).
• Đồ thị đảm bảo không có khuyên và giữa hai nút có tối đa một kết nối.

Output

Với mỗi file đầu vào testX.inp bạn cần nộp file đầu ra testX.out tương ứng theo định dạng:

• Dòng 1: Một chuỗi nhị phân độ dài \(N\) (chỉ gồm ký tự 0 và 1). Ký tự thứ \(i\) thể hiện chế độ hoạt động của nút thứ \(i\).
• Dòng 2: Số nguyên \(L\) (\(0 \le L \le K\)) là số lượng bước di chuyển mà ClawdBot thực hiện.
• Dòng 3: \(L + 1\) số nguyên thể hiện lộ trình của ClawdBot, gồm các nút đi qua theo thứ tự. Hai nút liền kề phải có kết nối trực tiếp với nhau trong mạng lưới.

Mỗi lần nộp bài bạn có thể nộp một hoặc nhiều file đầu ra, bạn cần nén các file đầu ra này lại thành submission.zip để nộp. Ở mục chọn ngôn ngữ của trang nộp bài, chọn "Output".

Example

4 4 3
1 2 10 5
2 3 20 10
3 4 30 5
4 1 40 5

0100
3
1 2 3 4

Subtask

Ràng buộc chung: \(N \le 1000, M \le 50000, K \le 10000\).

• Subtask 1 (20 điểm): \(N \le 20, M \le 50, K \le 15\).
• Subtask 2 (30 điểm): \(P_{u,v} = 0\) với mọi \(u, v\) và dữ liệu vào đảm bảo đồ thị là hai phía.
• Subtask 3 (50 điểm): Không có ràng buộc gì thêm.

Chấm điểm

Đối với mỗi test, bạn sẽ nhận 0 điểm nếu đầu ra không hợp lệ. Một số trường hợp mà output được xem là không hợp lệ:

• Chuỗi cấu hình không có độ dài đúng bằng \(N\) hoặc chứa ký tự khác 0 và 1.
• Số lượng bước di chuyển \(L < 0\) hoặc \(L > K\).
• Lộ trình chứa nút không hợp lệ (\(< 1\) hoặc \(> N\)), hoặc hai nút liên tiếp trong lộ trình không có kết nối vật lý.

Ngược lại, gọi:

• \(C\) là tổng điểm thu hoạch phương án bạn đạt được.
• \(J\) là tổng điểm trong phương án tốt nhất mà Ban Giám Khảo biết.
• \(A\) là điểm tối đa của test. Điểm bạn nhận được trên test đó được tính bằng công thức: \(max\left(0, \left(\frac{C}{J}\right)^3\right) \cdot A\)