USACO 2018 - Tháng 2 - Hạng Vàng

Mùa đông đã đến ở trang trại, và điều đó có nghĩa là tuyết! Có \(N\) ô lát trên con đường từ nhà đến chuồng bò, được đánh số thuận tiện từ \(1 \dots N\), và ô \(i\) bị phủ bởi lớp tuyết sâu \(f_i\) feet.

Trong tầng hầm của ngôi nhà, bác nông dân John có \(B\) đôi ủng, được đánh số từ \(1 \dots B\). Một số đôi chịu được điều kiện khắc nghiệt hơn những đôi khác, còn một số đôi linh hoạt hơn những đôi khác. Cụ thể, đôi \(i\) cho phép bác nông dân John bước vào lớp tuyết sâu tối đa \(s_i\) feet và tiến về phía trước tối đa \(d_i\) ô trong mỗi bước.

Bác nông dân John bắt đầu tại ô \(1\) và phải đến ô \(N\) để đánh thức đàn bò. Ô \(1\) được mái nhà che chắn còn ô \(N\) được mái chuồng che chắn, nên cả hai ô này đều không có tuyết. Hãy giúp bác nông dân John xác định những đôi ủng tuyết nào cho phép ông thực hiện hành trình này.

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên \(N\) và \(B\) cách nhau bởi dấu cách (\(1 \leq N,B \leq 10^5\)).

Dòng thứ hai chứa \(N\) số nguyên cách nhau bởi dấu cách; số nguyên thứ \(i\) là \(f_i\), độ sâu của tuyết trên ô \(i\) (\(0 \leq f_i \leq 10^9\)). Bảo đảm rằng \(f_1 = f_N = 0\).

\(B\) dòng tiếp theo, mỗi dòng chứa hai số nguyên cách nhau bởi dấu cách. Số nguyên đầu tiên trên dòng \(i+2\) là \(s_i\), độ sâu tuyết lớn nhất mà đôi ủng \(i\) có thể bước vào. Số nguyên thứ hai trên dòng \(i+2\) là \(d_i\), độ dài bước chân lớn nhất của đôi ủng \(i\). Bảo đảm rằng \(0 \leq s_i \leq 10^9\) và \(1 \leq d_i \leq N-1\).

Dữ liệu ra

Kết quả gồm \(B\) dòng. Dòng \(i\) chứa một số nguyên duy nhất: \(1\) nếu bác nông dân John có thể đi từ ô \(1\) đến ô \(N\) khi mang đôi ủng thứ \(i\), và \(0\) nếu không thể.

Ví dụ

8 7
0 3 8 5 6 9 0 0
0 5
0 6
6 2
8 1
10 1
5 3
150 7

0
1
1
0
1
1
1

Nguồn

USACO 2018 February Contest, Gold — Snow Boots

Tác giả bài toán: Dhruv Rohatgi.

Cô bò Bessie am hiểu máy tính một cách đáng ngạc nhiên. Trên chiếc máy tính trong chuồng, cô lưu tất cả các tệp quý giá của mình trong một hệ thống thư mục; chẳng hạn:

bessie/
  folder1/
    file1
    folder2/
      file2
  folder3/
    file3
  file4

Chỉ có một thư mục “cấp cao nhất”, tên là bessie.

Bessie có thể di chuyển để ở bên trong bất kỳ thư mục nào cô muốn. Từ một thư mục cho trước, có thể tham chiếu đến bất kỳ tệp nào bằng một “đường dẫn tương đối”. Trong một đường dẫn tương đối, ký hiệu .. chỉ thư mục cha. Nếu Bessie đang ở trong folder2, cô có thể tham chiếu đến bốn tệp như sau:

../file1
file2
../../folder3/file3
../../file4

Bessie muốn chọn một thư mục sao cho tổng độ dài các đường dẫn tương đối từ thư mục đó đến tất cả các tệp là nhỏ nhất.

Dữ liệu vào

Dòng đầu tiên chứa một số nguyên \(N\) (\(2 \leq N \leq 100{,}000\)), là tổng số tệp và thư mục. Trong dữ liệu vào, mỗi đối tượng (tệp hoặc thư mục) được gán một ID nguyên duy nhất từ \(1\) đến \(N\), trong đó ID \(1\) chỉ thư mục cấp cao nhất.

Tiếp theo là \(N\) dòng. Mỗi dòng bắt đầu bằng tên của một tệp hoặc thư mục. Tên chỉ gồm các chữ cái thường a-z và các chữ số 0-9, đồng thời dài không quá \(16\) ký tự. Sau tên là một số nguyên \(m\). Nếu \(m\) bằng \(0\) thì đối tượng này là một tệp. Nếu \(m > 0\) thì đối tượng này là một thư mục và chứa tổng cộng \(m\) tệp hoặc thư mục bên trong nó. Sau \(m\) là \(m\) số nguyên cho biết ID của các đối tượng nằm trong thư mục này.

Dữ liệu ra

In ra tổng độ dài nhỏ nhất có thể của các đường dẫn tương đối đến các tệp. Lưu ý rằng giá trị này có thể quá lớn để lưu trong một số nguyên \(32\) bit.

Ví dụ

8
bessie 3 2 6 8
folder1 2 3 4
file1 0
folder2 1 5
file2 0
folder3 1 7
file3 0
file4 0

42

file1
folder2/file2
../folder3/file3
../file4

Nguồn

USACO 2018 February Contest, Gold — Directory Traversal

Tác giả bài toán: Mark Gordon.

Vào sáng sớm, bác nông dân John thức giấc vì tiếng gỗ vỡ vụn. Lại là đàn bò, và chúng lại đang phá chuồng trốn ra ngoài!

Bác nông dân John đã quá chán ngán những vụ phá chuồng vào buổi sáng của đàn bò và quyết định rằng như thế là đủ: đã đến lúc phải mạnh tay. Ông đóng lên tường chuồng một bộ đếm theo dõi số ngày kể từ vụ phá chuồng gần nhất. Vì vậy, nếu một vụ phá chuồng xảy ra vào buổi sáng thì bộ đếm trong ngày đó sẽ là \(0\); nếu vụ phá chuồng gần nhất xảy ra \(3\) ngày trước thì bộ đếm sẽ hiển thị \(3\). Bác nông dân John ghi lại giá trị của bộ đếm mỗi ngày một cách cẩn thận.

Cuối năm đã đến và bác nông dân John sẵn sàng tính sổ. Lũ bò sẽ phải trả giá, ông nói! Nhưng có điều gì đó trong nhật ký của ông trông không ổn...

Bác nông dân John muốn tìm xem đã có bao nhiêu vụ phá chuồng xảy ra kể từ khi ông bắt đầu ghi nhật ký. Tuy nhiên, ông nghi ngờ đàn bò đã sửa nhật ký, và điều duy nhất ông biết chắc là ông bắt đầu ghi nhật ký đúng vào ngày xảy ra một vụ phá chuồng. Với mỗi số vụ phá chuồng có thể đã xảy ra kể từ khi ông bắt đầu ghi nhật ký, hãy giúp ông xác định số mục nhật ký ít nhất buộc phải bị sửa.

Dữ liệu vào

Dòng đầu tiên chứa một số nguyên \(N\) (\(1 \leq N \leq 100\)), biểu thị số ngày kể từ khi bác nông dân John bắt đầu ghi lại bộ đếm các vụ phá chuồng của đàn bò.

Dòng thứ hai chứa \(N\) số nguyên cách nhau bởi dấu cách. Số nguyên thứ \(i\) là một số nguyên không âm \(a_i\) (không quá \(100\)), cho biết bộ đếm ở ngày \(i\) có giá trị \(a_i\), trừ khi đàn bò đã sửa mục nhật ký của ngày đó.

Dữ liệu ra

Kết quả gồm \(N\) số nguyên, mỗi số trên một dòng. Số nguyên thứ \(i\) là số mục nhật ký không phù hợp nhỏ nhất trong tất cả các chuỗi phá chuồng có đúng \(i\) vụ phá chuồng.

Ví dụ

6
1 1 2 0 0 1

4
2
1
2
3
4

Nguồn

USACO 2018 February Contest, Gold — Taming the Herd

Tác giả bài toán: Brian Dean và Dhruv Rohatgi.