| # | Bài tập | Điểm | Thời gian: | Giới hạn bộ nhớ |
|---|---|---|---|---|
| 1 | USACO 2019 - Mixing Milk | 100 (p) | 4.0s | 512M |
| 2 | USACO 2019 - The Bucket List | 100 (p) | 4.0s | 512M |
| 3 | USACO 2019 - Back and Forth | 100 (p) | 4.0s | 512M |
Nông nghiệp là một ngành kinh doanh đầy cạnh tranh — đặc biệt là sản xuất sữa. Nông dân John nhận thấy rằng nếu không đổi mới phương pháp sản xuất sữa, cơ nghiệp bò sữa của ông có thể bị đối thủ đánh bại!
May mắn thay, Nông dân John có một ý tưởng hay. Ba cô bò sữa ưu tú của ông là Bessie, Elsie và Mildred, mỗi cô cho sữa có hương vị hơi khác nhau, và ông dự định trộn chúng lại để có được sự hòa quyện hoàn hảo của các hương vị.
Để trộn ba loại sữa khác nhau, ông lấy ba chiếc xô chứa sữa của ba cô bò. Các xô có thể có dung tích khác nhau và có thể không đầy hoàn toàn. Sau đó, ông rót xô 1 vào xô 2, rồi xô 2 vào xô 3, rồi xô 3 vào xô 1, rồi lại xô 1 vào xô 2, và cứ tiếp tục theo chu kỳ như vậy, tổng cộng 100 lần rót (do đó lần rót thứ 100 sẽ là từ xô 1 vào xô 2). Khi Nông dân John rót từ xô \(a\) vào xô \(b\), ông rót nhiều sữa nhất có thể cho đến khi xô \(a\) cạn hoặc xô \(b\) đầy.
Hãy cho Nông dân John biết lượng sữa trong mỗi xô sau khi ông hoàn thành cả 100 lần rót.
Dòng đầu tiên chứa hai số nguyên cách nhau bởi dấu cách: dung tích \(c_1\) của xô thứ nhất và lượng sữa \(m_1\) ban đầu trong xô thứ nhất. Cả \(c_1\) và \(m_1\) đều dương và không vượt quá 1 tỷ, với \(c_1 \geq m_1\). Dòng thứ hai và thứ ba có dạng tương tự, chứa dung tích và lượng sữa của xô thứ hai và thứ ba.
In ra ba dòng, lần lượt là lượng sữa cuối cùng trong mỗi xô sau 100 lần rót.
Ví dụ 1
10 3
11 4
12 50
10
2Trong ví dụ này, lượng sữa trong mỗi xô thay đổi như sau trong quá trình rót:
Trạng thái ban đầu: 3 4 5
1. Rót 1->2: 0 7 5
2. Rót 2->3: 0 0 12
3. Rót 3->1: 10 0 2
4. Rót 1->2: 0 10 2
5. Rót 2->3: 0 0 12
(Ba trạng thái cuối sau đó lặp lại theo chu kỳ ...)
Đề bài gốc: USACO 2018 December Contest, Bronze — Mixing Milk
Tác giả: Brian Dean
Nông dân John đang cân nhắc thay đổi cách phân bổ xô để vắt sữa bò. Ông cho rằng cuối cùng việc này sẽ giúp mình chỉ cần dùng một số lượng nhỏ xô, nhưng ông không biết chính xác là bao nhiêu. Hãy giúp ông!
Nông dân John có \(N\) cô bò (\(1 \leq N \leq 100\)), được đánh số thuận tiện từ \(1 \ldots N\). Cô bò thứ \(i\) cần được vắt sữa từ thời điểm \(s_i\) đến thời điểm \(t_i\) và cần sử dụng \(b_i\) chiếc xô trong quá trình vắt sữa. Có thể nhiều cô bò được vắt sữa cùng một lúc; nếu vậy, chúng không thể dùng chung xô. Nói cách khác, một chiếc xô được cấp cho việc vắt sữa cô bò \(i\) không thể được dùng cho bất kỳ cô bò nào khác trong khoảng thời gian từ \(s_i\) đến \(t_i\). Tất nhiên, ngoài khoảng thời gian này, chiếc xô có thể được dùng cho những cô bò khác. Để đơn giản hóa công việc, FJ đã đảm bảo rằng tại bất kỳ thời điểm nào, nhiều nhất chỉ có một cô bò bắt đầu hoặc kết thúc việc vắt sữa (tức là tất cả các giá trị \(s_i\) và \(t_i\) đều phân biệt).
FJ có một kho chứa các xô được đánh số liên tiếp bằng các nhãn 1, 2, 3, v.v. Theo chiến lược vắt sữa hiện tại, mỗi khi một cô bò nào đó (giả sử là cô bò \(i\)) bắt đầu được vắt sữa (tại thời điểm \(s_i\)), FJ chạy đến kho, lấy \(b_i\) chiếc xô đang khả dụng có nhãn nhỏ nhất và cấp chúng để vắt sữa cô bò \(i\).
Hãy xác định tổng số xô FJ cần giữ trong kho để có thể vắt sữa thành công cho tất cả các cô bò.
Dòng đầu tiên chứa \(N\). Mỗi dòng trong \(N\) dòng tiếp theo mô tả một cô bò, gồm các số \(s_i\), \(t_i\) và \(b_i\) cách nhau bởi dấu cách. Cả \(s_i\) và \(t_i\) đều là số nguyên trong khoảng \(1 \ldots 1000\), còn \(b_i\) là số nguyên trong khoảng \(1 \ldots 10\).
In ra một số nguyên duy nhất cho biết tổng số xô FJ cần.
Ví dụ 1
3
4 10 1
8 13 3
2 6 24Trong ví dụ này, FJ cần 4 chiếc xô: ông dùng xô 1 và 2 để vắt sữa cô bò 3 (bắt đầu tại thời điểm 2). Ông dùng xô 3 để vắt sữa cô bò 1 (bắt đầu tại thời điểm 4). Khi cô bò 2 đến vào thời điểm 8, xô 1 và 2 đã khả dụng trở lại nhưng xô 3 thì chưa, nên ông dùng các xô 1, 2 và 4.
Đề bài gốc: USACO 2018 December Contest, Bronze — The Bucket List
Tác giả: Brian Dean
Nông dân John có hai chuồng vắt sữa, mỗi chuồng đều có một bể sữa lớn và một kho chứa \(10\) chiếc xô với nhiều dung tích khác nhau. Ông thích mang sữa qua lại giữa hai chuồng để tập thể dục.
Vào thứ Hai, Nông dân John đo được chính xác \(1000\) gallon sữa trong bể của chuồng thứ nhất và chính xác \(1000\) gallon sữa trong bể của chuồng thứ hai.
Vào thứ Ba, ông lấy một chiếc xô từ chuồng thứ nhất, đổ đầy xô rồi mang sữa đến chuồng thứ hai, nơi ông rót sữa vào bể chứa. Ông để lại chiếc xô tại chuồng thứ hai.
Vào thứ Tư, ông lấy một chiếc xô từ chuồng thứ hai (có thể chính là chiếc xô ông để lại vào thứ Ba), đổ đầy xô rồi mang sữa đến chuồng thứ nhất, nơi ông rót sữa vào bể chứa. Ông để lại chiếc xô tại chuồng thứ nhất.
Vào thứ Năm, ông lấy một chiếc xô từ chuồng thứ nhất (có thể chính là chiếc xô ông để lại vào thứ Tư), đổ đầy xô rồi mang sữa đến chuồng thứ hai, nơi ông rót sữa vào bể. Ông để lại chiếc xô tại chuồng thứ hai.
Vào thứ Sáu, ông lấy một chiếc xô từ chuồng thứ hai (có thể là một trong những chiếc xô ông để lại vào thứ Ba hoặc thứ Năm), đổ đầy xô rồi mang sữa đến chuồng thứ nhất, nơi ông rót sữa vào bể. Ông để lại chiếc xô tại chuồng thứ nhất.
Sau đó, Nông dân John đo lượng sữa trong bể của chuồng thứ nhất. Ông có thể nhận được bao nhiêu kết quả đo khác nhau?
Dòng đầu tiên chứa \(10\) số nguyên, cho biết dung tích của các xô ban đầu ở chuồng thứ nhất. Dòng thứ hai chứa thêm \(10\) số nguyên, cho biết dung tích của các xô ban đầu ở chuồng thứ hai. Mọi dung tích xô đều nằm trong khoảng \(1 \dots 100\).
In ra số kết quả đo có thể có khi Nông dân John đo lượng sữa trong bể của chuồng thứ nhất sau ngày thứ Sáu.
Ví dụ 1
1 1 1 1 1 1 1 1 1 2
5 5 5 5 5 5 5 5 5 55Trong ví dụ này, lượng sữa cuối cùng trong bể của chuồng thứ nhất có thể nhận \(5\) giá trị:
Đề bài gốc: USACO 2018 December Contest, Bronze — Back and Forth
Tác giả: Brian Dean