| # | Bài tập | Điểm | Thời gian: | Giới hạn bộ nhớ |
|---|---|---|---|---|
| 1 | USACO 2012 - Above the Median | 100 (p) | 4.0s | 512M |
| 2 | USACO 2012 - Binary Sudoku | 100 (p) | 4.0s | 512M |
| 3 | USACO 2012 - Cow Steeplechase | 100 (p) | 4.0s | 512M |
Farmer John đã xếp \(N\) con bò (\(1 \leq N \leq 100\,000\)) thành một hàng để đo chiều cao; con bò thứ \(i\) có chiều cao \(H_i\) nanomét (\(1 \leq H_i \leq 1\,000\,000\,000\)) — FJ rất coi trọng độ chính xác! Ông muốn chụp ảnh một dãy con liên tiếp nào đó của đàn bò để gửi dự thi nhiếp ảnh bò tại hội chợ hạt.
Hội chợ có một quy định rất kỳ lạ đối với mọi bức ảnh dự thi: một bức ảnh chỉ hợp lệ nếu nó chụp một nhóm bò có trung vị chiều cao ít nhất bằng một ngưỡng \(X\) nào đó (\(1 \leq X \leq 1\,000\,000\,000\)).
Trong bài này, ta định nghĩa trung vị của một mảng \(A[0 \ldots K]\) là \(A[\lceil K/2 \rceil]\) sau khi \(A\) được sắp xếp, trong đó \(\lceil K/2 \rceil\) là \(K/2\) được làm tròn lên tới số nguyên gần nhất (hoặc vẫn là chính \(K/2\) nếu ban đầu \(K/2\) đã là số nguyên). Chẳng hạn, trung vị của \(\{7, 3, 2, 6\}\) là 6, còn trung vị của \(\{5, 4, 8\}\) là 5.
Hãy giúp FJ đếm số dãy con liên tiếp khác nhau của đàn bò mà ông có thể gửi dự thi nhiếp ảnh.
Dòng đầu tiên chứa hai số nguyên \(N\) và \(X\), cách nhau bởi dấu cách.
Dòng thứ \(i+1\) chứa một số nguyên \(H_i\) duy nhất, với \(1 \leq i \leq N\).
In số dãy con của đàn bò FJ có trung vị ít nhất bằng \(X\). Lưu ý rằng giá trị này có thể không vừa trong một số nguyên 32 bit.
Ví dụ 1
4 6
10
5
6
27Bốn con bò của FJ có chiều cao lần lượt là \(10, 5, 6, 2\). Ta muốn biết có bao nhiêu dãy con liên tiếp có trung vị ít nhất bằng 6.
Có 10 dãy con liên tiếp có thể xét. Trong đó, chỉ có 7 dãy có trung vị ít nhất bằng 6: \(\{10\}\), \(\{6\}\), \(\{10, 5\}\), \(\{5, 6\}\), \(\{6, 2\}\), \(\{10, 5, 6\}\) và \(\{10, 5, 6, 2\}\).
USACO 2011 November Contest, Gold Division — Above the Median. Tác giả đề: Brian Dean.
Đàn bò của Farmer John thích chơi một biến thể thú vị của trò chơi "Sudoku" nổi tiếng. Phiên bản của chúng cũng dùng một lưới \(9 \times 9\) gồm các lưới con \(3 \times 3\), giống như Sudoku thông thường. Tuy nhiên, phiên bản của đàn bò chỉ sử dụng các chữ số nhị phân:
000 000 000
001 000 100
000 000 000
000 110 000
000 111 000
000 000 000
000 000 000
000 000 000
000 000 000
Mục tiêu của Sudoku nhị phân là lật ít bit nhất có thể sao cho mỗi hàng trong chín hàng, mỗi cột trong chín cột và mỗi lưới con trong chín lưới con \(3 \times 3\) đều có tính chẵn (tức chứa một số chẵn chữ số 1). Với ví dụ trên, một tập gồm 3 phép lật sẽ cho một lời giải hợp lệ:
000 000 000
001 000 100
001 000 100
000 110 000
000 110 000
000 000 000
000 000 000
000 000 000
000 000 000
Cho trạng thái ban đầu của một bảng Sudoku nhị phân, hãy giúp đàn bò xác định số phép lật ít nhất cần thiết để giải bảng đó.
Mỗi dòng trong 9 dòng chứa một xâu nhị phân gồm 9 chữ số, tương ứng với một hàng của bảng trò chơi ban đầu.
In số phép lật ít nhất cần thực hiện để mọi hàng, mọi cột và mọi lưới con đều có tính chẵn.
Ví dụ 1
000000000
001000100
000000000
000110000
000111000
000000000
000000000
000000000
0000000003Bảng Sudoku trong dữ liệu vào mẫu giống với bảng trong phần mô tả bài toán ở trên. Ba phép lật là đủ để giải bảng.
USACO 2011 November Contest, Gold Division — Binary Sudoku. Tác giả đề: Brian Dean.
Farmer John có một ý tưởng xuất sắc cho môn thể thao thu hút khán giả vĩ đại tiếp theo: Cow Steeplechase! Như mọi người đều biết, môn vượt chướng ngại vật thông thường có một nhóm ngựa đua quanh đường chạy đầy các chướng ngại vật mà chúng phải nhảy qua. FJ cho rằng cuộc thi tương tự cũng sẽ phù hợp với những con bò được huấn luyện kỹ càng, miễn là các chướng ngại vật được làm đủ thấp.
Để thiết kế đường đua, FJ vẽ sơ đồ của tất cả \(N\) chướng ngại vật khả dĩ mà ông có thể xây dựng (\(1 \leq N \leq 250\)). Mỗi chướng ngại vật được biểu diễn bởi một đoạn thẳng trên mặt phẳng hai chiều, song song với trục ngang hoặc trục dọc. Chướng ngại vật thứ \(i\) có hai đầu mút phân biệt \((X1_i, Y1_i)\) và \((X2_i, Y2_i)\) (\(1 \leq X1_i, Y1_i, X2_i, Y2_i \leq 1\,000\,000\,000\)). Một ví dụ như sau:
--+-------
-----+-----
---+--- |
| | |
--+-----+--+- |
| | | | |
| --+--+--+-+-
| | | |
|
FJ muốn xây dựng nhiều chướng ngại vật nhất có thể, với điều kiện không có hai chướng ngại vật nào giao nhau. Bắt đầu từ sơ đồ trên, FJ có thể xây 7 chướng ngại vật:
----------
-----------
------- |
| |
| | |
| | | |
| | | |
| | | |
|
Hai đoạn thẳng được coi là giao nhau nếu chúng có chung bất kỳ điểm nào, kể cả một đầu mút của một hoặc cả hai đoạn. FJ chắc chắn rằng không có hai đoạn ngang nào trong sơ đồ đầu vào ban đầu giao nhau; tương tự, không có hai đoạn dọc nào trong sơ đồ đầu vào giao nhau.
Hãy giúp FJ xác định số chướng ngại vật lớn nhất ông có thể xây dựng.
Dòng đầu tiên chứa một số nguyên \(N\).
Dòng thứ \(i+1\) chứa bốn số nguyên cách nhau bởi dấu cách biểu diễn chướng ngại vật thứ \(i\): \(X1_i\), \(Y1_i\), \(X2_i\) và \(Y2_i\), với \(1 \leq i \leq N\).
In số đoạn thẳng không giao nhau lớn nhất mà FJ có thể chọn.
Ví dụ 1
3
4 5 10 5
6 2 6 12
8 3 8 52Có ba chướng ngại vật khả dĩ. Chướng ngại vật thứ nhất là đoạn ngang nối \((4, 5)\) với \((10, 5)\); chướng ngại vật thứ hai và thứ ba là các đoạn dọc lần lượt nối \((6, 2)\) với \((6, 12)\) và \((8, 3)\) với \((8, 5)\).
Lời giải tối ưu là chọn cả hai đoạn dọc.
USACO 2011 November Contest, Gold Division — Cow Steeplechase. Tác giả đề: Brian Dean.