JOI 2020 - Second Qualifier

JOI đã làm một tấm áp phích để quảng bá hoạt động của lớp trong lễ hội văn hóa. Tấm áp phích có dạng bảng gồm \(N\) hàng và \(N\) cột, mỗi ô được tô màu đỏ, xanh lá cây hoặc xanh dương. Ô ở hàng \(i\) từ trên xuống và cột \(j\) từ trái sang (\(1 \le i,j \le N\)) có màu đỏ nếu \(S_{i,j}\) là R, xanh lá cây nếu là G, và xanh dương nếu là B.

Tuy nhiên, các bạn trong lớp chưa hài lòng với tấm áp phích này. Sau khi thảo luận, cả lớp quyết định giữ nguyên hình dạng bảng và thay đổi cách bố trí màu để làm một tấm áp phích mới. Trong tấm áp phích mới, ô ở hàng \(i\) từ trên xuống và cột \(j\) từ trái sang (\(1 \le i,j \le N\)) phải có màu đỏ nếu \(T_{i,j}\) là R, xanh lá cây nếu là G, và xanh dương nếu là B.

JOI sẽ lặp lại các thao tác sau trên tấm áp phích hiện có để tạo ra tấm áp phích mới:

• Chọn một ô và tô lại ô đó bằng màu tùy ý.
• Xoay toàn bộ tấm áp phích \(90^\circ\) theo chiều kim đồng hồ. Ô ban đầu ở hàng \(i\), cột \(j\) chuyển đến hàng \(j\), cột \(N-i+1\).
• Xoay toàn bộ tấm áp phích \(90^\circ\) ngược chiều kim đồng hồ. Ô ban đầu ở hàng \(i\), cột \(j\) chuyển đến hàng \(N-j+1\), cột \(i\).

Mỗi thao tác đều mất \(1\) phút. Cho thông tin về tấm áp phích hiện có và tấm áp phích cần tạo, hãy tìm số phút ít nhất để JOI tạo được tấm áp phích mới.

Dữ liệu vào

Dữ liệu được cho từ đầu vào chuẩn. Dòng đầu chứa \(N\). Tiếp theo là \(N\) dòng mô tả bảng \(S\), rồi \(N\) dòng mô tả bảng \(T\), theo thứ tự từ trên xuống. Mỗi dòng của một bảng chứa \(N\) ký tự liền nhau, theo thứ tự từ trái sang.

Dữ liệu ra

In ra một dòng chứa số phút ít nhất cần để tạo ra tấm áp phích mới.

Ràng buộc

• \(1 \le N \le 500\).
• \(S_{i,j}\) là một trong các ký tự R, G, B.
• \(T_{i,j}\) là một trong các ký tự R, G, B.

Ví dụ

3
RRR
GGG
BBB
RRR
RRR
RRR

6

3
RRR
GGG
BBB
RGB
RGB
RGB

1

6
RRRBBB
RRRBBB
RRRBBB
GGGRRG
GGGRRG
GGGBBR
RRRGGG
RRRGGG
RRRGGG
BBBRRB
BBBRRB
BBBGGR

10

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

Trang trại dâu tây Just Oishi Ichigo (gọi tắt là trang trại JOI) nổi tiếng vì có hình dạng dài và hẹp theo hướng đông-tây. Lối vào nằm ở đầu phía tây của trang trại. Ta gọi vị trí cách lối vào \(k\) mét về phía đông là vị trí \(k\).

Trong trang trại có \(N\) quả dâu tây, được đánh số từ \(1\) đến \(N\). Ban đầu các quả đều còn xanh. Quả dâu thứ \(i\) (\(1 \le i \le N\)) nằm ở vị trí \(A_i\) và chín đỏ vào thời điểm \(T_i\).

Không thể thu hoạch một quả khi nó còn xanh; tức là chỉ có thể thu hoạch quả thứ \(i\) từ thời điểm \(T_i\) trở đi. Bạn xuất phát từ lối vào ở vị trí \(0\) vào thời điểm \(0\), di chuyển theo hướng đông hoặc tây với tốc độ tối đa \(1\) mét mỗi giây để thu hoạch dâu. Có thể bỏ qua thời gian thu hoạch.

Cho thông tin về trang trại, hãy tìm thời gian ít nhất để thu hoạch tất cả các quả dâu khi chúng đã chín đỏ, rồi trở về lối vào.

Dữ liệu vào

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

N
A_1 T_1
A_2 T_2
...
A_N T_N

Dữ liệu ra

In ra một dòng chứa thời gian ít nhất, tính bằng giây, để thu hoạch tất cả các quả dâu khi chúng đã chín đỏ rồi trở về lối vào.

Ràng buộc

• \(1 \le N \le 100\,000\).
• \(0 \le A_i \le 1\,000\,000\,000=10^9\) với \(1 \le i \le N\).
• \(0 \le T_i \le 1\,000\,000\,000=10^9\) với \(1 \le i \le N\).
• Tất cả các giá trị đầu vào đều là số nguyên.

Ví dụ

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

20

10
0 450
5 445
10 430
15 405
20 370
25 325
30 270
35 205
40 130
45 45

450

15
11 23
3 94
89 3
38 58
65 29
41 3
80 42
22 76
48 85
83 98
87 29
97 96
22 75
57 25
99 33

198

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

Ban đầu JOI có một số nguyên từ \(1\) đến \(N\). Sau khi thực hiện thao tác dưới đây không hoặc nhiều lần, số nguyên của JOI trở thành \(N\):

• Cộng vào số nguyên hiện tại tổng các chữ số trong biểu diễn thập phân của chính số đó.

Cho \(N\), hãy tìm có bao nhiêu số nguyên có thể là số mà JOI có ban đầu.

Dữ liệu vào

Dữ liệu được cho từ đầu vào chuẩn gồm một dòng chứa \(N\).

Dữ liệu ra

In ra một dòng chứa số lượng số nguyên có thể là số mà JOI có ban đầu.

Ràng buộc

• \(1 \le N \le 1\,000\,000\).
• \(N\) là số nguyên.

Ví dụ

13

4

20

1

2019

449

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

JOI có một bàn phím số với các phím mang chữ số từ \(0\) đến \(9\), được bố trí như hình dưới đây. Lưu ý rằng không có phím nào ở ngay dưới phím \(2\) hoặc phím \(3\).

Trên bàn phím có một con trỏ chỉ vào một phím. Ban đầu con trỏ chỉ vào phím \(0\).

Trong mỗi thao tác, JOI có thể chọn một trong hai việc sau:

• Di chuyển con trỏ sang một phím kề với phím hiện tại theo hướng lên, xuống, trái hoặc phải. Không được di chuyển đến vị trí không có phím.
• Nhấn phím mà con trỏ đang chỉ vào để nhập chữ số trên phím đó. Nếu trước đó đã nhập các chữ số, chữ số mới được thêm ngay bên phải dãy chữ số đã nhập.

JOI muốn dùng bàn phím này để nhập một số nguyên dương có số dư bằng \(R\) khi chia cho \(M\). Vì thao tác trên bàn phím mất thời gian, JOI muốn dùng ít thao tác nhất có thể.

Cho \(M\) và \(R\), hãy tìm số thao tác ít nhất JOI cần thực hiện.

Dữ liệu vào

Dữ liệu được cho từ đầu vào chuẩn gồm một dòng chứa hai số nguyên \(M\) và \(R\).

Dữ liệu ra

In ra một dòng chứa số thao tác ít nhất để nhập một số nguyên dương có số dư bằng \(R\) khi chia cho \(M\).

Ràng buộc

• \(2 \le M \le 100\,000\).
• \(1 \le R < M\).
• Tất cả các giá trị đầu vào đều là số nguyên.

Phân nhóm

1. (30 điểm) \(M=100\,000\).
2. (70 điểm) Không có ràng buộc bổ sung.

Ví dụ

100000 13

5

4 3

3

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

Trong bài toán này, ba lựa chọn búa, kéo, bao được ký hiệu lần lượt là R, S, P. R thắng S, S thắng P, và P thắng R.

Với hai lựa chọn \(x,y\), ta định nghĩa các phép toán x + y, x - y, x * y như sau. Đây không phải là các phép cộng, trừ, nhân thông thường.

• x + y: nếu \(x \ne y\), kết quả là lựa chọn thắng trong hai lựa chọn \(x,y\); nếu \(x=y\), kết quả là \(x\).
• x - y: nếu \(x \ne y\), kết quả là lựa chọn thua trong hai lựa chọn \(x,y\); nếu \(x=y\), kết quả là \(x\).
• x * y: nếu \(x \ne y\), kết quả là lựa chọn còn lại trong R, S, P, khác cả \(x\) lẫn \(y\); nếu \(x=y\), kết quả là \(x\).

Một biểu thức gồm các lựa chọn, các phép toán +, -, * và dấu ngoặc được tính theo những quy tắc sau:

• Tính phần trong ngoặc trước. Ví dụ: R * (P + S) = R * S = P.
• Ở cùng một mức lồng ngoặc, * có độ ưu tiên cao hơn + và -. Ví dụ: R - P * S = R - (P * S) = R - R = R.
• Ở cùng một mức lồng ngoặc, các phép toán có cùng độ ưu tiên được thực hiện từ trái sang phải: các phép + với nhau, các phép - với nhau, + với -, và các phép * với nhau. Ví dụ: R - P + S = (R - P) + S = R + S = R.

JOI có một biểu thức như trên, nhưng một số ký tự R, S, P trong đó đã bị che mất. Bạn được cho xâu \(E\) có độ dài \(N\), trong đó mỗi ký tự bị che được thay bằng ?. JOI muốn biết có bao nhiêu cách thay mỗi dấu ? bằng một trong ba ký tự R, S, P để giá trị của biểu thức bằng \(A\). Vì số cách có thể rất lớn, hãy tính số dư của số cách khi chia cho \(1\,000\,000\,007\).

Ngữ pháp được dùng trong bài toán được mô tả bằng BNF (ký pháp Backus-Naur) như sau. Biểu thức có một số ký tự bị che là một <expression>.

<expression> ::= <term> | <expression> "+" <term> | <expression> "-" <term>
<term> ::= <factor> | <term> "*" <factor>
<factor> ::= "R" | "S" | "P" | "?" | "(" <expression> ")"

Đây là một định nghĩa đệ quy. Chẳng hạn, một xâu là <expression> nếu nó là <term>, hoặc là kết quả nối lần lượt một xâu <expression>, ký tự + và một xâu <term>, hoặc là kết quả nối lần lượt một xâu <expression>, ký tự - và một xâu <term>.

Cho xâu \(E\) là một <expression> và kết quả cần đạt \(A\), hãy tính số cách thay các dấu ? bằng R, S, P để giá trị biểu thức bằng \(A\), lấy số dư khi chia cho \(1\,000\,000\,007\).

Dữ liệu vào

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

N
E
A

Dữ liệu ra

In ra một dòng chứa số cách thay mỗi dấu ? bằng R, S hoặc P để giá trị biểu thức bằng \(A\), lấy số dư khi chia cho \(1\,000\,000\,007\).

Ràng buộc

• \(1 \le N \le 200\,000\).
• \(E\) là xâu có độ dài \(N\).
• \(E\) là một <expression> theo định nghĩa trong đề bài.
• \(A\) là R, S hoặc P.

Phân nhóm

1. (20 điểm) \(N \le 15\).
2. (20 điểm) \(N \le 200\).
3. (60 điểm) Không có ràng buộc bổ sung.

Ví dụ

11
S+?-(R+?)*P
S

6

15
?+?-?*?+?-?*?+?
R

2187

13
(((((R)))))+?
P

1

1
P
S

0

27
R+((?+S-?*P+?)-P*?+S-?)*R+?
P

381

83
((R+?)*(?+?))*((?+?)*(?+?))*((?+?)*(?+?))-((S+?)*(?+?))*((?+?)*(?+?))*((?+?)*(?+?))
P

460353133

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