USACO 2015 - Tháng 12 - Hạng Bạc

Farmer John gần đây đã xây một chuồng khổng lồ gồm một lưới \(N\times N\) phòng (\(2\le N\le100\)), được đánh số từ \((1,1)\) đến \((N,N)\). Vì hơi sợ bóng tối, cô bò Bessie muốn bật đèn trong càng nhiều phòng càng tốt.

Bessie bắt đầu ở phòng \((1,1)\), căn phòng duy nhất có đèn sáng ban đầu. Trong một số phòng, cô sẽ tìm thấy các công tắc đèn có thể dùng để chuyển trạng thái đèn ở những phòng khác; chẳng hạn, trong phòng \((1,1)\) có thể có một công tắc chuyển trạng thái đèn ở phòng \((1,2)\). Bessie chỉ có thể đi qua các phòng có đèn sáng, và từ phòng \((x,y)\) cô chỉ có thể di chuyển đến bốn phòng kề \((x-1,y)\), \((x+1,y)\), \((x,y-1)\) và \((x,y+1)\) (hoặc có thể ít phòng kề hơn nếu phòng này nằm trên biên lưới).

Hãy xác định số phòng tối đa Bessie có thể thắp sáng.

Dữ liệu vào

Dòng đầu tiên chứa các số nguyên \(N\) và \(M\) (\(1\le M\le20\,000\)).

\(M\) dòng tiếp theo, mỗi dòng mô tả một công tắc đèn bằng bốn số nguyên \(x,y,a,b\), cho biết một công tắc trong phòng \((x,y)\) có thể được dùng để chuyển trạng thái đèn trong phòng \((a,b)\). Mỗi phòng có thể chứa nhiều công tắc và đèn của một phòng có thể được điều khiển bởi nhiều công tắc.

Dữ liệu ra

In một dòng chứa số phòng tối đa Bessie có thể thắp sáng.

Ví dụ

3 6
1 1 1 2
2 1 2 2
1 1 1 3
2 3 3 1
1 3 1 2
1 3 2 1

5

Nguồn

USACO 2015 December Contest, Silver - Switching on the Lights: https://usaco.org/index.php?page=viewproblem2&cpid=570

Tác giả: Austin Bannister và Brian Dean.

Cô bò Bessie là một người rất hâm mộ các trò chơi bài, điều này khá đáng ngạc nhiên vì cô không có ngón cái đối diện. Đáng tiếc là không có con bò nào khác trong đàn là đối thủ giỏi. Thực tế, chúng chơi tệ đến mức luôn chơi theo một cách hoàn toàn có thể dự đoán! Dù vậy, việc tìm ra cách chiến thắng vẫn có thể là một thử thách đối với Bessie.

Bessie và cô bạn Elsie hiện đang chơi một trò bài đơn giản. Họ lấy một bộ gồm \(2N\) lá bài, được đánh số thuận tiện từ \(1\ldots2N\), rồi chia cho Bessie \(N\) lá và Elsie \(N\) lá. Sau đó, hai cô chơi \(N\) vòng; trong mỗi vòng, Bessie và Elsie đều đánh một lá bài, và người có lá bài lớn hơn giành được một điểm.

Biết rằng Bessie có thể dự đoán thứ tự Elsie sẽ đánh các lá bài, hãy xác định số điểm tối đa Bessie có thể giành được.

Dữ liệu vào

Dòng đầu tiên chứa giá trị \(N\) (\(1\le N\le50\,000\)).

\(N\) dòng tiếp theo chứa các lá bài mà Elsie sẽ đánh trong từng vòng liên tiếp của trò chơi. Lưu ý rằng từ thông tin này có thể dễ dàng xác định các lá bài của Bessie.

Dữ liệu ra

In một dòng chứa số điểm tối đa Bessie có thể ghi được.

Ví dụ

3
1
6
4

2

Nguồn

USACO 2015 December Contest, Silver - High Card Wins: https://usaco.org/index.php?page=viewproblem2&cpid=571

Tác giả: Austin Bannister và Brian Dean.

\(N\) con bò của Farmer John, được đánh số thuận tiện từ \(1\ldots N\), đang đứng thành một hàng (dường như chúng làm vậy thường xuyên đến mức giờ đây Farmer John chỉ cần nhắc rất ít là chúng đã xếp hàng). Mỗi con bò có một mã giống: 1 đối với Holstein, 2 đối với Guernsey và 3 đối với Jersey. Farmer John muốn bạn giúp đếm số bò thuộc mỗi giống nằm trong một số đoạn nhất định của hàng.

Dữ liệu vào

Dòng đầu tiên chứa \(N\) và \(Q\) (\(1\le N\le100\,000\), \(1\le Q\le100\,000\)).

\(N\) dòng tiếp theo, mỗi dòng chứa một số nguyên bằng 1, 2 hoặc 3, cho biết mã giống của một con bò trong hàng.

\(Q\) dòng tiếp theo, mỗi dòng mô tả một truy vấn dưới dạng hai số nguyên \(a,b\) (\(a\le b\)).

Dữ liệu ra

Với mỗi truy vấn \((a,b)\) trong số \(Q\) truy vấn, in một dòng chứa ba số: số bò được đánh số từ \(a\ldots b\) thuộc giống Holstein (giống 1), Guernsey (giống 2) và Jersey (giống 3).

Ví dụ

6 3
2
1
1
3
2
1
1 6
3 3
2 4

3 2 1
1 0 0
2 0 1

Nguồn

USACO 2015 December Contest, Silver - Breed Counting: https://usaco.org/index.php?page=viewproblem2&cpid=572

Tác giả: Nick Wu.