| # | Bài tập | Điểm | Thời gian: | Giới hạn bộ nhớ |
|---|---|---|---|---|
| 1 | USACO 2017 - Modern Art | 100 (p) | 4.0s | 512M |
| 2 | USACO 2017 - Switch Grass | 100 (p) | 4.0s | 512M |
| 3 | USACO 2017 - COWBASIC | 100 (p) | 4.0s | 512M |
Giới phê bình nghệ thuật trên toàn thế giới chỉ mới bắt đầu công nhận thiên tài sáng tạo của Picowso, nữ họa sĩ bò vĩ đại.
Picowso vẽ tranh theo một cách rất đặc biệt. Cô bắt đầu với một bức vẽ trống kích thước \(N \times N\), được biểu diễn bởi một lưới \(N \times N\) chứa toàn số \(0\), trong đó số \(0\) biểu thị một ô còn trống trên bức vẽ. Sau đó, cô vẽ \(N^2\) hình chữ nhật lên bức vẽ, mỗi hình bằng một trong \(N^2\) màu (được đánh số tiện lợi từ \(1 \ldots N^2\)). Chẳng hạn, cô có thể bắt đầu bằng cách tô một hình chữ nhật màu \(2\), tạo ra bức vẽ trung gian sau:
2 2 2 0
2 2 2 0
2 2 2 0
0 0 0 0
Tiếp theo, cô có thể tô một hình chữ nhật màu \(7\):
2 2 2 0
2 7 7 7
2 7 7 7
0 0 0 0
Rồi cô có thể tô một hình chữ nhật nhỏ màu \(3\):
2 2 3 0
2 7 3 7
2 7 7 7
0 0 0 0
Các cạnh của mỗi hình chữ nhật song song với các cạnh của bức vẽ; một hình chữ nhật có thể lớn bằng toàn bộ bức vẽ hoặc nhỏ chỉ bằng một ô. Mỗi màu từ \(1 \ldots N^2\) được dùng đúng một lần, mặc dù các màu được tô sau có thể che phủ hoàn toàn một số màu được tô trước.
Cho trạng thái cuối cùng của bức vẽ, hãy đếm xem có bao nhiêu trong số \(N^2\) màu có thể đã được tô đầu tiên.
Dòng đầu tiên chứa \(N\), kích thước của bức vẽ (\(1 \leq N \leq 1\,000\)). \(N\) dòng tiếp theo mô tả bức tranh cuối cùng, mỗi dòng chứa \(N\) số nguyên trong khoảng \(0 \ldots N^2\). Dữ liệu vào được đảm bảo là đã được vẽ theo cách mô tả ở trên, bằng cách lần lượt tô các hình chữ nhật với những màu khác nhau.
In số màu có thể đã được tô đầu tiên.
Ví dụ 1
4
2 2 3 0
2 7 3 7
2 7 7 7
0 0 0 014Trong ví dụ này, màu \(2\) có thể đã được tô đầu tiên. Rõ ràng màu \(3\) phải được tô sau màu \(7\), và màu \(7\) phải được tô sau màu \(2\). Vì không nhìn thấy các màu còn lại, ta suy ra chúng cũng có thể đã được tô đầu tiên.
USACO 2017 US Open Contest, Platinum — Modern Art. Tác giả đề: Brian Dean.
Gần đây, Farmer John đang thử nghiệm trồng các loại cỏ khác nhau trên trang trại vì nhận ra rằng những loại bò khác nhau thích những loại cỏ khác nhau. Tuy nhiên, ông phải cẩn thận để đảm bảo các loại cỏ khác nhau được trồng đủ xa nhau, tránh cho chúng bị trộn lẫn đến mức không thể tách rời.
Trang trại của FJ gồm \(N\) cánh đồng (\(1 \leq N \leq 200\,000\)), trong đó \(M\) cặp cánh đồng được nối với nhau bằng các đường đi hai chiều (\(1 \leq M \leq 200\,000\)). Có thể đi từ một cánh đồng bất kỳ đến mọi cánh đồng khác bằng các đường đi này. Mỗi đường đi có độ dài nguyên trong khoảng \(1 \ldots 1\,000\,000\). Mỗi cặp cánh đồng được nối trực tiếp bởi nhiều nhất một đường đi.
Ban đầu, FJ trồng một trong \(K\) loại cỏ trên mỗi cánh đồng (\(1 \leq K \leq N\)). Tuy nhiên, theo thời gian, ông có thể quyết định đổi loại cỏ trên một cánh đồng nào đó sang loại khác. Ông gọi đây là một thao tác "cập nhật". Ông có thể thực hiện nhiều lần cập nhật theo thời gian, và tất cả các cập nhật đều có hiệu lực tích lũy.
Sau mỗi lần cập nhật, FJ muốn biết độ dài đường đi ngắn nhất giữa hai cánh đồng trồng hai loại cỏ khác nhau. Nói cách khác, trong tất cả các cặp cánh đồng có loại cỏ khác nhau, ông muốn biết hai cánh đồng gần nhau nhất. Lý tưởng nhất là giá trị này lớn, nhờ đó ông có thể ngăn cỏ thuộc loại này trộn lẫn với cỏ thuộc loại khác. Dữ liệu được đảm bảo rằng trang trại luôn có ít nhất hai cánh đồng trồng hai loại cỏ khác nhau.
Dòng đầu tiên chứa bốn số nguyên \(N\), \(M\), \(K\) và \(Q\), trong đó \(Q\) là số lần cập nhật (\(1 \leq Q \leq 200\,000\)).
\(M\) dòng tiếp theo mô tả các đường đi; mỗi dòng chứa ba số nguyên \(A\), \(B\) và \(L\), cho biết có một đường đi độ dài \(L\) từ cánh đồng \(A\) đến cánh đồng \(B\) (cả \(A\) và \(B\) đều nằm trong khoảng \(1 \ldots N\)).
Dòng tiếp theo chứa loại cỏ ban đầu được trồng trên mỗi cánh đồng (\(N\) số nguyên trong khoảng \(1 \ldots K\)).
Cuối cùng, \(Q\) dòng cuối, mỗi dòng mô tả một lần cập nhật bằng hai số nguyên \(A\) và \(B\), nghĩa là cỏ trên cánh đồng \(A\) được đổi thành loại \(B\).
Với mỗi lần cập nhật, sau khi áp dụng cập nhật đó, hãy in độ dài đường đi ngắn nhất giữa hai cánh đồng trồng hai loại cỏ khác nhau.
Ví dụ 1
3 2 3 4
1 2 3
2 3 1
1 1 2
3 3
2 3
1 2
2 21
3
3
1USACO 2017 US Open Contest, Platinum — Switch Grass. Tác giả đề: Lewin Gan.
Bessie đã phát minh ra một ngôn ngữ lập trình mới, nhưng vì chưa có trình biên dịch nên cô cần bạn giúp thực sự chạy các chương trình của mình.
COWBASIC là một ngôn ngữ đơn giản và tao nhã. Nó có hai tính năng chính: phép cộng và vòng lặp MOO. Bessie đã nghĩ ra một giải pháp thông minh cho vấn đề tràn số: mọi phép cộng đều được thực hiện theo modulo \(10^9+7\). Nhưng thành tựu thực sự của Bessie là vòng lặp MOO, dùng để chạy một khối mã với số lần cố định. Dĩ nhiên, các vòng lặp MOO và phép cộng có thể được lồng nhau.
Cho một chương trình COWBASIC, hãy giúp Bessie xác định số mà chương trình trả về.
Bạn được cho một chương trình COWBASIC dài không quá \(100\) dòng, mỗi dòng dài không quá \(350\) ký tự. Một chương trình COWBASIC là một danh sách các câu lệnh.
Có ba loại câu lệnh:
<variable> = <expression>
<literal> MOO {
<list of statements>
}
RETURN <variable>
Có ba loại biểu thức:
<literal>
<variable>
( <expression> ) + ( <expression> )
Một <literal> là một số nguyên dương không lớn hơn \(100\,000\).
Một <variable> là một chuỗi gồm không quá \(10\) chữ cái tiếng Anh viết thường.
Dữ liệu được đảm bảo rằng không biến nào được sử dụng hoặc RETURN trước khi được định nghĩa. RETURN được đảm bảo xuất hiện đúng một lần ở dòng cuối cùng của chương trình.
In một số nguyên dương duy nhất là giá trị của biến được RETURN.
Ví dụ 1
x = 1
10 MOO {
x = ( x ) + ( x )
}
RETURN x1024Chương trình COWBASIC này tính \(2^{10}\).
Ví dụ 2
n = 1
nsq = 1
100000 MOO {
100000 MOO {
nsq = ( nsq ) + ( ( n ) + ( ( n ) + ( 1 ) ) )
n = ( n ) + ( 1 )
}
}
RETURN nsq4761Chương trình COWBASIC này tính \((10^5*10^5+1)^2\) (theo modulo \(10^9+7\)).
USACO 2017 US Open Contest, Platinum — COWBASIC. Tác giả đề: Jonathan Paulson.