JOI 2021 - Open Contest

Bạn có biết phòng thí nghiệm Just Odd Investigations không? Công việc của phòng thí nghiệm này là thực hiện những "nghiên cứu kỳ lạ" (just odd investigations). Sau đây, ta gọi tắt nơi này là phòng thí nghiệm JOI.

Trong những năm gần đây, người ta đã phát hiện những vườn hoa rộng lớn, nở rực rỡ tại nhiều di tích lịch sử trên thế giới. Phòng thí nghiệm JOI phát hiện rằng những bông hoa trong các khu vườn này thuộc các loài mới và bộ gen của chúng có những đặc điểm tương tự nhau. Bộ gen của mỗi bông hoa được biểu diễn bằng một xâu độ dài \(N\), chỉ gồm các ký tự J, O, I. Ta gọi xâu này là xâu gen.

Bạn là một nhà nghiên cứu tại phòng thí nghiệm JOI. Ban đầu, bạn có ba bông hoa thuộc các loài mới, với các xâu gen lần lượt là \(S_A\), \(S_B\), \(S_C\).

Bạn có thể tạo ra một bông hoa mới từ hai bông hoa bằng một thao tác gọi là lai giống. Ký tự thứ \(i\) (\(1 \le i \le N\)) trong xâu gen của bông hoa mới được xác định như sau:

• Nếu ký tự thứ \(i\) trong hai xâu gen ban đầu giống nhau, ký tự thứ \(i\) của xâu gen mới cũng là ký tự đó.
• Nếu hai ký tự này khác nhau, ký tự thứ \(i\) của xâu gen mới là ký tự còn lại trong ba ký tự J, O, I.

Nói cách khác, nếu ký tự thứ \(i\) của hai xâu gen ban đầu là \(c_1\) và \(c_2\), ký tự \(c_3\) ở vị trí đó của xâu gen mới được cho bởi bảng sau:

Bạn có thể sử dụng cùng một bông hoa để lai giống bao nhiêu lần tùy ý. Những bông hoa mới tạo ra cũng có thể được sử dụng trong các lần lai giống tiếp theo.

Để tạo ra những bông hoa đẹp hơn, phòng thí nghiệm JOI đề xuất \(Q+1\) xâu gen ứng viên, được đánh số từ \(0\) đến \(Q\). Bạn được cung cấp một danh sách mô tả các xâu này, gồm xâu \(T_0\) và, với mỗi \(j\) (\(1 \le j \le Q\)), hai số nguyên \(L_j\), \(R_j\) cùng ký tự \(C_j\). Các xâu gen ứng viên được xác định như sau:

• Xâu gen ứng viên \(0\) là \(T_0\).
• Xâu gen ứng viên \(j\) (\(1 \le j \le Q\)) được tạo từ xâu gen ứng viên \(j-1\) bằng cách thay tất cả các ký tự từ vị trí \(L_j\) đến vị trí \(R_j\) bằng ký tự \(C_j\).

Cho \(N\), các xâu gen của ba bông hoa ban đầu và danh sách mô tả các xâu gen ứng viên, hãy xác định với từng xâu ứng viên liệu có thể tạo được một bông hoa có xâu gen đó từ ba bông hoa ban đầu bằng cách thực hiện không hoặc nhiều lần lai giống hay không.

Dữ liệu vào

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

N
S_A
S_B
S_C
Q
T_0
L_1 R_1 C_1
...
L_Q R_Q C_Q

Dữ liệu ra

Ghi \(Q+1\) dòng ra đầu ra chuẩn. Ở dòng thứ \(j+1\) (\(0 \le j \le Q\)), ghi Yes nếu có thể tạo được bông hoa có xâu gen ứng viên \(j\) từ ba bông hoa ban đầu bằng không hoặc nhiều lần lai giống; ngược lại, ghi No.

Ràng buộc

• \(1 \le N \le 200\,000\).
• \(S_A\), \(S_B\), \(S_C\) đều là các xâu độ dài \(N\), chỉ gồm các ký tự J, O, I.
• \(1 \le Q \le 200\,000\).
• \(T_0\) là xâu độ dài \(N\), chỉ gồm các ký tự J, O, I.
• \(1 \le L_j \le R_j \le N\) (\(1 \le j \le Q\)).
• \(C_j\) là một trong các ký tự J, O, I (\(1 \le j \le Q\)).

Phân nhóm

1. (3 điểm) \(S_A=S_B=S_C\) và \(N \le 100\).
2. (23 điểm) \(S_A=S_B=S_C\).
3. (23 điểm) \(N \le 100\).
4. (51 điểm) Không có giới hạn bổ sung.

Ví dụ

4
JOJO
JJOI
OJOO
3
IJOJ
1 4 O
2 2 J
2 4 I

Yes
No
Yes
Yes

3
JOI
JOI
JOI
2
OJI
1 2 O
1 1 J

No
No
Yes

Nguồn

JOI Open Contest 2021, JCIOI. Bản dịch tiếng Việt từ đề chính thức; phát hành theo giấy phép CC BY-SA 4.0.

JOI mart là một cửa hàng đã hoạt động được \(N\) ngày. Doanh thu vào ngày thứ \(i\) (\(1 \le i \le N\)) kể từ khi khai trương là \(A_i\) yen.

Bitaro, quản lý của JOI mart, chuẩn bị thuyết trình báo cáo tài chính. Anh sẽ chọn một số ngày và trình bày biểu đồ cột thể hiện doanh thu của những ngày đó theo thứ tự thời gian, rồi giải thích doanh thu đã thay đổi như thế nào. Để bài thuyết trình gây ấn tượng hơn, anh muốn chọn dữ liệu sao cho biểu đồ tạo được ấn tượng tốt nhất.

Giả sử Bitaro chọn dữ liệu của \(m\) ngày (\(1 \le m \le N\)), là các ngày \(p_1,p_2,\ldots,p_m\) kể từ khi khai trương, với \(1 \le p_1<p_2<\cdots<p_m \le N\). Điểm ấn tượng của biểu đồ được tính như sau:

Điểm ấn tượng là số lần doanh thu lập kỷ lục mới khi chỉ xét những ngày được chọn. Nói cách khác, đó là số chỉ số \(j\) (\(1 \le j \le m\)) thỏa mãn \(j=1\) hoặc

Bitaro muốn tối đa hóa điểm ấn tượng, nhưng một số cách chọn dữ liệu có thể khiến bài thuyết trình trông thiếu tự nhiên. Vì vậy, anh quyết định chọn dữ liệu thỏa mãn đồng thời hai điều kiện sau:

• Phải trình bày doanh thu mới nhất, tức là \(p_m=N\).
• Hai ngày được chọn liên tiếp cách nhau không quá \(D\) ngày. Cụ thể, nếu \(m \ge 2\) thì \(p_{j+1}-p_j \le D\) với mọi \(j\) (\(1 \le j \le m-1\)).

Cho dữ liệu doanh thu của JOI mart kể từ khi khai trương và số nguyên \(D\), hãy tính điểm ấn tượng lớn nhất của biểu đồ mà Bitaro có thể trình bày.

Dữ liệu vào

Đọc dữ liệu từ đầu vào chuẩn theo định dạng sau. Mọi giá trị trong dữ liệu vào đều là số nguyên.

N D
A_1 ... A_N

Dữ liệu ra

Ghi một dòng chứa điểm ấn tượng lớn nhất của biểu đồ ra đầu ra chuẩn.

Ràng buộc

• \(1 \le N \le 300\,000\).
• \(1 \le D \le N\).
• \(0 \le A_i \le 1\,000\,000\,000\) (\(1 \le i \le N\)).

Phân nhóm

1. (14 điểm) \(N \le 20\).
2. (14 điểm) \(N \le 400\).
3. (20 điểm) \(N \le 7\,000\).
4. (12 điểm) \(D=1\).
5. (5 điểm) \(D=N\).
6. (35 điểm) Không có giới hạn bổ sung.

Ví dụ

7 1
100 600 600 200 300 500 500

3

6 6
100 500 200 400 600 300

4

11 2
1 4 4 2 2 4 9 5 7 0 3

4

Nguồn

JOI Open Contest 2021, JCIOI. Bản dịch tiếng Việt từ đề chính thức; phát hành theo giấy phép CC BY-SA 4.0.

Một trò chơi điện tử mới vừa được phát hành. Trong thế giới của trò chơi có \(N\) quái vật, được đánh số từ \(0\) đến \(N-1\). Mỗi quái vật có một số nguyên gọi là sức mạnh. Sức mạnh của quái vật \(i\) (\(0 \le i \le N-1\)) là \(S_i\). Ta biết rằng:

• Sức mạnh của mỗi quái vật là một số nguyên từ \(0\) đến \(N-1\), kể cả hai đầu mút.
• Hai quái vật khác nhau không có cùng sức mạnh.

Bạn có thể chọn hai quái vật khác nhau và cho chúng giao đấu. Nếu quái vật \(a\) và quái vật \(b\) (\(0 \le a,b \le N-1\), \(a \ne b\)) giao đấu, kết quả được xác định như sau:

• Nếu \(|S_a-S_b|=1\), quái vật có sức mạnh nhỏ hơn thắng.
• Nếu \(|S_a-S_b|>1\), quái vật có sức mạnh lớn hơn thắng.

Bất kể thắng hay thua, cùng một quái vật có thể được cho giao đấu bao nhiêu lần tùy ý.

Ban đầu, bạn không biết sức mạnh của các quái vật. Bạn muốn xác định sức mạnh của từng quái vật bằng cách tổ chức không quá \(25\,000\) trận đấu và quan sát kết quả. Hơn nữa, bạn muốn sử dụng số trận đấu ít nhất có thể.

Cho số lượng quái vật, hãy viết chương trình xác định sức mạnh của từng quái vật thông qua các trận đấu.

Chi tiết cài đặt

Bạn cần nộp một tệp có tên monster.cpp. Tệp này phải dùng chỉ thị #include để nạp monster.h và cài đặt hàm sau:

std::vector<int> Solve(int N)

• Hàm được gọi đúng một lần trong mỗi bộ dữ liệu kiểm tra.
• Tham số N là số lượng quái vật.
• Hàm trả về một mảng mô tả sức mạnh của từng quái vật. Gọi mảng trả về là T.
• Độ dài của T phải bằng \(N\). Nếu không, chương trình bị chấm Wrong Answer [1].
• Mỗi phần tử của T phải nằm trong đoạn từ \(0\) đến \(N-1\). Nếu không, chương trình bị chấm Wrong Answer [2].
• Với mọi \(i\) (\(0 \le i \le N-1\)), phải có T[i] \(=S_i\). Nếu không, chương trình bị chấm Wrong Answer [3].

Chương trình của bạn có thể gọi hàm sau để cho hai quái vật giao đấu:

bool Query(int a, int b)

• Các tham số a, b là chỉ số của hai quái vật giao đấu.
• Hàm trả về true nếu quái vật \(a\) thắng, và false nếu quái vật \(b\) thắng.
• Phải có \(0 \le a,b \le N-1\). Nếu không, chương trình bị chấm Wrong Answer [4].
• Phải có \(a \ne b\). Nếu không, chương trình bị chấm Wrong Answer [5].
• Không được gọi Query quá \(25\,000\) lần. Nếu vượt quá giới hạn này, chương trình bị chấm Wrong Answer [6].

Lưu ý quan trọng

• Bạn được phép cài đặt các hàm khác để sử dụng nội bộ hoặc khai báo biến toàn cục.
• Chương trình của bạn 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, bạn được phép ghi thông tin gỡ lỗi ra đầu ra lỗi chuẩn.

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

Đề chính thức cho biết trang thi cung cấp một tệp nén chứa trình chấm mẫu và tệp mã nguồn mẫu dành cho chương trình của bạn.

Trình chấm mẫu là tệp grader.cpp. Để thử chương trình, đặt grader.cpp, monster.cpp, monster.h trong cùng một thư mục và dùng lệnh sau:

g++ -std=gnu++17 -O2 -o grader grader.cpp monster.cpp

Sau khi biên dịch thành công, tệp thực thi grader được tạo ra. Lưu ý rằng trình chấm thực tế khác với trình chấm mẫu. Trình 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.

Dữ liệu vào

Trình chấm mẫu đọc dữ liệu theo định dạng:

N
S_0 ... S_{N-1}

Dữ liệu ra

Khi chương trình kết thúc bình thường, trình chấm mẫu ghi thông tin sau ra đầu ra chuẩn, không kèm dấu ngoặc kép:

• Nếu câu trả lời đúng, trình chấm ghi số lần gọi Query, chẳng hạn Accepted: 100.
• Nếu câu trả lời sai, trình chấm ghi loại lỗi, chẳng hạn Wrong Answer [1].

Nếu chương trình vi phạm nhiều điều kiện, trình chấm mẫu chỉ báo một trong các loại lỗi đó.

Lưu ý về trình chấm

Trong một số bộ dữ liệu kiểm tra, trình chấm thực tế là thích nghi (adaptive). Điều này có nghĩa là trình chấm không cố định đáp án ngay từ đầu mà trả lời dựa trên các lần gọi Query trước đó. Tuy nhiên, luôn bảo đảm tồn tại ít nhất một đáp án phù hợp với tất cả các câu trả lời đã đưa ra.

Ràng buộc

• \(4 \le N \le 1\,000\).
• \(0 \le S_i \le N-1\) (\(0 \le i \le N-1\)).
• \(S_i \ne S_j\) (\(0 \le i<j \le N-1\)).

Phân nhóm

1. (10 điểm) \(N \le 200\).
2. (15 điểm) Trình chấm thực tế không thích nghi.

3. (75 điểm) Không có giới hạn bổ sung. Nếu chương trình trả lời đúng tất cả các bộ dữ liệu kiểm tra trong phân nhóm này, điểm được tính như sau. Gọi \(X\) là số lần gọi Query lớn nhất trên tất cả các bộ dữ liệu kiểm tra của phân nhóm:

4. Nếu \(10\,000<X\le25\,000\), điểm là \(\left\lfloor75\times\dfrac{25\,000-X}{15\,000}\right\rfloor\).

5. Nếu \(X\le10\,000\), điểm là \(75\).

Ví dụ giao tiếp

Sau đây là một đầu vào cho trình chấm mẫu và các lời gọi hàm tương ứng. Giá trị trả về của Solve không phải dữ liệu mà chương trình của bạn được phép ghi ra đầu ra chuẩn.

Ví dụ 1

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

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

5
3 1 4 2 0

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

Mảng trả về của Solve, không phải đầu ra chuẩn.

3 1 4 2 0

Các lời gọi hàm

Nguồn

JOI Open Contest 2021, JCIOI. Bản dịch tiếng Việt từ đề chính thức; phát hành theo giấy phép CC BY-SA 4.0.