JOI 2019 - Vòng loại - Bộ đề bài - LQDOJ: Le Quy Don Online Judge

#	Bài tập	Điểm	Thời gian:	Giới hạn bộ nhớ
1	JOI 2019 - Social Game	100 (p)	2.0s	256M
2	JOI 2019 - Sugoroku and Pieces	100 (p)	2.0s	256M
3	JOI 2019 - Circle Cross Stamps	100 (p)	2.0s	256M
4	JOI 2019 - Japan Sinks	100 (p)	2.0s	256M
5	JOI 2019 - Illumination	100 (p)	2.0s	256M
6	JOI 2019 - Seats	100 (p)	5.0s	256M

1. JOI 2019 - Social Game

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

JOI quyết định bắt đầu chơi một trò chơi trực tuyến từ ngày mai.

Trong trò chơi này, mỗi ngày cậu có thể đăng nhập nhiều nhất một lần. Mỗi lần đăng nhập, cậu nhận được \(A\) đồng xu. Ngoài ra, mỗi khi đăng nhập đủ \(7\) ngày liên tiếp từ thứ Hai đến Chủ nhật, cậu được thưởng thêm \(B\) đồng xu. Không có cách nào khác để nhận xu.

Ngày mai là thứ Hai. Hãy tìm số lần đăng nhập ít nhất để JOI nhận được ít nhất \(C\) đồng xu.

Dữ liệu vào

Dữ liệu được cho từ đầu vào chuẩn theo định dạng sau:

A B C

Dữ liệu ra

In ra số lần đăng nhập ít nhất để JOI nhận được ít nhất \(C\) đồng xu.

Ràng buộc

\(A, B, C\) là các số nguyên.
\(1 \le A \le 1000\).
\(0 \le B \le 1000\).
\(1 \le C \le 10^6\).

Phân nhóm

Nhóm 1 (40 điểm): \(1 \le A \le 1000\), \(B=0\), \(1 \le C \le 10^6\).
Nhóm 2 (60 điểm): \(1 \le A \le 1000\), \(0 \le B \le 1000\), \(1 \le C \le 10^6\).

Ví dụ

Ví dụ 1

Input

3 0 10

Output

Giải thích

Mỗi lần đăng nhập nhận được \(3\) đồng xu, và JOI muốn có ít nhất \(10\) đồng xu. Đăng nhập liên tiếp \(4\) ngày kể từ thứ Hai giúp cậu nhận được \(12\) đồng xu. Không thể nhận được ít nhất \(10\) đồng xu chỉ với \(3\) lần đăng nhập hoặc ít hơn, nên đáp án là \(4\).

Ví dụ 2

Input

1 2 10

Output

Giải thích

Mỗi lần đăng nhập nhận được \(1\) đồng xu; đăng nhập đủ một tuần từ thứ Hai đến Chủ nhật được thưởng thêm \(2\) đồng xu. JOI muốn có ít nhất \(10\) đồng xu.

Sau khi đăng nhập liên tiếp từ thứ Hai đến Chủ nhật, cậu có \(7+2=9\) đồng xu. Đăng nhập thêm một lần nữa giúp cậu có \(10\) đồng xu. Không thể đạt ít nhất \(10\) đồng xu với \(7\) lần đăng nhập hoặc ít hơn, nên đáp án là \(8\).

Nguồn

Bản dịch tiếng Việt từ đề gốc tiếng Nhật của Ủy ban Olympic Tin học Nhật Bản, vòng loại JOI 2018/2019. Đề gốc và bản dịch được cung cấp theo giấy phép CC BY-SA 4.0.

2. JOI 2019 - Sugoroku and Pieces

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

JOI có một bàn chơi sugoroku gồm \(2019\) ô nằm trên một hàng ngang. Các ô được đánh số từ \(1\) đến \(2019\), theo thứ tự từ ô xuất phát ở đầu bên trái đến ô đích ở đầu bên phải.

Hiện có \(N\) quân cờ trên bàn. Các quân được đánh số từ \(1\) đến \(N\) theo thứ tự từ gần ô xuất phát nhất đến xa nhất. Quân \(i\) đang ở ô \(X_i\) với \(1 \le i \le N\). Mỗi quân nằm ở một ô khác nhau.

JOI sẽ thực hiện \(M\) thao tác. Trong thao tác thứ \(j\) với \(1 \le j \le M\), cậu thử đưa quân \(A_j\) tiến một ô về phía đích. Tuy nhiên, nếu quân đó đã ở ô đích hoặc ô ngay phía trước đã có quân khác, nó không di chuyển và vẫn ở vị trí cũ.

Hãy xác định vị trí của từng quân sau khi thực hiện tất cả các thao tác.

Dữ liệu vào

Dữ liệu được cho từ đầu vào chuẩn theo định dạng sau:

N
X_1 X_2 ... X_N
M
A_1 A_2 ... A_M

Dữ liệu ra

In ra \(N\) dòng. Dòng thứ \(i\) chứa số hiệu ô mà quân \(i\) đang đứng sau tất cả các thao tác, với \(1 \le i \le N\).

Ràng buộc

Các giá trị đầu vào đều là số nguyên.
\(1 \le N \le 100\).
\(1 \le X_1 < X_2 < \cdots < X_N \le 2019\).
\(1 \le M \le 100\).
\(1 \le A_j \le N\) với \(1 \le j \le M\).

Ví dụ

Ví dụ 1

Input

Output

2
3
7

Giải thích

Ở thao tác đầu tiên, quân \(1\) thử tiến từ ô \(2\) đến ô \(3\). Tuy nhiên, quân \(2\) đã ở ô \(3\), nên quân \(1\) không di chuyển.

Ở thao tác thứ hai, quân \(3\) tiến từ ô \(6\) đến ô \(7\). Cuối cùng, các quân \(1,2,3\) lần lượt ở các ô \(2,3,7\).

Ví dụ 2

Input

Output

1
2019

Giải thích

Sau thao tác thứ ba, quân \(2\) đã đến ô \(2019\). Vì vậy, quân này không di chuyển trong thao tác thứ tư.

Ví dụ 3

Input

4
1001 1002 1003 1004
7
1 2 3 4 3 2 1

Output

Nguồn

Bản dịch tiếng Việt từ đề gốc tiếng Nhật của Ủy ban Olympic Tin học Nhật Bản, vòng loại JOI 2018/2019. Đề gốc và bản dịch được cung cấp theo giấy phép CC BY-SA 4.0.

3. JOI 2019 - Circle Cross Stamps

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

JOI có ba loại con dấu: con dấu tròn, con dấu chéo và con dấu tròn-chéo. Với mỗi loại, cậu có thể có từ \(0\) con dấu trở lên. Các con dấu này dùng để in dấu tròn hoặc dấu chéo lên giấy.

Một con dấu tròn in ra một dấu tròn; một con dấu chéo in ra một dấu chéo. Một con dấu tròn-chéo in ra một dấu tròn và một dấu chéo nằm cạnh nhau trên một hàng ngang. Bằng cách xoay con dấu, có thể in dấu chéo ở bên phải dấu tròn hoặc in dấu tròn ở bên phải dấu chéo.

JOI đã dùng mỗi con dấu mình có đúng một lần, theo một thứ tự thích hợp, để in thành một hàng gồm các dấu tròn và dấu chéo. Hàng dấu đã in được biểu diễn bởi chuỗi \(S\) có độ dài \(N\), chỉ gồm hai ký tự O và X. Với \(1 \le i \le N\), ký tự \(S_i\) là O nếu dấu thứ \(i\) từ trái sang là dấu tròn, và là X nếu đó là dấu chéo.

Bạn không biết JOI có bao nhiêu con dấu mỗi loại, nhưng biết hàng dấu mà cậu đã in. Hãy tìm số con dấu tròn-chéo lớn nhất mà JOI có thể đã có.

Dữ liệu vào

Dữ liệu được cho từ đầu vào chuẩn theo định dạng sau:

N
S

Dữ liệu ra

In ra số con dấu tròn-chéo lớn nhất mà JOI có thể đã có.

Ràng buộc

\(N\) là số nguyên, \(1 \le N \le 10^5\).
\(S\) có độ dài \(N\).
Mỗi ký tự của \(S\) là O hoặc X.

Ví dụ

Ví dụ 1

Input

5
OXXOX

Output

Giải thích

Từ trái sang, JOI đã in các dấu tròn, chéo, chéo, tròn, chéo. Giả sử cậu có \(0\) con dấu tròn, \(1\) con dấu chéo và \(2\) con dấu tròn-chéo. Cậu có thể in hàng dấu đó như sau:

Dùng con dấu tròn-chéo thứ nhất để in OX.
Ở bên phải, dùng con dấu tròn-chéo thứ hai để in XO.
Cuối cùng, ở bên phải, dùng con dấu chéo để in X.

Không thể có từ \(3\) con dấu tròn-chéo trở lên, nên in ra \(2\).

Ví dụ 2

Input

14
OXOXOXOXXOXOXO

Output

Ví dụ 3

Input

10
OOOOOOOOOO

Output

Nguồn

Bản dịch tiếng Việt từ đề gốc tiếng Nhật của Ủy ban Olympic Tin học Nhật Bản, vòng loại JOI 2018/2019. Đề gốc và bản dịch được cung cấp theo giấy phép CC BY-SA 4.0.

4. JOI 2019 - Japan Sinks

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

Quần đảo Nhật Bản có hình dạng dài và hẹp. Các đường ranh giới song song chia quần đảo thành \(N\) vùng, được đánh số từ \(1\) đến \(N\) theo thứ tự từ một đầu đến đầu còn lại. Vùng \(i\) có độ cao \(A_i\), với \(1 \le i \le N\).

Quần đảo được biển bao quanh, và mực nước biển tại mọi nơi đều bằng nhau. Một vùng được gọi là đất liền nếu độ cao của nó lớn hơn mực nước biển.

Một phần đất liền liên tiếp được gọi là một đảo. Chính xác hơn, với các số nguyên \(l,r\) thỏa mãn \(1 \le l \le r \le N\), gọi phần gồm các vùng \(l,l+1,\ldots,r\) là đoạn \([l,r]\). Đoạn này là một đảo nếu thỏa mãn tất cả các điều kiện sau:

Các vùng \(l,l+1,\ldots,r\) đều là đất liền.
Nếu \(l>1\), vùng \(l-1\) không phải là đất liền.
Nếu \(r<N\), vùng \(r+1\) không phải là đất liền.

Do mực nước biển dâng lên, Nhật Bản đang dần chìm xuống. Mực nước biển hiện tại bằng \(0\); theo thời gian, nó tăng dần cho đến khi toàn bộ Nhật Bản bị ngập.

JOI nhận thấy số đảo có thể tăng hoặc giảm khi mực nước biển dâng. Hãy tìm số đảo lớn nhất trong khoảng thời gian từ hiện tại cho đến khi không còn đất liền, tính cả thời điểm hiện tại.

Dữ liệu vào

Dữ liệu được cho từ đầu vào chuẩn theo định dạng sau:

N
A_1 A_2 ... A_N

Dữ liệu ra

In ra một dòng chứa số đảo lớn nhất trong khoảng thời gian đã nêu.

Ràng buộc

Các giá trị đầu vào đều là số nguyên.
\(1 \le N \le 10^5\).
\(0 \le A_i \le 10^9\) với \(1 \le i \le N\).

Phân nhóm

Nhóm 1 (7 điểm): \(1 \le N \le 2000\) và \(0 \le A_i \le 2000\) với mọi \(1 \le i \le N\).
Nhóm 2 (8 điểm): \(1 \le N \le 2000\) và \(0 \le A_i \le 10^9\) với mọi \(1 \le i \le N\).
Nhóm 3 (85 điểm): \(1 \le N \le 10^5\) và \(0 \le A_i \le 10^9\) với mọi \(1 \le i \le N\).

Ví dụ

Ví dụ 1

Input

6
0 1 2 1 3 2

Output

Giải thích

Gọi mực nước biển là \(h\).

Khi \(0 \le h < 1\), các vùng \(2,3,4,5,6\) là đất liền. Đoạn \([2,6]\) là đảo duy nhất, nên có \(1\) đảo.
Khi \(1 \le h < 2\), các vùng \(3,5,6\) là đất liền. Hai đoạn \([3,3]\) và \([5,6]\) là đảo, nên có \(2\) đảo.
Khi \(2 \le h < 3\), chỉ vùng \(5\) là đất liền. Đoạn \([5,5]\) là đảo duy nhất, nên có \(1\) đảo.
Khi \(h=3\), không còn đất liền và số đảo bằng \(0\).

Số đảo lớn nhất là \(2\), nên in ra \(2\).

Ví dụ 2

Input

6
3 2 3 0 2 0

Output

Giải thích

Gọi mực nước biển là \(h\).

Khi \(0 \le h < 2\), các vùng \(1,2,3,5\) là đất liền. Hai đoạn \([1,3]\) và \([5,5]\) là đảo, nên có \(2\) đảo.
Khi \(2 \le h < 3\), các vùng \(1,3\) là đất liền. Hai đoạn \([1,1]\) và \([3,3]\) là đảo, nên có \(2\) đảo.
Khi \(h=3\), không còn đất liền và số đảo bằng \(0\).

Số đảo lớn nhất là \(2\), nên in ra \(2\).

Ví dụ 3

Input

10
4 1 2 1 2 3 5 4 3 2

Output

Nguồn

Bản dịch tiếng Việt từ đề gốc tiếng Nhật, đối chiếu với bản trên AtCoder, của Ủy ban Olympic Tin học Nhật Bản, vòng loại JOI 2018/2019. Đề gốc và bản dịch được cung cấp theo giấy phép CC BY-SA 4.0.

5. JOI 2019 - Illumination

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

Ông JOI có \(N\) cây trong khuôn viên nhà mình. Các cây nằm trên một hàng và được đánh số từ \(1\) đến \(N\) theo thứ tự.

Mùa đông này, ông quyết định chọn một số cây để trang trí đèn. Việc trang trí đèn cho cây \(i\) mang lại độ đẹp bằng \(A_i\).

Ông JOI nhận thấy rằng trang trí đèn cho cả hai cây quá gần nhau có thể gây chói mắt. Cụ thể, với mỗi \(j=1,2,\ldots,M\), trong các cây \(L_j,L_j+1,\ldots,R_j\), không được trang trí đèn cho từ hai cây trở lên.

Hãy tìm tổng độ đẹp lớn nhất có thể đạt được khi tuân thủ tất cả các điều kiện trên.

Dữ liệu vào

Dữ liệu được cho từ đầu vào chuẩn theo định dạng sau:

N M
A_1 A_2 ... A_N
L_1 R_1
L_2 R_2
...
L_M R_M

Dữ liệu ra

In ra một dòng chứa tổng độ đẹp lớn nhất có thể đạt được.

Ràng buộc

Các giá trị đầu vào đều là số nguyên.
\(1 \le N \le 2\times 10^5\).
\(1 \le M \le 2\times 10^5\).
\(1 \le A_i \le 10^9\) với \(1 \le i \le N\).
\(1 \le L_j \le R_j \le N\) với \(1 \le j \le M\).

Phân nhóm

Nhóm 1 (10 điểm): \(1 \le N,M \le 16\); \(1 \le A_i \le 10^9\) với \(1 \le i \le N\); \(1 \le L_j \le R_j \le N\) với \(1 \le j \le M\).
Nhóm 2 (30 điểm): \(1 \le N,M \le 300\); \(1 \le A_i \le 10^9\) với \(1 \le i \le N\); \(1 \le L_j \le R_j \le N\) với \(1 \le j \le M\).
Nhóm 3 (30 điểm): \(1 \le N,M \le 4000\); \(1 \le A_i \le 10^9\) với \(1 \le i \le N\); \(1 \le L_j \le R_j \le N\) với \(1 \le j \le M\).
Nhóm 4 (30 điểm): \(1 \le N,M \le 2\times 10^5\); \(1 \le A_i \le 10^9\) với \(1 \le i \le N\); \(1 \le L_j \le R_j \le N\) với \(1 \le j \le M\).

Ví dụ

Ví dụ 1

Input

4 1
1 2 3 8
2 4

Output

Giải thích

Trang trí đèn cho các cây \(1\) và \(4\) cho tổng độ đẹp lớn nhất là \(9\).

Vì \(L_1=2\) và \(R_1=4\), không được trang trí đèn cho từ hai cây trở lên trong các cây \(2,3,4\). Chẳng hạn, không thể đồng thời trang trí các cây \(1,2,4\).

Ví dụ 2

Input

Output

Ví dụ 3

Input

20 10
870851814 594414687 615919461 65033245 460143082 617460823 881870957 126041265 623075703 34130727 27054628 853567651 483228744 491145755 220689940 148007930 229257101 790404982 612186806 281076231
15 19
20 20
12 13
1 4
19 19
9 13
3 6
9 12
16 16
18 19

Output

4912419478

Nguồn

Bản dịch tiếng Việt từ đề gốc tiếng Nhật của Ủy ban Olympic Tin học Nhật Bản, vòng loại JOI 2018/2019. Đề gốc và bản dịch được cung cấp theo giấy phép CC BY-SA 4.0.

6. JOI 2019 - Seats

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

Vào năm 2XXX, các quốc gia trên thế giới nằm trên một đường thẳng. Có \(N\) quốc gia, được đánh số \(1,2,\ldots,N\). Với mỗi \(i=1,2,\ldots,N-1\), quốc gia \(i\) và quốc gia \(i+1\) là hai nước láng giềng.

Tại kỳ Olympic Tin học Quốc tế năm đó, quốc gia \(i\) có \(A_i\) thí sinh tham dự. Bạn là thành viên ban kỹ thuật, phụ trách lập sơ đồ chỗ ngồi cho các thí sinh. Do phòng thi dài và hẹp, các thí sinh phải được xếp vào \(A_1+A_2+\cdots+A_N\) chỗ ngồi trên một hàng.

Để ngăn ngừa gian lận, hai thí sinh đến từ cùng một quốc gia hoặc từ hai quốc gia láng giềng không được ngồi cạnh nhau. Các thí sinh là những người phân biệt, kể cả khi họ đến từ cùng một quốc gia.

Có bao nhiêu cách xếp các thí sinh vào các chỗ ngồi? Vì kết quả có thể rất lớn, hãy tìm phần dư của số cách khi chia cho \(10007\).

Dữ liệu vào

Dữ liệu được cho từ đầu vào chuẩn theo định dạng sau:

N
A_1 A_2 ... A_N

Dữ liệu ra

In ra một dòng chứa số cách xếp chỗ ngồi thỏa mãn điều kiện, lấy phần dư khi chia cho \(10007\).

Ràng buộc

Các giá trị đầu vào đều là số nguyên.
\(1 \le N \le 100\).
\(1 \le A_i \le 4\) với \(1 \le i \le N\).

Phân nhóm

Nhóm 1 (6 điểm): \(1 \le N \le 5\) và \(1 \le A_i \le 2\) với mọi \(1 \le i \le N\).
Nhóm 2 (14 điểm): \(1 \le N \le 10\) và \(1 \le A_i \le 3\) với mọi \(1 \le i \le N\).
Nhóm 3 (80 điểm): \(1 \le N \le 100\) và \(1 \le A_i \le 4\) với mọi \(1 \le i \le N\).

Ví dụ

Ví dụ 1

Input

4
2 1 1 1

Output

Giải thích

Gọi hai thí sinh của quốc gia \(1\) là \(1\) và \(1'\), còn thí sinh của các quốc gia \(2,3,4\) lần lượt là \(2,3,4\). Có đúng bốn thứ tự xếp từ trái sang phải:

\(1,3,1',4,2\).
\(1',3,1,4,2\).
\(2,4,1,3,1'\).
\(2,4,1',3,1\).

Ví dụ 2

Input

5
1 2 3 2 1

Output

Giải thích

Không có sơ đồ chỗ ngồi nào thỏa mãn điều kiện.

Ví dụ 3

Input

6
1 2 3 3 2 1

Output

Giải thích

Có \(24768\) cách xếp chỗ ngồi. Phần dư của \(24768\) khi chia cho \(10007\) là \(4754\), nên in ra \(4754\).

Nguồn

Bản dịch tiếng Việt từ đề gốc tiếng Nhật, đối chiếu với bản trên AtCoder, của Ủy ban Olympic Tin học Nhật Bản, vòng loại JOI 2018/2019. Đề gốc và bản dịch được cung cấp theo giấy phép CC BY-SA 4.0.