JOI 2024 - Open Contest

Bộ đề bài

Trở lại kỳ thi
# Bài tập Điểm Thời gian: Giới hạn bộ nhớ
1 JOI 2024 - Examination 2 100 (p) 2.0s 1G
2 JOI 2024 - Heat Stroke 100 (p) 2.0s 2G
3 JOI 2024 - Library 3 100 (p) 1.0s 1G

1. JOI 2024 - Examination 2

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

JOI-kun học tại trường trung học IOI và sắp tham gia kỳ thi cuối kỳ. Bài thi kiểm tra khả năng tính đúng giá trị của một hàm IOI. Hàm IOI là một xâu được tạo bằng một trong sáu quy tắc dưới đây, do trường IOI định nghĩa. Mỗi hàm ánh xạ các số nguyên từ \(1\) đến \(10^9\) thành một trong hai giá trị logic True hoặc False.

  1. Với số nguyên \(a\) trong đoạn từ \(1\) đến \(10^9\), xâu [a] là một hàm IOI; ở đây a là biểu diễn thập phân của số \(a\). Hàm này trả về True cho các số lớn hơn hoặc bằng \(a\), và False cho các số nhỏ hơn \(a\).
  2. Nếu f là một hàm IOI thì (f) cũng là một hàm IOI. Với mỗi số đầu vào, hàm này trả về cùng giá trị với f.
  3. Nếu f là một hàm IOI thì !f cũng là một hàm IOI. Hàm này trả về False cho các số mà f trả về True, và ngược lại.
  4. Nếu f và g là các hàm IOI thì f&g cũng là một hàm IOI. Hàm này trả về True khi cả f và g đều trả về True, và False trong các trường hợp còn lại.
  5. Nếu f và g là các hàm IOI thì f^g cũng là một hàm IOI. Hàm này trả về True khi đúng một trong hai hàm f, g trả về True, và False trong các trường hợp còn lại.
  6. Nếu f và g là các hàm IOI thì f|g cũng là một hàm IOI. Hàm này trả về True khi ít nhất một trong hai hàm f, g trả về True, và False trong các trường hợp còn lại.

Nếu một xâu có thể được tạo bằng nhiều quy tắc, chọn quy tắc có số thứ tự lớn nhất làm bước tạo hàm cuối cùng để xác định giá trị của hàm. Chẳng hạn, với [1]&[2]|[3], áp dụng quy tắc \(6\) cho f = [1]&[2], g = [3], thay vì áp dụng quy tắc \(4\) cho f = [1], g = [2]|[3]. Ngoài ra, khi áp dụng quy tắc \(4\), \(5\) hoặc \(6\), chọn f dài nhất có thể. Chẳng hạn, với [4]^[5]^[6], áp dụng quy tắc \(5\) cho f = [4]^[5], g = [6], thay vì chọn f = [4], g = [5]^[6].

Để ôn thi, JOI-kun đã chuẩn bị một hàm IOI \(S\) có độ dài \(N\) và muốn luyện xác định giá trị mà hàm này trả về cho \(Q\) số nguyên \(X_1,X_2,\ldots,X_Q\). Biết bạn thành thạo về hàm IOI, cậu nhờ bạn viết một lời giải mẫu.

Cho \(N,Q,S\) và \(X_1,X_2,\ldots,X_Q\), hãy xác định giá trị logic mà hàm IOI \(S\) trả về cho từng số \(X_i\).

Dữ liệu vào

Đọc từ đầu vào chuẩn theo định dạng:

N Q
S
X_1
X_2
...
X_Q

Dữ liệu ra

Xuất \(Q\) dòng ra đầu ra chuẩn. Dòng thứ \(i\) (\(1\le i\le Q\)) chứa giá trị logic True hoặc False mà hàm IOI \(S\) trả về cho \(X_i\).

Ràng buộc

  • \(1\le N\le 1\,000\,000\).
  • \(1\le Q\le 200\,000\).
  • \(S\) là một hàm IOI có độ dài \(N\).
  • \(1\le X_i\le 10^9\) với \(1\le i\le Q\).
  • \(N,Q,X_i\) (\(1\le i\le Q\)) đều là số nguyên.

Phân nhóm

Mọi nhóm đều tuân theo các ràng buộc chung ở trên.

Nhóm Điểm Ràng buộc bổ sung
1 5 \(S\) không chứa ký tự & hoặc |.
2 20 \(Q=1\).
3 10 \(N\le 10\,000\).
4 6 \(S\) không chứa ký tự ! hoặc ^.
5 12 Mỗi khi áp dụng quy tắc \(4\) hoặc \(6\) trong quá trình tạo \(S\), ít nhất một trong hai hàm f, g phải là hàm IOI được tạo bằng quy tắc \(1\), tức có dạng [a].
6 20 \(N\le 400\,000\).
7 27 Không có ràng buộc bổ sung.

Ví dụ

Ví dụ 1

Input 
15 5
(![2]|[3])&![4]
1
2
3
4
5
Output 
True
False
True
False
False
Note

Khi tạo \(S\) theo các quy tắc trong đề, một số hàm IOI xuất hiện trong quá trình đó có các giá trị sau tại những số \(X_i\) (\(1\le i\le Q\)):

\(X_i\) ![2] [3] ![2]|[3] ![4] (![2]|[3])&![4]
1 True False True True True
2 False False False True False
3 False True True True True
4 False True True False False
5 False True True False False

Ví dụ này thỏa mãn ràng buộc của các nhóm \(3,6,7\).

Ví dụ 2

Input 
20 4
(!![23])^((([116])))
54
1
200
89
Output 
True
False
False
True
Note

Ví dụ này thỏa mãn ràng buộc của các nhóm \(1,3,5,6,7\).

Ví dụ 3

Input 
32 4
[2]|[5]&[1]|(([1000000000])|[7])
4
10
6
1
Output 
True
True
True
False
Note

Ví dụ này thỏa mãn ràng buộc của các nhóm \(3,4,6,7\).

Nguồn

JOI Open Contest 2024, bài Examination 2, tác giả Ryomei Sugai.

Bản dịch tiếng Việt từ đề của JCIOI (Ủy ban Olympic Tin học Quốc tế Nhật Bản), theo giấy phép CC BY-SA 4.0.

2. JOI 2024 - Heat Stroke

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

Đảo JOI gồm \(L\) khu vực, đánh số từ \(1\) đến \(L\) theo thứ tự từ tây sang đông. Trên đảo có \(L-1\) con đường, đánh số từ \(1\) đến \(L-1\). Đường \(i\) (\(1\le i\le L-1\)) nối hai khu vực \(i\) và \(i+1\) theo cả hai chiều.

Trong hình, các ô lần lượt biểu diễn khu vực \(1,2,3,\ldots,L\); đường \(1\) nối khu vực \(1\) với khu vực \(2\), đường \(2\) nối khu vực \(2\) với khu vực \(3\).

Olympic Tin học Quốc tế IOI 20XX dự kiến được tổ chức trên đảo JOI. Tuy nhiên, hòn đảo nổi tiếng với thời tiết cực kỳ nóng. Nguy cơ sốc nhiệt rất cao, đặc biệt với các thí sinh nước ngoài chưa quen khí hậu nóng. Vì vậy, ban tổ chức quyết định thực hiện các biện pháp sau:

  • Với mỗi khu vực \(i\) (\(1\le i\le L\)), chuẩn bị một bệnh viện có sức chứa \(C_i\) người. Có thể có \(C_i=0\).
  • Khi một người trên đường \(x\) (\(1\le x\le L-1\)) bị sốc nhiệt, đưa người đó tới bệnh viện ở khu vực \(x\) hoặc \(x+1\) còn chỗ. Nếu cả hai bệnh viện đều còn chỗ, có thể chọn bất kỳ bệnh viện nào trong hai bệnh viện đó. Nếu cả hai đều đã đầy, đưa bệnh nhân bằng trực thăng tới một bệnh viện đa khoa ở ngoài đảo.

Việc sử dụng trực thăng rất tốn kém, nên ban tổ chức muốn ước lượng số bệnh nhân lớn nhất có thể phải vận chuyển bằng trực thăng. Họ xét kịch bản sau:

  • Trước khi IOI diễn ra, tất cả bệnh viện đều không có bệnh nhân.
  • Trong thời gian tổ chức IOI, có \(N\) người bị sốc nhiệt trên đảo. Bệnh nhân thứ \(j\) (\(1\le j\le N\)) xuất hiện trên đường \(X_j\).
  • Với mỗi \(1\le j\le N-1\), khi bệnh nhân thứ \(j+1\) bị sốc nhiệt thì bệnh nhân thứ \(j\) và mọi bệnh nhân trước đó đã được đưa tới bệnh viện. Do triệu chứng sốc nhiệt nghiêm trọng, không bệnh nhân nào rời bệnh viện trong suốt thời gian tổ chức IOI.

Cho số khu vực, thông tin bệnh viện và các bệnh nhân, hãy tính số bệnh nhân lớn nhất có thể phải vận chuyển bằng trực thăng trong kịch bản trên.

Dữ liệu vào

Đọc từ đầu vào chuẩn theo định dạng:

L
C_1 C_2 ... C_L
N
X_1 X_2 ... X_N

Dữ liệu ra

Xuất một dòng chứa số bệnh nhân lớn nhất có thể phải vận chuyển bằng trực thăng.

Ràng buộc

  • \(2\le L\le 8\,000\).
  • \(0\le C_i\le 8\,000\) với \(1\le i\le L\).
  • \(1\le N\le 8\,000\).
  • \(1\le X_j\le L-1\) với \(1\le j\le N\).
  • Tất cả giá trị đầu vào đều là số nguyên.

Phân nhóm

Mọi nhóm đều tuân theo các ràng buộc chung ở trên.

Nhóm Điểm Ràng buộc bổ sung
1 6 \(X_1\le X_2\le\cdots\le X_N\).
2 7 \(L\le 18\), \(N\le 18\) và \(C_i=1\) với mọi \(1\le i\le L\).
3 7 \(L\le 18\), \(N\le 100\) và \(C_i=1\) với mọi \(1\le i\le L\).
4 25 \(L\le 100\), \(N\le 100\) và \(C_i=1\) với mọi \(1\le i\le L\).
5 25 \(L\le 100\), \(N\le 100\).
6 10 \(L\le 600\), \(N\le 600\).
7 15 \(L\le 3\,500\), \(N\le 3\,500\).
8 5 Không có ràng buộc bổ sung.

Ví dụ

Ví dụ 1

Input 
3
1 1 1
3
1 2 2
Output 
1
Note

Có thể phải vận chuyển \(1\) bệnh nhân bằng trực thăng nếu xử lý như sau:

  1. Đưa bệnh nhân thứ \(1\) tới bệnh viện ở khu vực \(2\). Số bệnh nhân tại các khu vực \(1,2,3\) lần lượt là \(0,1,0\).
  2. Đưa bệnh nhân thứ \(2\) tới bệnh viện ở khu vực \(3\). Số bệnh nhân tại các khu vực \(1,2,3\) lần lượt là \(0,1,1\).
  3. Với bệnh nhân thứ \(3\), cả hai bệnh viện ở khu vực \(2,3\) đều đã đầy, nên phải đưa người đó bằng trực thăng tới bệnh viện đa khoa ngoài đảo.

Không có cách nào khiến từ \(2\) bệnh nhân trở lên phải đi bằng trực thăng, nên kết quả là \(1\). Ví dụ này thỏa mãn ràng buộc của tất cả các nhóm \(1,2,3,4,5,6,7,8\).

Ví dụ 2

Input 
6
1 1 1 1 1 1
7
1 3 5 4 2 2 3
Output 
3
Note

Có thể phải vận chuyển \(3\) bệnh nhân bằng trực thăng nếu xử lý như sau:

  1. Đưa bệnh nhân thứ \(1\) tới bệnh viện ở khu vực \(2\). Số bệnh nhân tại các khu vực \(1,2,3,4,5,6\) lần lượt là \(0,1,0,0,0,0\).
  2. Đưa bệnh nhân thứ \(2\) tới bệnh viện ở khu vực \(4\). Số bệnh nhân tại các khu vực \(1,2,3,4,5,6\) lần lượt là \(0,1,0,1,0,0\).
  3. Đưa bệnh nhân thứ \(3\) tới bệnh viện ở khu vực \(5\). Số bệnh nhân tại các khu vực \(1,2,3,4,5,6\) lần lượt là \(0,1,0,1,1,0\).
  4. Với bệnh nhân thứ \(4\), cả hai bệnh viện ở khu vực \(4,5\) đều đã đầy, nên phải vận chuyển bằng trực thăng tới bệnh viện đa khoa ngoài đảo.
  5. Đưa bệnh nhân thứ \(5\) tới bệnh viện ở khu vực \(3\). Số bệnh nhân tại các khu vực \(1,2,3,4,5,6\) lần lượt là \(0,1,1,1,1,0\).
  6. Với bệnh nhân thứ \(6\), cả hai bệnh viện ở khu vực \(2,3\) đều đã đầy, nên phải vận chuyển bằng trực thăng tới bệnh viện đa khoa ngoài đảo.
  7. Với bệnh nhân thứ \(7\), cả hai bệnh viện ở khu vực \(3,4\) đều đã đầy, nên phải vận chuyển bằng trực thăng tới bệnh viện đa khoa ngoài đảo.

Không có cách nào khiến từ \(4\) bệnh nhân trở lên phải đi bằng trực thăng, nên kết quả là \(3\). Ví dụ này thỏa mãn ràng buộc của các nhóm \(2,3,4,5,6,7,8\).

Ví dụ 3

Input 
6
4000 1 1 0 4000 1
5
1 1 2 3 5
Output 
1
Note

Ví dụ này thỏa mãn ràng buộc của các nhóm \(1,5,6,7,8\).

Ví dụ 4

Input 
5
1 2 2 2 1
8
2 3 2 1 4 1 2 3
Output 
2
Note

Ví dụ này thỏa mãn ràng buộc của các nhóm \(5,6,7,8\).

Ví dụ 5

Input 
10
2 2 2 2 2 2 2 2 2 2
18
1 3 5 7 9 2 4 6 8 1 3 5 7 9 2 4 6 8
Output 
3
Note

Ví dụ này thỏa mãn ràng buộc của các nhóm \(5,6,7,8\).

Nguồn

JOI Open Contest 2024, bài Heat Stroke, tác giả Hirotaka Yoneda và Masataka Yoneda.

Bản dịch tiếng Việt và hình từ đề của JCIOI (Ủy ban Olympic Tin học Quốc tế Nhật Bản), theo giấy phép CC BY-SA 4.0.

3. JOI 2024 - Library 3

Điểm: 100 (p) Thời gian: 1.0s Bộ nhớ: 1G Input: bàn phím Output: màn hình

Sau vài trăm năm, thành phố JOI đã trở thành phế tích. Nhà thám hiểm IOI-chan đang khảo sát khu vực từng có thư viện. Qua khảo sát, cô biết rằng:

  • Thư viện của thành phố JOI có một giá sách nằm ngang, gồm \(N\) vị trí đặt sách trên một hàng, đánh số từ \(0\) đến \(N-1\) từ trái sang phải. Mỗi vị trí đặt được đúng một quyển sách.
  • Trên giá có \(N\) quyển sách, đánh số từ \(0\) đến \(N-1\).
  • Một cách sắp xếp là một cách đặt toàn bộ \(N\) quyển sách vào \(N\) vị trí.
  • Có một cách sắp xếp đúng: tại vị trí \(i\) (\(0\le i\le N-1\)) đặt quyển sách \(B_i\). Các giá trị \(B_i\) đôi một khác nhau.

Vị trí của các quyển sách thường bị thay đổi. Người ta biết rằng thư viện đưa sách trở lại cách sắp xếp đúng bằng cách lặp lại thao tác sau:

Gọi \(x\) là quyển sách nằm ngoài cùng bên trái trong số các quyển đang không ở đúng vị trí. Gọi \(y\) là quyển sách hiện đang nằm tại vị trí mà quyển \(x\) phải nằm trong cách sắp xếp đúng. Hoán đổi vị trí của hai quyển \(x,y\).

IOI-chan tìm thấy những quyển sách cũ nhưng không xác định được cách sắp xếp đúng. Tuy nhiên, cô tìm thấy một chiếc máy cũ từng quản lý các thao tác trên giá sách. Khi gửi một cách sắp xếp \(N\) quyển sách cho máy, máy trả về số thao tác cần thực hiện để đưa toàn bộ sách từ cách sắp xếp đó về cách sắp xếp đúng. IOI-chan muốn xác định cách sắp xếp đúng bằng cách gửi các truy vấn cho máy. Vì máy đã cũ, cô chỉ được gửi nhiều nhất \(5\,000\) truy vấn.

Hãy viết chương trình nhận thông tin về giá sách và xác định cách sắp xếp đúng bằng không quá \(5\,000\) truy vấn.

Chi tiết cài đặt

Nộp một tệp library3.cpp, sử dụng chỉ thị #include "library3.h" và cài đặt hàm:

C++
void solve(int N);

Hàm này được gọi đúng một lần trong mỗi bộ kiểm thử. Tham số N là số quyển sách.

Trong library3.cpp, bạn có thể gọi hai hàm sau:

C++
int query(std::vector<int> a);
void answer(std::vector<int> b);

Hàm query gửi một truy vấn cho máy. Tham số a là mảng độ dài \(N\), mô tả cách sắp xếp: quyển sách a[i] được đặt tại vị trí \(i\) (\(0\le i\le N-1\)). Giá trị trả về là số thao tác cần thực hiện để đưa toàn bộ sách từ cách sắp xếp đã gửi về cách sắp xếp đúng.

Hàm answer báo cáo cách sắp xếp đúng. Tham số b là mảng độ dài \(N\), trong đó quyển sách b[i] được đặt tại vị trí \(i\) (\(0\le i\le N-1\)).

Các yêu cầu và trường hợp bị chấm sai:

Kết quả Điều kiện gây lỗi
Wrong Answer [1] Độ dài mảng a truyền cho query khác \(N\).
Wrong Answer [2] Có phần tử của a không nằm trong đoạn từ \(0\) đến \(N-1\).
Wrong Answer [3] Các phần tử của a không đôi một khác nhau.
Wrong Answer [4] Gọi query nhiều hơn \(5\,000\) lần.
Wrong Answer [5] Độ dài mảng b truyền cho answer khác \(N\).
Wrong Answer [6] Có phần tử của b không nằm trong đoạn từ \(0\) đến \(N-1\).
Wrong Answer [7] Các phần tử của b không đôi một khác nhau.
Wrong Answer [8] Cách sắp xếp báo cáo không phải cách sắp xếp đúng.
Wrong Answer [9] Gọi answer nhiều hơn một lần.
Wrong Answer [10] Khi solve kết thúc, answer chưa được gọi.

Như vậy, phải gọi answer đúng một lần. Chương trình có thể định nghĩa các hàm phụ trợ và biến toàn cục. Chương trình không được sử dụng đầu vào chuẩn, đầu ra chuẩn hoặc giao tiếp với các tệp khác bằng bất kỳ cách nào. Có thể ghi thông tin gỡ lỗi ra đầu ra lỗi chuẩn.

Biên dịch và chạy thử

Gói tệp hỗ trợ của bài chứa trình chấm mẫu và mã nguồn mẫu. Trình chấm mẫu là tệp grader.cpp. Đặt grader.cpp, library3.cpp và library3.h trong cùng thư mục, rồi biên dịch bằng:

Bash
g++ -std=gnu++20 -O2 -o grader grader.cpp library3.cpp

Hoặc chạy tệp compile.sh trong gói hỗ trợ. Khi biên dịch thành công, tệp thực thi grader được tạo ra. Trình chấm thật khác trình chấm mẫu. Trình chấm mẫu chạy trong một tiến trình, đọc đầu vào chuẩn và ghi kết quả ra đầu ra chuẩn.

Dữ liệu vào

Định dạng đầu vào của trình chấm mẫu:

N
B_0 B_1 ... B_{N-1}

\(B_i\) (\(0\le i\le N-1\)) là số hiệu quyển sách tại vị trí \(i\) trong cách sắp xếp đúng.

Dữ liệu ra

Trình chấm mẫu ghi thông tin sau ra đầu ra chuẩn và đầu ra lỗi chuẩn:

  • Nếu chương trình đúng, báo số lần gọi query, chẳng hạn Accepted: 3000.
  • Nếu chương trình bị chấm sai, báo loại lỗi, chẳng hạn Wrong Answer [3].

Nếu chương trình đồng thời thỏa mãn nhiều điều kiện bị chấm sai, trình chấm mẫu chỉ báo một loại lỗi.

Ràng buộc

  • \(2\le N\le 500\).
  • \(0\le B_i\le N-1\) với \(0\le i\le N-1\).
  • \(B_i\ne B_j\) với \(0\le i<j\le N-1\).
  • Tất cả giá trị đầu vào đều là số nguyên.

Phân nhóm

Mọi nhóm đều tuân theo các ràng buộc chung ở trên.

Nhóm Điểm Ràng buộc bổ sung
1 2 \(N\le 6\).
2 19 \(N\le 100\).
3 79 Không có ràng buộc bổ sung.

Ví dụ

Ví dụ 1

Input 
4
2 0 3 1
Lời gọi và giá trị trả về
Lời gọi của trình chấm Lời gọi của chương trình Giá trị trả về
solve(4)
query([0, 1, 2, 3]) 3
query([1, 3, 0, 2]) 2
query([3, 0, 1, 2]) 2
query([2, 0, 3, 1]) 0
answer([2, 0, 3, 1])
Note

Chẳng hạn, lời gọi query([0, 1, 2, 3]) mô tả cách sắp xếp mà các quyển sách \(0,1,2,3\) lần lượt nằm ở vị trí \(0,1,2,3\). Các thao tác diễn ra như sau:

  1. Hoán đổi quyển sách \(0\) và quyển sách \(1\). Các quyển \(1,0,2,3\) lần lượt nằm ở vị trí \(0,1,2,3\).
  2. Hoán đổi quyển sách \(1\) và quyển sách \(3\). Các quyển \(3,0,2,1\) lần lượt nằm ở vị trí \(0,1,2,3\).
  3. Hoán đổi quyển sách \(3\) và quyển sách \(2\). Các quyển \(2,0,3,1\) lần lượt nằm ở vị trí \(0,1,2,3\).

Cần \(3\) thao tác để đưa sách về cách sắp xếp đúng, nên truy vấn trả về \(3\). Ví dụ này thỏa mãn ràng buộc của tất cả các nhóm.

Nguồn

JOI Open Contest 2024, bài Library 3, tác giả Sora Todaka.

Bản dịch tiếng Việt từ đề của JCIOI (Ủy ban Olympic Tin học Quốc tế Nhật Bản), theo giấy phép CC BY-SA 4.0.