USACO 2023 - Tháng 12 - Hạng Đồng

Những chú bò của Farmer John rất hảo ngọt, và chúng đặc biệt thích ăn kẹo gậy! FJ có tổng cộng \(N\) con bò, mỗi con có một chiều cao ban đầu nhất định, và ông muốn cho chúng ăn \(M\) cây kẹo gậy, mỗi cây cũng có chiều cao khác nhau (\(1\le N,M\le 2\cdot 10^5\)).

FJ dự định lần lượt cho các con bò ăn từng cây kẹo gậy theo thứ tự được cho trong dữ liệu vào. Để cho chúng ăn một cây kẹo gậy, ông sẽ treo cây kẹo sao cho ban đầu nó vừa chạm mặt đất. Sau đó, các con bò lần lượt xếp hàng theo thứ tự trong dữ liệu vào và tiến đến cây kẹo; mỗi con ăn phần kẹo lên đến chiều cao của mình (vì nó không thể với cao hơn). Cây kẹo vẫn được treo cố định tại vị trí ban đầu và không được hạ xuống mặt đất, kể cả sau khi phần dưới của cây kẹo đã bị ăn. Có thể một con bò không ăn được gì trong lượt của mình nếu đáy phần kẹo còn lại đã cao hơn chiều cao của nó. Sau khi tất cả các con bò đã đến lượt, mỗi con cao thêm đúng bằng số đơn vị kẹo mà nó đã ăn. Farmer John treo cây kẹo tiếp theo và các con bò lặp lại quá trình (bò số 1 lại là con đầu tiên ăn cây kẹo mới).

Dữ liệu vào

Dòng đầu tiên chứa \(N\) và \(M\).

Dòng tiếp theo chứa chiều cao ban đầu của \(N\) con bò, mỗi chiều cao thuộc đoạn \([1,10^9]\).

Dòng tiếp theo chứa chiều cao của \(M\) cây kẹo gậy, mỗi chiều cao thuộc đoạn \([1,10^9]\).

Dữ liệu ra

In chiều cao cuối cùng của mỗi con bò trên một dòng riêng.

Lưu ý rằng các số nguyên lớn trong bài này có thể đòi hỏi kiểu dữ liệu số nguyên 64 bit (ví dụ long long trong C/C++).

Ví dụ

3 2
3 2 5
6 1

7
2
7

Phân nhóm

• Dữ liệu 2–10: \(N,M\le 10^3\).
• Dữ liệu 11–14: Không có ràng buộc bổ sung.

Nguồn

USACO 2023 December Contest, Bronze — Candy Cane Feast: https://usaco.org/index.php?page=viewproblem2&cpid=1347

Tác giả bài toán: Agastya Goel

Farmer John có \(N\) con bò đứng thành một hàng (\(1\leq N\leq 3\cdot 10^5\)). Không may, một căn bệnh đang lây lan trong đàn.

Ban đầu, một số con bò bị nhiễm bệnh. Mỗi đêm, một con bò nhiễm bệnh lây bệnh sang con bò bên trái và bên phải nó (nếu có). Một khi đã nhiễm bệnh, con bò sẽ luôn nhiễm bệnh.

Sau một số đêm, Farmer John nhận ra tình hình đã mất kiểm soát nên ông xét nghiệm đàn bò để xác định những con mắc bệnh. Hãy tìm số lượng nhỏ nhất các con bò có thể đã mắc bệnh từ đầu.

Dữ liệu vào

Dòng đầu tiên chứa \(N\), số bò của Farmer John.

Dòng tiếp theo chứa một xâu bit dài \(N\) chỉ gồm các ký tự \(1\) và \(0\), trong đó \(1\) biểu thị một con bò nhiễm bệnh và \(0\) biểu thị một con bò không nhiễm bệnh sau một số đêm.

Dữ liệu ra

In một số nguyên duy nhất: số lượng nhỏ nhất các con bò có thể đã mắc bệnh từ đầu.

Ví dụ

5
11111

1

0 đêm:       00100 (bò thứ ba bị nhiễm bệnh từ đầu)
1 đêm:    -> 01110 (bò thứ hai và thứ tư vừa bị nhiễm bệnh)
2 đêm:    -> 11111 (bò thứ nhất và thứ năm vừa bị nhiễm bệnh)
3 đêm:    -> 11111 (tất cả bò đã nhiễm bệnh, nên không có thêm bò nào bị nhiễm)
          -> ...

0 đêm:       10001
1 đêm:    -> 11011
2 đêm:    -> 11111

0 đêm:       01001
1 đêm:    -> 11111

0 đêm:       01000
1 đêm:    -> 11100
2 đêm:    -> 11110
3 đêm:    -> 11111

6
011101

4

Phân nhóm

• Dữ liệu 3–7: \(N\le 1000\).
• Dữ liệu 8–12: Không có ràng buộc bổ sung.

Nguồn

USACO 2023 December Contest, Bronze — Cowntact Tracing 2: https://usaco.org/index.php?page=viewproblem2&cpid=1348

Tác giả bài toán: Suhas Nagar

Farmer John đang trồng \(N\) cây măng tây (\(1\leq N\leq 2\cdot 10^5\)) trong trang trại! Tuy nhiên, một số cây có khác biệt di truyền nên sẽ sinh trưởng nhanh hơn những cây khác. Chiều cao ban đầu của cây thứ \(i\) là \(h_i\) inch, và sau mỗi ngày, cây thứ \(i\) cao thêm \(a_i\) inch.

FJ thích một số cây hơn những cây khác và muốn một số cây cụ thể cao hơn các cây còn lại. Ông đưa cho bạn một mảng gồm các giá trị đôi một khác nhau \(t_1,\dots,t_N\), chứa tất cả các số nguyên từ \(0\) đến \(N-1\), và muốn cây thứ \(i\) có đúng \(t_i\) cây khác cao hơn nó. Hãy tìm số ngày nhỏ nhất để yêu cầu của FJ được thỏa mãn, hoặc xác định rằng điều đó là không thể.

Dữ liệu vào

Dòng đầu tiên chứa số nguyên \(T\), biểu thị số bộ test độc lập (\(1\leq T\leq 10\)).

Dòng đầu tiên của mỗi bộ test chứa số nguyên \(N\).

Dòng thứ hai chứa \(N\) số nguyên \(h_i\) (\(1\leq h_i\leq 10^9\)), biểu thị chiều cao ban đầu tính bằng inch của cây thứ \(i\).

Dòng thứ ba chứa \(N\) số nguyên \(a_i\) (\(1\leq a_i\leq 10^9\)), biểu thị số inch mà cây thứ \(i\) cao thêm mỗi ngày.

Dòng thứ tư chứa \(N\) số nguyên đôi một khác nhau \(t_i\), biểu thị mảng mà FJ đưa cho bạn.

Tổng \(N\) trên tất cả các bộ test không vượt quá \(2\cdot 10^5\).

Dữ liệu ra

In \(T\) dòng, mỗi dòng là đáp án cho một bộ test. Nếu không thể, in \(-1\).

Lưu ý rằng các số nguyên lớn trong bài này có thể đòi hỏi kiểu dữ liệu số nguyên 64 bit (ví dụ long long trong C/C++).

Ví dụ

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

0
3
2
5
-1
-1

2
5
7 4 1 10 12
3 4 5 2 1
2 1 0 3 4
5
4 10 12 7 1
3 1 1 4 5
2 4 3 1 0

4
7

Phân nhóm

• Dữ liệu 3: \(N\le 2\).
• Dữ liệu 4–5: \(N\le 50\) và \(a_i,h_i\le 10^3\).
• Dữ liệu 6–8: \(N\le 10^3\).
• Dữ liệu 9–13: Không có ràng buộc bổ sung.

Nguồn

USACO 2023 December Contest, Bronze — Farmer John Actually Farms: https://usaco.org/index.php?page=viewproblem2&cpid=1349

Tác giả bài toán: Chongtian Ma