JOI 2022 - Tuyển chọn mùa xuân - Ngày 1 - Bộ đề bài

#	Bài tập	Điểm	Thời gian:	Giới hạn bộ nhớ
1	JOI 2022 - Jail	100 (p)	4.0s	1G
2	JOI 2022 - Sightseeing in Kyoto	100 (p)	2.0s	1G
3	JOI 2022 - Misspelling	100 (p)	3.5s	1G

1. JOI 2022 - Jail

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

Nhà tù IOI nổi tiếng là nhà tù được quản lý nghiêm ngặt nhất vương quốc JOI. Nhà tù có \(N\) phòng, được đánh số từ \(1\) đến \(N\), và \(N-1\) hành lang. Hành lang thứ \(i\) (\(1\le i\le N-1\)) nối hai chiều phòng \(A_i\) với phòng \(B_i\). Từ một phòng bất kỳ có thể đi đến mọi phòng khác qua các hành lang.

Có \(M\) tù nhân, được đánh số từ \(1\) đến \(M\). Tù nhân \(j\) (\(1\le j\le M\)) có phòng ngủ là \(S_j\) và phòng làm việc là \(T_j\). Phòng ngủ của một người có thể là phòng làm việc của người khác. Tuy nhiên, không có hai người chung phòng ngủ, cũng không có hai người chung phòng làm việc.

Một buổi sáng, tất cả tù nhân phải đi từ phòng ngủ đến phòng làm việc. Giám đốc APIO sẽ lặp lại mệnh lệnh sau:

Chọn một tù nhân và chuyển người đó từ phòng hiện tại sang một phòng được nối trực tiếp bằng một hành lang. Để tránh các tù nhân nói chuyện với nhau, phòng đích không được có tù nhân khác.

Để công việc bắt đầu sớm, giám đốc muốn biết có thể đưa tất cả tù nhân đến phòng làm việc mà không ai đi qua cùng một phòng hai lần hay không. Nói cách khác, mỗi tù nhân phải đi theo đường đi ngắn nhất của mình.

Hãy viết chương trình xác định điều đó từ thông tin các phòng, hành lang và tù nhân.

Dữ liệu vào

Đọc từ đầu vào chuẩn. Mỗi bộ dữ liệu gồm \(Q\) tình huống, được đánh số từ \(1\) đến \(Q\):

Q
(Dữ liệu tình huống 1)
(Dữ liệu tình huống 2)
...
(Dữ liệu tình huống Q)

Mỗi tình huống có định dạng sau; tất cả giá trị đều là số nguyên:

N
A_1 B_1
A_2 B_2
...
A_{N-1} B_{N-1}
M
S_1 T_1
S_2 T_2
...
S_M T_M

Dữ liệu ra

In \(Q\) dòng ra đầu ra chuẩn. Dòng thứ \(k\) (\(1\le k\le Q\)) chứa Yes nếu có thể đưa tất cả tù nhân trong tình huống \(k\) đến phòng làm việc theo các đường đi ngắn nhất, hoặc No nếu không thể.

Ràng buộc

\(1\le Q\le 1\,000\).
\(2\le N\le 120\,000\).
\(1\le A_i<B_i\le N\) (\(1\le i\le N-1\)).
\(2\le M\le N\).
\(1\le S_j,T_j\le N\) và \(S_j\ne T_j\) (\(1\le j\le M\)).
Các giá trị \(S_1,S_2,\ldots,S_M\) đôi một khác nhau.
Các giá trị \(T_1,T_2,\ldots,T_M\) đôi một khác nhau.
Từ bất kỳ phòng nào đều đi được đến mọi phòng khác qua các hành lang.
Tổng \(N\) của cả \(Q\) tình huống không vượt quá \(120\,000\).

Phân nhóm

Các ràng buộc về một tình huống dưới đây phải đúng với mọi tình huống trong bộ dữ liệu.

Nhóm 1 (5 điểm): \(A_i=i\), \(B_i=i+1\) với mọi \(1\le i\le N-1\).
Nhóm 2 (5 điểm): \(Q\le 20\), \(N\le 250\), \(M=2\).
Nhóm 3 (16 điểm): \(Q\le 20\), \(N\le 250\), \(M\le 6\).
Nhóm 4 (28 điểm): \(Q\le 20\), \(N\le 250\), \(M\le 100\).
Nhóm 5 (12 điểm): \(Q\le 20\), \(M\le 500\).
Nhóm 6 (11 điểm): Từ bất kỳ phòng nào đều có thể đến mọi phòng khác qua không quá \(20\) hành lang.
Nhóm 7 (23 điểm): Không có ràng buộc bổ sung.

Ví dụ

Ví dụ 1

Input

Output

Yes

Giải thích

Có thể thực hiện các mệnh lệnh sau:

Chuyển tù nhân 2 từ phòng 4 sang phòng 5.
Chuyển tù nhân 1 từ phòng 3 sang phòng 4.
Chuyển tù nhân 2 từ phòng 5 sang phòng 6.
Chuyển tù nhân 2 từ phòng 6 sang phòng 7.
Chuyển tù nhân 2 từ phòng 7 sang phòng 8.

Mọi tù nhân đều đi theo đường đi ngắn nhất, nên in Yes. Cấu trúc nhà tù được minh họa bên dưới.

Ví dụ này thỏa mãn ràng buộc của tất cả các nhóm.

Ví dụ 2

Input

Output

Yes
No

Giải thích

Có \(Q=2\) tình huống. Trong tình huống 1, có thể thực hiện:

Chuyển tù nhân 1 từ phòng 4 sang phòng 3.
Chuyển tù nhân 1 từ phòng 3 sang phòng 2.
Chuyển tù nhân 2 từ phòng 5 sang phòng 4.
Chuyển tù nhân 2 từ phòng 4 sang phòng 3.
Chuyển tù nhân 2 từ phòng 3 sang phòng 6.
Chuyển tù nhân 1 từ phòng 2 sang phòng 1.
Chuyển tù nhân 2 từ phòng 6 sang phòng 7.

Ngược lại, trong tình huống 2 không thể đưa mọi tù nhân đến đích theo đường đi ngắn nhất. Vì vậy, dòng đầu in Yes, dòng thứ hai in No.

Ví dụ này thỏa mãn ràng buộc của các nhóm 3, 4, 5, 6, 7.

Ví dụ 3

Input

Output

Yes
No
Yes

Giải thích

Ví dụ này thỏa mãn ràng buộc của các nhóm 1, 3, 4, 5, 6, 7.

Nguồn

Bài toán thuộc JOI 2021/2022, trại huấn luyện mùa xuân, ngày thi 1 (20/03/2022). Bản gốc do JCIOI phát hành theo giấy phép CC BY-SA 4.0. Bản tiếng Việt là bản dịch từ đề chính thức.

2. JOI 2022 - Sightseeing in Kyoto

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

Kyoto là một địa điểm du lịch nổi tiếng thế giới, cũng nổi tiếng với mạng đường phố dạng ô bàn cờ. Bạn đang tham quan thành phố và muốn đi bộ đến một danh lam thắng cảnh nhanh nhất có thể. Bài toán xét mô hình đơn giản sau.

Thành phố có \(H\) con đường chạy theo hướng đông-tây và \(W\) con đường chạy theo hướng nam-bắc, chia thành phố thành lưới \((H-1)\times(W-1)\) ô vuông. Giao điểm của đường thứ \(i\) tính từ phía bắc (\(1\le i\le H\)) và đường thứ \(j\) tính từ phía tây (\(1\le j\le W\)) được ký hiệu là \((i,j)\).

Độ rộng, vật liệu và mức độ đông đúc của các đường khác nhau, nên tốc độ đi bộ trên chúng có thể khác nhau:

Đi một đơn vị độ dài trên đường thứ \(i\) từ phía bắc mất \(A_i\) giây. Cụ thể, với mỗi \(1\le c\le W-1\), đi từ giao điểm \((i,c)\) đến \((i,c+1)\) mất \(A_i\) giây.
Đi một đơn vị độ dài trên đường thứ \(j\) từ phía tây mất \(B_j\) giây. Cụ thể, với mỗi \(1\le r\le H-1\), đi từ giao điểm \((r,j)\) đến \((r+1,j)\) mất \(B_j\) giây.

Để không làm ảnh hưởng cảnh quan đẹp của Kyoto, bạn không được đi ra ngoài các con đường.

Bạn đang ở giao điểm \((1,1)\) và muốn đến \((H,W)\). Vì đi xa sẽ mệt, bạn không muốn đi vòng: bạn không bao giờ đi về phía bắc hoặc phía tây. Với điều kiện này, hãy tính thời gian ít nhất để đến đích.

Dữ liệu vào

Đọc từ đầu vào chuẩn theo định dạng sau. Tất cả giá trị đều là số nguyên.

H W
A_1 A_2 ... A_H
B_1 B_2 ... B_W

Dữ liệu ra

In một dòng chứa thời gian ít nhất, tính bằng giây, để đi bộ từ \((1,1)\) đến \((H,W)\) mà không đi vòng.

Ràng buộc

\(2\le H\le 100\,000\).
\(2\le W\le 100\,000\).
\(1\le A_i\le 1\,000\,000\,000\) (\(1\le i\le H\)).
\(1\le B_j\le 1\,000\,000\,000\) (\(1\le j\le W\)).

Phân nhóm

Nhóm 1 (10 điểm): \(H\le 1\,000\), \(W\le 1\,000\).
Nhóm 2 (30 điểm): \(A_i\le 1\,000\) với mọi \(i\), \(B_j\le 1\,000\) với mọi \(j\).
Nhóm 3 (60 điểm): Không có ràng buộc bổ sung.

Ví dụ

Ví dụ 1

Input

2 2
1 3
2 5

Output

Giải thích

Có hai đường đi từ \((1,1)\) đến \((2,2)\) mà không đi vòng:

\((1,1)\to(1,2)\to(2,2)\), mất \(A_1+B_2=1+5=6\) giây.
\((1,1)\to(2,1)\to(2,2)\), mất \(B_1+A_2=2+3=5\) giây.

Thời gian ít nhất là \(5\) giây, nên in 5. Hai đường đi được minh họa dưới đây. Số ghi cạnh mỗi đường là thời gian đi một đơn vị độ dài trên đường đó.

Ví dụ này thỏa mãn ràng buộc của tất cả các nhóm.

Ví dụ 2

Input

5 5
7 1 5 2 8
7 2 4 1 6

Output

Giải thích

Chẳng hạn, đi theo đường trong hình dưới đây sẽ mất \(20\) giây để đến \((5,5)\) từ \((1,1)\). Không có cách nào mất không quá \(19\) giây, nên in 20. Số ghi cạnh mỗi đường là thời gian đi một đơn vị độ dài trên đường đó.

Ví dụ này thỏa mãn ràng buộc của tất cả các nhóm.

Ví dụ 3

Input

4 6
454863204 543362989 866044086 813602010
71574269 17945210 688720933 392135202 38174709 168241720

Output

2737473954

Giải thích

Ví dụ này thỏa mãn ràng buộc của các nhóm 1, 3.

Nguồn

Bài toán thuộc JOI 2021/2022, trại huấn luyện mùa xuân, ngày thi 1 (20/03/2022). Bản gốc do JCIOI phát hành theo giấy phép CC BY-SA 4.0. Bản tiếng Việt là bản dịch từ đề chính thức.

3. JOI 2022 - Misspelling

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

Chủ tịch K từng có một xâu \(S\) độ dài \(N\) gồm các chữ cái tiếng Anh viết thường, nhưng ông đã quên mất xâu đó. Ông có một cuốn từ điển ghi nhiều kiểu lỗi chính tả và từng tra cứu các lỗi chính tả của \(S\). Vì vậy, ông còn nhớ thông tin sau:

Gọi \(T_i\) (\(1\le i\le N\)) là xâu thu được khi xóa ký tự thứ \(i\) của \(S\) rồi dồn các ký tự còn lại để lấp chỗ trống. Với mỗi \(1\le j\le M\), ta có \(T_{A_j}\le T_{B_j}\).

Ở đây, \(T_{A_j}\le T_{B_j}\) nghĩa là hai xâu bằng nhau, hoặc \(T_{A_j}\) nhỏ hơn \(T_{B_j}\) theo thứ tự từ điển (thứ tự bảng chữ cái).

Cho những thông tin mà chủ tịch K nhớ, hãy tính số xâu \(S\) không mâu thuẫn với chúng, lấy phần dư khi chia cho \(1\,000\,000\,007\).

Dữ liệu vào

Đọc từ đầu vào chuẩn theo định dạng sau. Tất cả giá trị đều là số nguyên.

N M
A_1 B_1
A_2 B_2
...
A_M B_M

Dữ liệu ra

In một dòng chứa số xâu \(S\) không mâu thuẫn với thông tin đã cho, lấy phần dư khi chia cho \(1\,000\,000\,007\).

Ràng buộc

\(2\le N\le 500\,000\).
\(1\le M\le 500\,000\).
\(1\le A_j,B_j\le N\) và \(A_j\ne B_j\) (\(1\le j\le M\)).
\((A_j,B_j)\ne(A_k,B_k)\) với mọi \(1\le j<k\le M\).

Phân nhóm

Nhóm 1 (8 điểm): \(N\le 10\).
Nhóm 2 (20 điểm): \(N\le 200\).
Nhóm 3 (29 điểm): \(M=N-1\). Ngoài ra, tồn tại một hoán vị \(P\) của \((1,2,\ldots,N)\) sao cho \(A_j=P_j\) và \(B_j=P_{j+1}\) với mọi \(1\le j\le M\).
Nhóm 4 (32 điểm): \(N\le 20\,000\).
Nhóm 5 (11 điểm): Không có ràng buộc bổ sung.

Ví dụ

Ví dụ 1

Input

3 2
1 3
3 2

Output

Giải thích

Ví dụ, với \(S=\) bab, ta có \(T_1=\) ab, \(T_2=\) bb, \(T_3=\) ba. Hai quan hệ \(T_1\le T_3\) và \(T_3\le T_2\) đều đúng, nên xâu này không mâu thuẫn với thông tin đã cho. Tổng cộng có \(5\,876\) xâu phù hợp, nên in 5876.

Ngược lại, với \(S=\) aab, ta có \(T_1=\) ab, \(T_2=\) ab, \(T_3=\) aa. Quan hệ \(T_1\le T_3\) không đúng, nên xâu này mâu thuẫn với thông tin đã cho.

Ví dụ này thỏa mãn ràng buộc của tất cả các nhóm.

Ví dụ 2

Input

Output

Giải thích

Ví dụ này thỏa mãn ràng buộc của các nhóm 1, 2, 4, 5.

Ví dụ 3

Input

Output

206289833

Giải thích

Có \(824\,206\,295\,601\) xâu phù hợp. Phần dư của số này khi chia cho \(1\,000\,000\,007\) là \(206\,289\,833\), nên in 206289833.

Ví dụ này thỏa mãn ràng buộc của các nhóm 1, 2, 4, 5.

Ví dụ 4

Input

Output

Giải thích

Ví dụ này thỏa mãn ràng buộc của tất cả các nhóm.

Ví dụ 5

Input

Output

Giải thích

Ví dụ này thỏa mãn ràng buộc của tất cả các nhóm.

Nguồn

Bài toán thuộc JOI 2021/2022, trại huấn luyện mùa xuân, ngày thi 1 (20/03/2022). Bản gốc do JCIOI phát hành theo giấy phép CC BY-SA 4.0. Bản tiếng Việt là bản dịch từ đề chính thức.