JOI 2025 - Tuyển chọn mùa xuân - Ngày 1

Bảo tàng Mỹ thuật JOI sắp tổ chức một triển lãm tranh. Bảo tàng sở hữu \(N\) bức tranh, được đánh số từ \(1\) đến \(N\). Bức tranh \(i\) (\(1 \le i \le N\)) có độ đẹp \(A_i\). Các bức tranh sẽ được xếp thành một hàng từ trái sang phải, nhưng thứ tự trưng bày chưa được quyết định.

Có \(M\) tạp chí sẽ đưa tin về triển lãm. Các tạp chí được đánh số từ \(1\) đến \(M\) theo thứ tự giảm dần về mức độ ảnh hưởng. Mỗi tạp chí sẽ đăng ảnh của các bức tranh trong một đoạn liên tiếp của hàng tranh. Cụ thể, tạp chí \(j\) (\(1 \le j \le M\)) sẽ đăng ảnh của các bức tranh ở vị trí \(L_j,L_j+1,\ldots,R_j\) tính từ trái sang phải. Độ hấp dẫn của bài viết trên tạp chí \(j\) là độ đẹp lớn nhất trong số các bức tranh mà tạp chí đó đăng ảnh.

JOI, giám đốc bảo tàng, muốn sắp xếp tranh để các tạp chí viết được những bài có độ hấp dẫn cao hơn, qua đó thu hút nhiều người đến triển lãm. Vì các tạp chí có ảnh hưởng lớn tiếp cận được nhiều độc giả hơn, JOI ưu tiên tăng độ hấp dẫn của bài viết trên những tạp chí đó.

Chính xác hơn, gọi \(b_j\) là độ hấp dẫn của bài viết trên tạp chí \(j\) (\(1 \le j \le M\)). JOI muốn sắp xếp tranh sao cho dãy \(b=(b_1,b_2,\ldots,b_M)\) lớn nhất theo thứ tự từ điển. Với hai dãy khác nhau \(b=(b_1,b_2,\ldots,b_M)\) và \(b'=(b'_1,b'_2,\ldots,b'_M)\), dãy \(b\) lớn hơn \(b'\) theo thứ tự từ điển nếu tại chỉ số \(k\) nhỏ nhất mà \(b_k \ne b'_k\), ta có \(b_k>b'_k\).

Cho thông tin về các bức tranh và các tạp chí. Hãy tính độ hấp dẫn của bài viết trên mỗi tạp chí khi các bức tranh được sắp xếp để dãy \(b\) lớn nhất theo thứ tự từ điển.

Dữ liệu vào

Đọc dữ liệu từ đầu vào chuẩn:

• Dòng thứ nhất chứa hai số nguyên \(N,M\).
• Dòng thứ hai chứa \(N\) số nguyên \(A_1,A_2,\ldots,A_N\).
• Trong \(M\) dòng tiếp theo, dòng thứ \(j\) chứa hai số nguyên \(L_j,R_j\).

Các số trên cùng một dòng được ngăn cách bởi dấu cách.

Dữ liệu ra

In ra đầu ra chuẩn \(M\) dòng. Dòng thứ \(j\) (\(1 \le j \le M\)) chứa \(b_j\), độ hấp dẫn của bài viết trên tạp chí \(j\). Dãy \(b=(b_1,b_2,\ldots,b_M)\) phải lớn nhất theo thứ tự từ điển.

Ràng buộc

• \(1 \le N \le 100000\).
• \(1 \le M \le 100000\).
• \(1 \le A_i \le N\) với \(1 \le i \le N\).
• \(1 \le L_j \le R_j \le N\) với \(1 \le j \le M\).
• Tất cả các giá trị trong dữ liệu vào đều là số nguyên.

Chấm điểm

1. \(19\) điểm: \(N \le 400\), \(M \le 400\).
2. \(9\) điểm: \(N \le 400\).
3. \(19\) điểm: \(A_i \le 5\) với mọi \(1 \le i \le N\).
4. \(12\) điểm: \(A_i=i\) với mọi \(1 \le i \le N\).
5. \(17\) điểm: Với mỗi \(k\) (\(1 \le k \le N\)), có nhiều nhất \(5\) chỉ số \(i\) thỏa mãn \(A_i=k\).
6. \(24\) điểm: Không có ràng buộc bổ sung.

Ví dụ

4 4
1 2 1 2
1 1
2 3
4 4
3 4

2
2
1
2

4 8
1 2 3 4
1 2
2 3
4 4
1 1
2 4
3 3
3 3
4 4

4
4
3
2
4
1
1
3

12 10
6 2 2 5 2 5 2 3 3 3 2 2
3 5
10 12
12 12
2 4
8 9
10 11
1 3
7 9
9 10
10 11

6
5
5
6
5
3
6
5
5
3

Giới hạn

Giới hạn thời gian là \(3\) giây; giới hạn bộ nhớ là \(1024\) MB.

Nguồn

Đề gốc và bản dịch được cung cấp theo giấy phép CC BY-SA 4.0.

Bản dịch tiếng Việt từ đề tiếng Anh và tiếng Nhật của Ủy ban Olympic Tin học Nhật Bản, JOI 2024/2025, vòng tuyển chọn mùa xuân, ngày thi thứ nhất. Tham khảo thêm thông báo triển khai và thông tin chấm điểm.

Anna và Bruno thích bói toán và thường cùng nhau thử nhiều cách bói khác nhau. Hôm nay, họ sẽ thực hiện \(Q\) lượt bói bằng những lá bài ghi số \(0\) hoặc \(1\). Mỗi lượt diễn ra như sau:

1. Họ chuẩn bị nhiều lá bài, mỗi lá ghi số \(0\) hoặc \(1\), xáo trộn rồi xếp thành một chồng bài.
2. Anna rút lần lượt từng lá, tổng cộng \(N=900\) lá. Cả Anna và Bruno đều biết \(N\). Mỗi khi rút được một lá, Anna quyết định bỏ lá đó hoặc đặt nó lên bàn. Nếu đặt lên bàn, Anna được chèn lá bài vào bất kỳ vị trí nào trong dãy bài đang có. Cụ thể, nếu trên bàn đang có \(l\) lá, Anna chọn số nguyên \(x\) với \(0 \le x \le l\) và chèn lá mới ngay bên phải lá thứ \(x\) tính từ trái sang phải. Khi \(x=0\), lá mới được chèn vào đầu bên trái của dãy.
3. Sau khi rút và xử lý đủ \(N\) lá, phần việc của Anna kết thúc. Kết quả bói là số lá ghi số \(1\) trong toàn bộ \(N\) lá Anna đã rút, kể cả những lá đã bỏ đi.
4. Bruno chỉ nhìn dãy bài cuối cùng trên bàn để đoán kết quả bói. Nếu đoán đúng, lượt bói thành công.

Càng đặt ít lá bài lên bàn, cách bói càng được đánh giá cao. Hãy cài đặt chiến lược của Anna và Bruno để thành công trong cả \(Q\) lượt. Trong bài này, Anna đặt càng ít lá lên bàn thì bạn càng được nhiều điểm.

Chi tiết cài đặt

Bạn phải nộp hai tệp: Anna.cpp và Bruno.cpp.

Tệp Anna.cpp cài đặt chiến lược của Anna, phải nạp Anna.h bằng chỉ thị #include và cài đặt hàm sau:

void Anna(int N)

Hàm này được gọi tổng cộng \(Q\) lần. Lần gọi thứ \(i\) (\(1 \le i \le Q\)) tương ứng với phần việc của Anna trong lượt bói thứ \(i\). Tham số N là số lá bài Anna phải rút.

Trong mỗi lần thực hiện Anna, bạn phải gọi hàm sau đúng \(N+1\) lần:

int DrawCard(int x)

Hàm này cho phép Anna nhận lá bài tiếp theo đồng thời quyết định cách xử lý lá bài vừa rút trước đó. Giá trị trả về của lần gọi thứ \(j\) (\(1 \le j \le N\)) là số ghi trên lá bài thứ \(j\). Tham số của lần gọi thứ \(k\) (\(2 \le k \le N+1\)) chỉ định cách xử lý lá bài thứ \(k-1\).

• Lần gọi thứ \(j\) (\(1 \le j \le N\)) trả về \(0\) hoặc \(1\), là số ghi trên lá bài thứ \(j\) Anna rút được.
• Lần gọi thứ \(N+1\) trả về \(-1\), báo rằng Anna đã rút đủ bài.
• Trong lần gọi đầu tiên, bắt buộc phải có \(x=-1\). Nếu không, chương trình bị chấm Wrong Answer [1].
• Trong lần gọi thứ \(k\) (\(2 \le k \le N+1\)), nếu \(x=-1\) thì bỏ lá bài thứ \(k-1\). Nếu \(x \ge 0\), chèn lá đó ngay bên phải lá thứ \(x\) tính từ trái sang phải trong dãy hiện tại; riêng \(x=0\) nghĩa là chèn vào đầu bên trái. Gọi \(l\) là số lá hiện có trên bàn, tham số phải thỏa mãn \(-1 \le x \le l\). Nếu không, chương trình bị chấm Wrong Answer [2].
• Nếu số lần gọi DrawCard không đúng bằng \(N+1\) khi Anna kết thúc, chương trình bị chấm Wrong Answer [3].

Tệp Bruno.cpp cài đặt chiến lược của Bruno, phải nạp Bruno.h bằng chỉ thị #include và cài đặt hàm sau:

int Bruno(int N, int L, std::vector<int> C)

Hàm này được gọi đúng một lần sau mỗi lần gọi Anna, tổng cộng \(Q\) lần. Lần gọi thứ \(i\) (\(1 \le i \le Q\)) tương ứng với phần việc của Bruno trong lượt bói thứ \(i\). Hàm phải trả về số lá ghi số \(1\) trong tất cả các lá Anna đã rút.

• N là số lá bài Anna đã rút.
• L là số lá bài đang nằm trên bàn.
• C là mảng có độ dài L. Phần tử C[l-1] là số ghi trên lá thứ \(l\) tính từ trái sang phải trên bàn, với \(1 \le l \le L\).
• Nếu giá trị trả về không bằng số lá ghi số \(1\) mà Anna đã rút, chương trình bị chấm Wrong Answer [4].

Lưu ý quan trọng

Bạn được cài đặt các hàm phụ và khai báo biến toàn cục. Hai tệp nộp sẽ được liên kết cùng bộ chấm thành một tệp thực thi. Để tránh xung đột tên giữa các tệp, mọi biến toàn cục và hàm nội bộ phải được khai báo trong một không gian tên không có tên, tức namespace { ... }.

Khi chấm thật, tệp thực thi được chạy thành hai tiến trình, một phía Anna và một phía Bruno. Hai phía không thể chia sẻ biến toàn cục.

Chương trình bạn nộp không được sử dụng đầu vào chuẩn, đầu ra chuẩn hoặc trao đổi với các tệp khác bằng bất kỳ cách nào. Tuy nhiên, được phép ghi thông tin gỡ lỗi ra đầu ra lỗi chuẩn.

Bộ chấm thật không thích nghi: dãy số trên các lá bài đã được cố định trước khi chương trình chạy, không thay đổi dựa trên hành động của chương trình.

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

Gói tệp tải từ trang kỳ thi chứa bộ chấm mẫu và các tệp mã nguồn mẫu. Bộ chấm mẫu nằm trong grader.cpp.

Đặt grader.cpp, Anna.cpp, Bruno.cpp, Anna.h, Bruno.h trong cùng một thư mục, rồi biên dịch bằng lệnh:

g++ -std=gnu++20 -O2 -o grader grader.cpp Anna.cpp Bruno.cpp

Bạn cũng có thể chạy tệp compile.sh đi kèm gói tải:

./compile.sh

Nếu biên dịch thành công, tệp thực thi grader được tạo ra.

Bộ chấm thật khác với bộ chấm mẫu. Bộ chấm mẫu chạy trong một tiến trình, đọc dữ liệu từ đầu vào chuẩn và ghi kết quả ra đầu ra chuẩn. Thông tin gỡ lỗi có thể được ghi ra đầu ra lỗi chuẩn. Việc bộ chấm mẫu đọc và ghi các luồng này không cho phép mã bạn nộp sử dụng chúng.

Dữ liệu vào

• Dòng thứ nhất chứa hai số nguyên \(Q,N\).
• Trong \(Q\) dòng tiếp theo, dòng thứ \(i\) chứa \(N\) số nguyên \(A_{i,1},A_{i,2},\ldots,A_{i,N}\), cách nhau bởi dấu cách.

\(A_{i,j}\) (\(1 \le i \le Q\), \(1 \le j \le N\)) là số ghi trên lá bài thứ \(j\) mà Anna rút trong lượt bói thứ \(i\).

Dữ liệu ra

Bộ chấm mẫu thông báo kết quả theo các dạng sau; dấu ngoặc kép không được in:

• Nếu chương trình đúng, bộ chấm in số lá bài trên bàn lớn nhất trong tất cả các lượt, chẳng hạn Accepted: 100. Số sau dấu hai chấm là số lá bài, không phải số điểm.
• Nếu chương trình sai, bộ chấm in loại lỗi, chẳng hạn Wrong Answer [1].

Nếu chương trình đồng thời vi phạm nhiều điều kiện, bộ chấm mẫu chỉ báo một loại lỗi trong số đó. Bộ chấm mẫu có thể dừng chương trình ngay khi phát hiện lỗi.

Ràng buộc

• \(1 \le Q \le 100\).
• \(N=900\).
• \(A_{i,j}\) là \(0\) hoặc \(1\) với \(1 \le i \le Q\), \(1 \le j \le N\).

Chấm điểm

Nếu chương trình bị chấm một trong các lỗi Wrong Answer [1] đến Wrong Answer [4], quá thời gian, quá bộ nhớ hoặc lỗi khi chạy ở bất kỳ bộ dữ liệu nào, bạn nhận \(0\) điểm cho toàn bộ bài.

Nếu chương trình đúng ở tất cả các bộ dữ liệu, gọi \(L\) là giá trị lớn nhất của số lần gọi DrawCard với tham số \(x \ge 0\) trong một lần gọi Anna, xét trên mọi lượt bói của mọi bộ dữ liệu. Đây cũng là số lá bài trên bàn lớn nhất. Điểm được tính như sau:

• Nếu \(L>500\): nhận \(3\) điểm.
• Nếu \(14<L \le 500\): nhận \(\left\lfloor 100\left(\frac{2.5}{L-11.5}\right)^{0.35}\right\rfloor\) điểm.
• Nếu \(L \le 14\): nhận \(100\) điểm.

Ví dụ giao tiếp

Dưới đây là dữ liệu vào của bộ chấm mẫu và một chuỗi lời gọi hàm tương ứng. Phần Output biểu diễn các lời gọi và giá trị trả về, không phải văn bản mà chương trình nộp phải in. Các lời gọi DrawCard được thụt vào bên dưới lần gọi Anna đang thực hiện.

Ví dụ 1

Dữ liệu vào của trình chấm mẫu:

2 5
0 1 0 0 1
1 1 0 1 0

Dữ liệu ra của trình chấm mẫu:

Anna(5)
  DrawCard(-1) -> 0
  DrawCard(0) -> 1
  DrawCard(-1) -> 0
  DrawCard(1) -> 0
  DrawCard(-1) -> 1
  DrawCard(1) -> -1
Bruno(5, 3, [0, 1, 0]) -> 2
Anna(5)
  DrawCard(-1) -> 1
  DrawCard(0) -> 1
  DrawCard(1) -> 0
  DrawCard(2) -> 1
  DrawCard(-1) -> 0
  DrawCard(1) -> -1
Bruno(5, 4, [1, 0, 1, 0]) -> 3

Giải thích

Ví dụ có \(Q=2\) lượt bói, mỗi lượt Anna rút \(N=5\) lá. Trong lượt thứ nhất, Anna thực hiện như sau:

1. Rút một lá bài ghi số \(0\).
2. Chọn đặt lá đó lên bàn, chèn vào đầu bên trái. Dãy trên bàn trở thành \(0\). Sau đó rút lá tiếp theo, ghi số \(1\).
3. Bỏ lá vừa rút. Sau đó rút lá tiếp theo, ghi số \(0\).
4. Chọn đặt lá đó lên bàn, chèn ngay bên phải lá thứ nhất tính từ trái sang phải. Dãy trên bàn trở thành \(0,0\). Sau đó rút lá tiếp theo, ghi số \(0\).
5. Bỏ lá vừa rút. Sau đó rút lá tiếp theo, ghi số \(1\).
6. Chọn đặt lá đó lên bàn, chèn ngay bên phải lá thứ nhất tính từ trái sang phải. Dãy trên bàn trở thành \(0,1,0\).

Bruno biết \(N\) và nhìn thấy dãy \(0,1,0\). Bruno đoán rằng có \(2\) lá ghi số \(1\) trong các lá Anna đã rút. Đáp án đúng nên lượt bói thành công. Số lá Anna đặt lên bàn trong lượt này là \(L=3\).

Trong lượt bói thứ hai, Anna đặt \(L=4\) lá lên bàn.

Ví dụ này không thỏa mãn ràng buộc của bài, vì \(N=5\) thay vì \(900\). Tệp sample-01-in.txt trong gói tải tương ứng với ví dụ trên. Tệp sample-02-in.txt đi kèm là một dữ liệu mẫu thỏa mãn các ràng buộc.

Giới hạn

Giới hạn thời gian là \(2\) giây; giới hạn bộ nhớ là \(1024\) MB.

Nguồn

Bản dịch tiếng Việt từ đề tiếng Anh và tiếng Nhật của Ủy ban Olympic Tin học Nhật Bản, JOI 2024/2025, vòng tuyển chọn mùa xuân, ngày thi thứ nhất. Tham khảo thêm gói bộ chấm mẫu, thông báo triển khai và thông tin chấm điểm. Đề gốc và bản dịch được cung cấp theo giấy phép CC BY-SA 4.0.

Dãy núi JOI gồm nhiều ngọn núi, được biểu diễn bằng một lưới có \(H\) hàng và \(W\) cột. Chiều dọc của lưới là hướng Bắc–Nam, còn chiều ngang là hướng Đông–Tây. Ô ở hàng thứ \(i\) tính từ phía Bắc (\(1 \le i \le H\)), cột thứ \(j\) tính từ phía Tây (\(1 \le j \le W\)) được ký hiệu là \((i,j)\). Mỗi ô có đúng một ngọn núi. Độ cao đỉnh núi tại ô \((i,j)\) là \(T_{i,j}\).

Bitaro là một chú hải ly có sức bật \(L\). Khi đang đứng trên một đỉnh núi, Bitaro có thể di chuyển bằng một cú nhảy cao, gồm các bước sau theo thứ tự:

1. Bitaro bay thẳng lên từ đỉnh núi hiện tại. Nếu đỉnh núi có độ cao \(x\), Bitaro sẽ lơ lửng ở độ cao \(x+L+0.5\).
2. Bitaro di chuyển sang một ô kề theo một trong bốn hướng Đông, Tây, Nam, Bắc mà không thay đổi độ cao, lặp lại việc này không hoặc nhiều lần. Tại mọi ô đi qua, đỉnh núi phải thấp hơn độ cao mà Bitaro đang lơ lửng.
3. Bitaro hạ xuống đỉnh núi ở ô hiện tại.

Bitaro đang lên kế hoạch cho \(Q\) chuyến đi. Trong chuyến đi thứ \(k\) (\(1 \le k \le Q\)), Bitaro muốn đi từ đỉnh núi tại ô \((A_k,B_k)\) đến đỉnh núi tại ô \((C_k,D_k)\) chỉ bằng các cú nhảy cao. Bitaro muốn biết từng chuyến đi có thực hiện được hay không. Vì mỗi lần bay lên tiêu tốn nhiều sức lực, nếu thực hiện được, Bitaro còn muốn biết số cú nhảy cao ít nhất cần dùng.

Cho thông tin về các ngọn núi, sức bật của Bitaro và các kế hoạch di chuyển. Với mỗi chuyến đi, hãy xác định có thể thực hiện được hay không và, nếu có, tìm số cú nhảy cao ít nhất cần dùng.

Dữ liệu vào

Đọc dữ liệu từ đầu vào chuẩn:

• Dòng thứ nhất chứa ba số nguyên \(H,W,L\).
• Trong \(H\) dòng tiếp theo, dòng thứ \(i\) chứa \(W\) số nguyên \(T_{i,1},T_{i,2},\ldots,T_{i,W}\).
• Dòng tiếp theo chứa số nguyên \(Q\).
• Trong \(Q\) dòng tiếp theo, dòng thứ \(k\) chứa bốn số nguyên \(A_k,B_k,C_k,D_k\).

Các số trên cùng một dòng được ngăn cách bởi dấu cách.

Dữ liệu ra

In ra đầu ra chuẩn \(Q\) dòng. Dòng thứ \(k\) (\(1 \le k \le Q\)) chứa số cú nhảy cao ít nhất cần dùng cho chuyến đi thứ \(k\) nếu có thể thực hiện chuyến đi đó; nếu không, in ra -1.

Ràng buộc

• \(1 \le H\).
• \(1 \le W\).
• \(2 \le H \times W \le 300000\).
• \(1 \le L \le 10^9\).
• \(1 \le T_{i,j} \le 10^9\) với \(1 \le i \le H\), \(1 \le j \le W\).
• \(1 \le Q \le 300000\).
• \(1 \le A_k \le H\) và \(1 \le C_k \le H\) với \(1 \le k \le Q\).
• \(1 \le B_k \le W\) và \(1 \le D_k \le W\) với \(1 \le k \le Q\).
• \((A_k,B_k) \ne (C_k,D_k)\) với \(1 \le k \le Q\).
• Tất cả các giá trị trong dữ liệu vào đều là số nguyên.

Chấm điểm

1. \(10\) điểm: \(H \times W \le 300\), \(Q \le 150000\).
2. \(20\) điểm: \(H \times W \le 3000\), \(Q \le 150000\).
3. \(20\) điểm: \(H \times W \le 150000\), \(Q \le 150000\), \((A_k,B_k)=(1,1)\) với mọi \(1 \le k \le Q\).
4. \(30\) điểm: \(H \times W \le 150000\), \(Q \le 150000\).
5. \(20\) điểm: Không có ràng buộc bổ sung.

Ví dụ

2 4 5
1 3 22 1
8 13 6 16
6
1 1 2 2
1 1 1 3
1 1 2 3
1 1 2 4
1 1 1 4
1 1 1 2

3
-1
3
4
4
1

6 5 11
175 100 110 117 158
144 133 123 150 191
167 252 219 181 346
231 241 280 201 209
261 332 325 225 338
269 298 315 291 308
12
1 1 4 2
1 1 1 5
1 1 5 1
1 1 5 4
1 1 3 4
1 1 6 4
1 1 2 5
1 1 3 1
1 1 4 4
1 1 5 5
1 1 6 2
1 1 6 1

8
1
10
6
1
13
2
1
3
19
14
11

4 4 5
53 55 51 49
56 60 89 45
54 57 92 43
96 99 95 92
9
1 4 2 3
4 1 3 2
2 4 2 3
2 1 4 1
1 2 1 1
2 4 1 1
4 1 2 3
3 4 1 1
1 3 1 4

-1
1
-1
-1
1
3
1
4
1

Giới hạn

Giới hạn thời gian là \(4\) giây; giới hạn bộ nhớ là \(1024\) MB.

Nguồn

Đề gốc và bản dịch được cung cấp theo giấy phép CC BY-SA 4.0.

Bản dịch tiếng Việt từ đề tiếng Anh và tiếng Nhật của Ủy ban Olympic Tin học Nhật Bản, JOI 2024/2025, vòng tuyển chọn mùa xuân, ngày thi thứ nhất. Tham khảo thêm thông báo triển khai và thông tin chấm điểm.