JOI 2020 - Trại huấn luyện mùa xuân - Ngày 4

Bộ đề bài

Trở lại kỳ thi
# Bài tập Điểm Thời gian: Giới hạn bộ nhớ
1 JOI 2020 - Capital City 100 (p) 2.5s 512M
2 JOI 2020 - Legendary Dango Maker 100 (p) 10.0s 512M
3 JOI 2020 - Treatment Project 100 (p) 2.0s 512M

1. JOI 2020 - Capital City

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

Vương quốc JOI có \(N\) thị trấn, đánh số từ \(1\) đến \(N\). Có \(N-1\) con đường nối các thị trấn. Đường thứ \(i\) (\(1 \le i \le N-1\)) nối thị trấn \(A_i\) và thị trấn \(B_i\), đi được theo cả hai chiều. Có thể đi từ bất kỳ thị trấn nào đến bất kỳ thị trấn nào khác qua các con đường.

Hiện tại, vương quốc được chia thành \(K\) thành phố, đánh số từ \(1\) đến \(K\). Thị trấn thứ \(j\) (\(1 \le j \le N\)) thuộc thành phố \(C_j\). Mỗi thành phố có ít nhất một thị trấn.

Ngài K là vua của vương quốc JOI. Ngài muốn chọn một thành phố làm thủ đô. Vì lý do an ninh, thủ đô phải thỏa mãn điều kiện: có thể đi từ bất kỳ thị trấn nào thuộc thủ đô đến bất kỳ thị trấn nào khác thuộc thủ đô mà chỉ đi qua các thị trấn thuộc thủ đô.

Tuy nhiên, có thể không thành phố nào thỏa mãn điều kiện đó. Để giải quyết vấn đề, ngài K sẽ sáp nhập các thành phố bằng thao tác sau:

Chọn \(x,y\) thỏa mãn \(1 \le x,y \le K\) và \(x\ne y\), rồi chuyển tất cả thị trấn đang thuộc thành phố \(y\) sang thành phố \(x\).

Vì sáp nhập rất tốn kém, ngài K muốn thực hiện ít lần sáp nhập nhất để có thể chọn một thành phố làm thủ đô. Cho cấu trúc các thị trấn, các con đường và thành phố mà mỗi thị trấn đang thuộc về, hãy tính số lần sáp nhập nhỏ nhất.

Dữ liệu vào

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

N K
A_1 B_1
...
A_{N-1} B_{N-1}
C_1
...
C_N

Dữ liệu ra

In ra một dòng chứa số lần sáp nhập thành phố ít nhất cần thực hiện để có thể chọn thủ đô.

Ràng buộc

  • \(1 \le N \le 200\,000\).
  • \(1 \le K \le N\).
  • \(1 \le A_i,B_i \le N\) với \(1 \le i \le N-1\).
  • Có thể đi từ bất kỳ thị trấn nào đến bất kỳ thị trấn nào khác qua các con đường.
  • \(1 \le C_j \le K\) với \(1 \le j \le N\).
  • Với mỗi \(1 \le k \le K\), tồn tại ít nhất một \(j\) (\(1 \le j \le N\)) sao cho \(C_j=k\).

Phân nhóm

Các ràng buộc chung áp dụng cho mọi nhóm.

  1. \(1\) điểm: \(N \le 20\)
  2. \(10\) điểm: \(N \le 2000\)
  3. \(30\) điểm: Mỗi thị trấn được nối trực tiếp bằng đường với nhiều nhất hai thị trấn khác
  4. \(59\) điểm: Không có

Ví dụ

Ví dụ 1

Input 
6 3
2 1
3 5
6 2
3 4
2 3
1
3
1
2
3
2
Output 
1
Giải thích

Có thể sáp nhập thành phố \(3\) vào thành phố \(1\) bằng cách chọn \((x,y)=(1,3)\). Sau đó, chọn thành phố \(1\) làm thủ đô. Ban đầu không có thành phố nào đủ điều kiện làm thủ đô, nên số lần sáp nhập nhỏ nhất là \(1\).

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

Ví dụ 2

Input 
8 4
4 1
1 3
3 6
6 7
7 2
2 5
5 8
2
4
3
1
1
2
3
4
Output 
1
Giải thích

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

Ví dụ 3

Input 
12 4
7 9
1 3
4 6
2 4
10 12
1 2
2 10
11 1
2 8
5 3
6 7
3
1
1
2
4
3
3
2
2
3
4
4
Output 
2
Giải thích

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

Nguồn

JOI 2019/2020, Trại huấn luyện mùa xuân, ngày thi 4. Đề gốc của Ủy ban Olympic Tin học Nhật Bản, được cung cấp theo giấy phép CC BY-SA 4.0. Bản tiếng Việt được dịch từ đề tiếng Anh chính thức.

2. JOI 2020 - Legendary Dango Maker

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

Đây là bài chỉ nộp dữ liệu đầu ra.

Bạn là thợ làm bánh gạo dango chuyên nghiệp. Hiện tại, bạn đang xiên các viên dango vào que.

Các viên dango nằm trong một bảng hình chữ nhật có \(R\) hàng và \(C\) cột, mỗi ô chứa một viên. Màu của một viên là hồng (P), trắng (W) hoặc xanh lá (G). Bạn chọn ba viên liên tiếp theo chiều dọc, chiều ngang hoặc một trong hai đường chéo: từ trên trái xuống dưới phải, hoặc từ trên phải xuống dưới trái. Sau đó, lấy lần lượt ba viên từ đầu này đến đầu kia và xiên chúng vào que theo đúng thứ tự đó.

Ví dụ, nếu chọn ba viên liên tiếp theo chiều dọc, có thể lấy theo thứ tự trên-giữa-dưới hoặc dưới-giữa-trên; không được lấy theo thứ tự giữa-dưới-trên hoặc dưới-trên-giữa. Mỗi viên dango không được nằm trên nhiều hơn một que.

Một que dango được gọi là đẹp nếu thứ tự màu trên que là hồng-trắng-xanh lá hoặc xanh lá-trắng-hồng. Bạn muốn làm được nhiều que đẹp nhất có thể.

Bạn có thể làm được bao nhiêu que dango đẹp?

Dữ liệu vào

Bài có sáu bộ dữ liệu đầu vào. Mỗi bộ có định dạng:

R C
D_1
...
D_R

Với \(1 \le i \le R\), \(D_i\) là xâu dài \(C\) chỉ gồm các ký tự P, W, G. Ký tự thứ \(j\) của \(D_i\) (\(1 \le j \le C\)) là màu viên dango ở hàng thứ \(i\) từ trên xuống, cột thứ \(j\) từ trái sang.

Dữ liệu ra

Với mỗi bộ dữ liệu đầu vào, nộp dữ liệu đầu ra theo định dạng:

S_1
...
S_R

Mỗi \(S_i\) (\(1 \le i \le R\)) là xâu dài \(C\) chỉ gồm các ký tự P, W, G, |, -, \, /. Ký tự thứ \(j\) mô tả cách xiên viên dango tại hàng \(i\), cột \(j\):

  • |: tạo một que đẹp từ viên tại ô này, ô kề ngay phía trên và ô kề ngay phía dưới.
  • -: tạo một que đẹp từ viên tại ô này, ô kề ngay bên trái và ô kề ngay bên phải.
  • \: tạo một que đẹp từ viên tại ô này, ô chéo trên trái và ô chéo dưới phải.
  • /: tạo một que đẹp từ viên tại ô này, ô chéo trên phải và ô chéo dưới trái.
  • Trong các trường hợp còn lại, ghi P, W hoặc G đúng theo màu ban đầu của viên tại ô đó, tức là giữ nguyên ký tự tương ứng của \(D_i\).

Các ký hiệu que được đặt ở ô giữa của ba viên. Các ô ở hai đầu que vẫn giữ ký tự màu ban đầu.

Ràng buộc

  • \(3 \le R \le 500\).
  • \(3 \le C \le 500\).
  • Mỗi \(D_i\) (\(1 \le i \le R\)) có độ dài \(C\) và chỉ gồm P, W, G.

Phân nhóm

Mỗi bộ dữ liệu có bốn tham số: \(S\) là điểm tối đa của bộ đó, cùng ba ngưỡng \(X,Y,Z\).

Bộ dữ liệu \(S\) \(X\) \(Y\) \(Z\)
01 15 44000 47000 47220
02 15 39000 41700 41980
03 15 45000 51000 51390
04 15 18000 19000 19120
05 20 43000 48200 48620
06 20 44000 46000 46500

Với mỗi bộ dữ liệu, gọi \(N\) là số que dango đẹp tạo được theo đầu ra của bạn. Điểm của bộ dữ liệu đó bằng:

\[ \begin{cases} 0, & N<X,\\ \dfrac{N-X}{2(Y-X)}S, & X \le N<Y,\\ \left(\dfrac12+\dfrac{N-Y}{2(Z-Y)}\right)S, & Y \le N<Z,\\ S, & Z \le N. \end{cases} \]

Điểm của bài là tổng điểm của sáu bộ dữ liệu, sau đó làm tròn tổng đến số nguyên gần nhất.

Tuy nhiên, điểm của một bộ dữ liệu bằng \(0\) nếu đầu ra không hợp lệ: không thể tạo các que đẹp theo các ký hiệu |, -, \, / trong đầu ra (bao gồm việc dùng một viên trên nhiều que), các ký tự P, W, G không khớp với dữ liệu vào, hoặc định dạng đầu ra sai.

Ví dụ

Ví dụ 1

Input 
3 4
PWGP
WGPW
GWPG
Output 
P-GP
WGP|
G-PG
Giải thích

Trong ví dụ này, bạn tạo được ba que dango đẹp. Lưu ý rằng thứ tự màu W G P không tạo thành một que đẹp.

Ví dụ 2

Input 
3 4
PWWP
WWWW
PGGP
Output 
PWWP
W\/W
PGGP
Giải thích

Trong ví dụ này, bạn tạo được hai que dango đẹp.

Công cụ trực quan

Công cụ trực quan cho phép xem tổng quan dữ liệu đầu vào hoặc đầu ra dưới dạng hình ảnh. Mở tệp HTML bằng trình duyệt rồi chọn hoặc kéo thả tệp dữ liệu vào.

Công cụ không kiểm tra đầy đủ tính đúng đắn của định dạng tệp. Nó có thể hoạt động không đúng nếu định dạng dữ liệu sai hoặc \(R,C\) vượt quá các ràng buộc.

Nguồn

JOI 2019/2020, Trại huấn luyện mùa xuân, ngày thi 4. Đề gốc của Ủy ban Olympic Tin học Nhật Bản, được cung cấp theo giấy phép CC BY-SA 4.0. Bản tiếng Việt được dịch từ đề tiếng Anh chính thức.

3. JOI 2020 - Treatment Project

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

Vương quốc JOI có \(N\) ngôi nhà, đánh số từ \(1\) đến \(N\), nằm trên một đường thẳng theo thứ tự số hiệu. Mỗi nhà có một người dân; người sống trong nhà \(x\) (\(1 \le x \le N\)) được gọi là người dân \(x\).

Gần đây, một loại vi-rút mới xuất hiện và tất cả người dân đều bị nhiễm. Có \(M\) dự án điều trị được đề xuất. Dự án thứ \(i\) (\(1 \le i \le M\)) có chi phí \(C_i\). Nếu thực hiện dự án này thì vào buổi tối ngày thứ \(T_i\), mọi người dân \(x\) thỏa mãn \(L_i \le x \le R_i\) đang nhiễm vi-rút sẽ được chữa khỏi.

Vi-rút lây giữa các người dân ở nhà kề nhau như sau: nếu người dân \(x\) (\(1 \le x \le N\)) bị nhiễm vào buổi sáng của một ngày, thì đến buổi trưa cùng ngày, người dân \(x-1\) (nếu \(x \ge 2\)) và người dân \(x+1\) (nếu \(x \le N-1\)) sẽ bị nhiễm. Người đã được chữa khỏi vẫn có thể bị nhiễm lại.

Bạn là một bộ trưởng của vương quốc và phải chọn một số dự án sao cho sau khi tất cả dự án đã chọn được thực hiện, không còn người dân nào nhiễm vi-rút. Có thể thực hiện nhiều dự án trong cùng một ngày.

Cho số ngôi nhà và thông tin các dự án, hãy xác định có thể đạt được điều kiện trên hay không; nếu có, hãy tính tổng chi phí nhỏ nhất.

Dữ liệu vào

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

N M
T_1 L_1 R_1 C_1
...
T_M L_M R_M C_M

Dữ liệu ra

In ra một dòng. Nếu không thể thỏa mãn điều kiện, in ra \(-1\); ngược lại, in ra tổng chi phí nhỏ nhất.

Ràng buộc

  • \(1 \le N \le 1\,000\,000\,000\).
  • \(1 \le M \le 100\,000\).
  • \(1 \le T_i \le 1\,000\,000\,000\) với \(1 \le i \le M\).
  • \(1 \le L_i \le R_i \le N\) với \(1 \le i \le M\).
  • \(1 \le C_i \le 1\,000\,000\,000\) với \(1 \le i \le M\).

Phân nhóm

Các ràng buộc chung áp dụng cho mọi nhóm.

  1. \(4\) điểm: \(T_i=1\) với mọi \(1 \le i \le M\)
  2. \(5\) điểm: \(M \le 16\)
  3. \(30\) điểm: \(M \le 5000\)
  4. \(61\) điểm: Không có

Ví dụ

Ví dụ 1

Input 
10 5
2 5 10 3
1 1 6 5
5 2 8 3
7 6 10 4
4 1 3 1
Output 
7
Giải thích

Có thể thực hiện các dự án như sau:

  • Tối ngày \(2\), thực hiện dự án \(1\), chữa khỏi cho các người dân \(5,6,7,8,9,10\). Các người dân \(1,2,3,4\) vẫn bị nhiễm.
  • Trưa ngày \(3\), người dân \(5\) bị nhiễm. Lúc này các người dân \(1,2,3,4,5\) bị nhiễm.
  • Trưa ngày \(4\), người dân \(6\) bị nhiễm. Lúc này các người dân \(1,2,3,4,5,6\) bị nhiễm.
  • Tối ngày \(4\), thực hiện dự án \(5\), chữa khỏi cho các người dân \(1,2,3\). Các người dân \(4,5,6\) vẫn bị nhiễm.
  • Trưa ngày \(5\), các người dân \(3\) và \(7\) bị nhiễm. Lúc này các người dân \(3,4,5,6,7\) bị nhiễm.
  • Tối ngày \(5\), thực hiện dự án \(3\), chữa khỏi cho các người dân \(3,4,5,6,7\). Sau đó không còn ai bị nhiễm.

Tổng chi phí của các dự án \(1\), \(3\) và \(5\) là \(7\). Không có cách thỏa mãn điều kiện với tổng chi phí nhỏ hơn \(7\), nên in ra \(7\).

Ví dụ 2

Input 
10 5
2 6 10 3
1 1 5 5
5 2 7 3
8 6 10 4
4 1 3 1
Output 
-1
Giải thích

Không thể thỏa mãn điều kiện nên in ra \(-1\).

Ví dụ 3

Input 
10 5
1 5 10 4
1 1 6 5
1 4 8 3
1 6 10 3
1 1 3 1
Output 
7
Giải thích

Ví dụ này thỏa mãn ràng buộc của nhóm \(1\).

Nguồn

JOI 2019/2020, Trại huấn luyện mùa xuân, ngày thi 4. Đề gốc của Ủy ban Olympic Tin học Nhật Bản, được cung cấp theo giấy phép CC BY-SA 4.0. Bản tiếng Việt được dịch từ đề tiếng Anh chính thức.