JOI 2019 - Kỳ thi mở rộng

Có một con đường thẳng rất dài gồm \(N\) đoạn có độ dài bằng nhau, được đánh số từ \(1\) đến \(N\). Độ cứng của đoạn thứ \(i\) là \(A_i\).

JOI-kun, một ngôi sao thể thao tài năng, sẽ thực hiện môn nhảy ba bước. Mỗi lần nhảy ba bước gồm ba bước nhảy liên tiếp. Gọi \(a,b,c\) là số hiệu các đoạn đường mà JOI-kun giậm nhảy. Các số này phải thỏa mãn:

• \(a<b<c\): số hiệu các đoạn đường tăng dần.
• \(b-a\le c-b\): độ dài bước nhảy thứ nhất không lớn hơn độ dài bước nhảy thứ hai.

JOI-kun sẽ thực hiện \(Q\) lần nhảy ba bước. Trong lần thứ \(j\), các đoạn giậm nhảy phải có số hiệu từ \(L_j\) đến \(R_j\), tức là \(L_j\le a<b<c\le R_j\).

JOI-kun muốn giậm nhảy trên các đoạn đường cứng hơn. Với mỗi lần nhảy, hãy tính tổng độ cứng lớn nhất của ba đoạn giậm nhảy.

Dữ liệu vào

Dữ liệu được đọc từ đầu vào chuẩn. Tất cả các giá trị đều là số nguyên.

• Dòng đầu chứa \(N\).
• Dòng thứ hai chứa \(A_1,A_2,\ldots,A_N\).
• Dòng thứ ba chứa \(Q\).
• Trong \(Q\) dòng tiếp theo, dòng thứ \(j\) chứa \(L_j,R_j\).

Dữ liệu ra

Ghi \(Q\) dòng ra đầu ra chuẩn. Dòng thứ \(j\) chứa tổng độ cứng lớn nhất của ba đoạn giậm nhảy trong lần nhảy thứ \(j\).

Ràng buộc

• \(3\le N\le 500\,000\).
• \(1\le A_i\le 100\,000\,000\) với \(1\le i\le N\).
• \(1\le Q\le 500\,000\).
• \(1\le L_j<L_j+2\le R_j\le N\) với \(1\le j\le Q\).

Phân nhóm

1. \(5\) điểm: \(N\le 100\), \(Q\le 100\).
2. \(14\) điểm: \(N\le 5\,000\).
3. \(27\) điểm: \(N\le 200\,000\), \(Q=1\), \(L_1=1\), \(R_1=N\).
4. \(54\) điểm: Không có ràng buộc bổ sung.

Ví dụ

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

12
9
12

5
5 4 4 5 4
1
1 5

14

15
12 96 100 61 54 66 37 34 58 21 21 1 13 50 81
12
1 15
3 12
11 14
1 13
5 9
4 6
6 14
2 5
4 15
1 7
1 10
8 13

277
227
72
262
178
181
174
257
208
262
262
113

Nguồn

JOI Open Contest 2019, bài Triple Jump (jumps), ngày 14/7/2019. Bản dịch từ đề tiếng Anh chính thức của JCIOI, theo giấy phép CC BY-SA 4.0.

Có \(N\) ngôi nhà quanh hồ Beaver ở vương quốc JOI, được đánh số từ \(1\) đến \(N\) theo chiều ngược kim đồng hồ.

Mỗi ngôi nhà có thể dùng dịch vụ chuyển tiền để gửi tiền đến ngôi nhà liền kề bên trái khi nhìn từ hồ: nhà \(i\) gửi đến nhà \(i+1\) nếu \(1\le i<N\), còn nhà \(N\) gửi đến nhà \(1\). Phí chuyển tiền bằng đúng số tiền được gửi. Số tiền gửi phải là một số nguyên yên. Khi gửi tiền phải trả phí ngay, nên tổng số tiền gửi và phí không được vượt quá số tiền hiện có trong nhà.

Hiện tại, nhà \(i\) có \(A_i\) yên. Vì lý do thuế, người ta muốn nhà \(i\) có đúng \(B_i\) yên. Bạn chỉ được dùng dịch vụ chuyển tiền này; không được tiêu tiền vào việc gì khác ngoài phí chuyển tiền, cũng không được chuyển tiền bằng cách khác.

Hãy xác định liệu có thể làm cho số tiền của tất cả các ngôi nhà đồng thời bằng số tiền mong muốn hay không.

Dữ liệu vào

• Dòng đầu chứa \(N\).
• Trong \(N\) dòng tiếp theo, dòng thứ \(i\) chứa \(A_i,B_i\).

Dữ liệu được đọc từ đầu vào chuẩn.

Dữ liệu ra

Ghi Yes nếu có thể đạt số tiền mong muốn ở mọi ngôi nhà bằng dịch vụ chuyển tiền; ngược lại, ghi No.

Ràng buộc

• \(2\le N\le 1\,000\,000\).
• \(0\le A_i\le 1\,000\,000\,000\) với \(1\le i\le N\).
• \(0\le B_i\le 1\,000\,000\,000\) với \(1\le i\le N\).

Phân nhóm

1. \(15\) điểm: \(N\le 7\), \(A_i\le 5\) và \(B_i\le 5\) với mọi \(1\le i\le N\).
2. \(40\) điểm: \(N\le 20\).
3. \(45\) điểm: Không có ràng buộc bổ sung.

Ví dụ

5
0 0
1 0
2 3
3 3
4 0

Yes

5
0 0
1 2
2 4
3 2
4 0

No

2
1 1
2 1

No

2
1 1
2 2

Yes

Nguồn

JOI Open Contest 2019, bài Remittance (remittance), ngày 14/7/2019. Bản dịch từ đề tiếng Anh chính thức của JCIOI, theo giấy phép CC BY-SA 4.0.

Công ty Just Odd Inventions, gọi tắt là công ty JOI, chuyên tạo ra những phát minh kỳ lạ. Công ty vừa phát triển một loại vi-rút mới mang tên JOI Virus và muốn tiến hành thí nghiệm bằng cách cho cư dân trên đảo IOI nhiễm vi-rút này.

Đảo IOI có hình chữ nhật. Có \(R-1\) con đường song song chạy theo hướng đông-tây và \(C-1\) con đường song song chạy theo hướng bắc-nam, chia đảo thành \(RC\) ô. Mỗi ô có đúng một cư dân. Cư dân ở ô thứ \(i\) tính từ phía bắc và thứ \(j\) tính từ phía tây được gọi là cư dân \((i,j)\).

Mỗi ngày trên đảo được chia thành \(M\) khoảng thời gian, đánh số từ \(1\) đến \(M\). Gió luôn thổi từ một trong bốn hướng bắc, nam, đông hoặc tây. Hướng gió có thể thay đổi theo khoảng thời gian, nhưng tại cùng một khoảng thời gian trong ngày thì hướng gió giống nhau ở mọi ngày.

Mỗi cư dân \((i,j)\) có mức kháng vi-rút là số nguyên không âm \(U_{i,j}\):

• Nếu \(U_{i,j}=0\), cư dân này có sức đề kháng cao và không bao giờ nhiễm JOI Virus.
• Nếu \(U_{i,j}>0\), cư dân này có thể nhiễm JOI Virus. Nếu điều kiện sau được duy trì trong \(U_{i,j}\) khoảng thời gian liên tiếp, cư dân này sẽ nhiễm vi-rút kể từ khoảng thời gian tiếp theo: cư dân ở ô kề theo hướng mà gió thổi từ đó đến đã nhiễm JOI Virus.

Khoảng thời gian cuối cùng của một ngày và khoảng thời gian đầu tiên của ngày kế tiếp được tính là liên tiếp. Hướng gió trong chuỗi khoảng thời gian liên tiếp nói trên không nhất thiết phải giữ nguyên.

Để phục vụ thí nghiệm, công ty muốn có ít nhất một người nhiễm nhưng không muốn quá nhiều người nhiễm. Ban đầu, công ty chọn đúng một cư dân làm người nhiễm đầu tiên và cho người đó nhiễm JOI Virus. Không được chọn người có mức kháng vi-rút bằng \(0\).

Cho hướng gió trong từng khoảng thời gian và mức kháng vi-rút của từng cư dân, hãy tính số người nhiễm ít nhất sau \(10^{100}\) ngày, cùng số cách chọn người nhiễm đầu tiên để đạt được số người nhiễm ít nhất đó.

Dữ liệu vào

• Dòng đầu chứa \(M,R,C\).
• Dòng thứ hai chứa chuỗi \(D\) độ dài \(M\).
• Trong \(R\) dòng tiếp theo, dòng thứ \(i\) chứa \(U_{i,1},\ldots,U_{i,C}\).

Dữ liệu được đọc từ đầu vào chuẩn. Ký tự thứ \(k\) của \(D\) cho biết hướng mà gió thổi từ đó đến trong khoảng thời gian \(k\), không phải hướng gió thổi tới. Các ký tự N, S, W, E lần lượt chỉ bắc, nam, tây, đông.

Dữ liệu ra

Ghi hai dòng ra đầu ra chuẩn:

• Dòng thứ nhất chứa số người nhiễm ít nhất sau \(10^{100}\) ngày.
• Dòng thứ hai chứa số cư dân mà khi chọn làm người nhiễm đầu tiên sẽ đạt được số người nhiễm ít nhất đó.

Ràng buộc

• \(1\le M\le 100\,000\).
• \(1\le R\le 800\).
• \(1\le C\le 800\).
• \(D\) có độ dài \(M\) và chỉ gồm các ký tự N, S, W, E.
• \(0\le U_{i,j}\le 100\,000\) với \(1\le i\le R\), \(1\le j\le C\).
• Có ít nhất một cặp \((i,j)\) với \(1\le i\le R\), \(1\le j\le C\) và \(U_{i,j}\ge 1\).

Phân nhóm

1. \(14\) điểm: \(D\) chỉ gồm các ký tự W và E.
2. \(6\) điểm: \(1\le R\le 50\), \(1\le C\le 50\).
3. \(80\) điểm: Không có ràng buộc bổ sung.

Ví dụ

6 3 4
SWNEES
2 1 1 2
1 0 1 3
1 1 2 2

8
8

4 4 4
EWWE
1 2 1 2
1 1 1 1
0 0 0 0
2 2 2 4

3
3

Nguồn

JOI Open Contest 2019, bài Virus Experiment (virus), ngày 14/7/2019. Bản dịch từ đề tiếng Anh chính thức của JCIOI, theo giấy phép CC BY-SA 4.0.