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

Bộ đề bài

Trở lại kỳ thi
# Bài tập Điểm Thời gian: Giới hạn bộ nhớ
1 USACO 2024 February Contest, Gold, Bessla Motors 100 (p) 1.0s 256M
2 USACO 2024 February Contest, Gold, Milk Exchange 100 (p) 1.0s 256M
3 USACO 2024 February Contest, Gold, Quantum Moochanics 100 (p) 1.0s 256M

1. USACO 2024 February Contest, Gold, Bessla Motors

Điểm: 100 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Nông dân John muốn quảng bá dòng máy kéo điện Bessla của mình bằng cách giới thiệu mạng lưới các trạm sạc của Bessla. Anh ấy đã xác định được \(N (2 \le N \le 5*10^4)\) điểm quan tâm được đánh số từ \(1\) đến \(N\), trong đó \(C(1 \le C \le N)\) trạm đầu tiên là các trạm sạc và còn lại là các điểm du lịch. Các điểm này được kết nối với nhau bởi \(M(1\le M \le 10^5)\) đường hai chiều, đường thứ \(i\) nối hai điểm phân biệt \(u_i\) và \(v_i\) và có độ dài \(l_i\) dặm \((1\le l_i \le 10^9)\).

Bessla có thể di chuyển với quãng đường lên tới \(2R\) dặm \((1 \le R \le 10^9)\) trong một lần sạc, cho phép nó đến bất kỳ điểm đến nào trong phạm vi \(R\) dặm tính từ trạm sạc. Một điểm đến được coi là kết nối tốt nếu có thể đến được điểm đến đó từ ít nhất \(K(1\le K\le 10)\) trạm sạc riêng biệt. Nhiệm vụ của bạn là hỗ trợ John xác định các điểm đến du lịch có kết nối tốt.

Input

Dòng đầu tiên chứa năm số nguyên \(N,M,C,R,K\). Mỗi dòng trong \(M\) dòng tiếp chứa ba số nguyên cách nhau bằng dấu cách \(u_i,v_i,l_i\) sao cho \(u_i \ne v_i\). Các trạm sạc được đánh số \(1,2,...,C\). Các điểm còn lại đều là các điểm du lịch.

Output

Đầu tiên, in ra số lượng điểm đến du lịch có kết nối tốt trên một dòng. Sau đó, liệt kê tất cả các điểm đến du lịch có kết nối tốt theo thứ tự tăng dần, mỗi điểm trên một dòng riêng biệt.

Scoring

  • Subtask \(1\): \(K=2\), \(N \le 500\) và \(M \le 1000\).
  • Subtast \(2\): \(K=2\).
  • Subtask \(3\): Không có điều kiện gì thêm.

Example

Test 1

Input 
3 3 1 4 1
1 2 3
1 3 5
2 3 2
Output 
1
2
Note

Chúng ta có một trạm sạc ở \(1\). Từ trạm sạc này, chúng ta có thể đến điểm \(2\) (vì nó cách \(1\) khoảng cách là \(3\)), nhưng không thể đến điểm \(3\) (vì nó cách \(1\) khoảng cách là \(5\)). Như vậy chỉ có điểm \(2\) là kết nối tốt.

Test 2

Input 
4 3 2 101 2
1 2 1
2 3 100
1 4 10
Output 
2
3
4
Note

Chúng ta có các trạm sạc tại \(1\) và \(2\), và cả hai điểm \(3\) và \(4\) đều cách hai điểm \(1\) và \(2\) khoảng cách là \(101\). Vì vậy, cả hai điểm \(3\) và \(4\) đều có kết nối tốt.

Test 3

Input 
4 3 2 100 2
1 2 1
2 3 100
1 4 10
Output 
1
4

2. USACO 2024 February Contest, Gold, Milk Exchange

Điểm: 100 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

\(N (1 \le N \le 10^5)\) con bò của nông dân John được xếp thành vòng tròn. Con bò thứ \(i\) có một cái xô có dung tích là số nguyên \(a_i(1 \le a_i \le 10^9)\) lít. Tất cả các thùng ban đầu đều đầy.
Mỗi phút, con bò \(i\) sẽ chuyển tất cả sữa trong thùng của nó cho con bò \(i+1\) với \(1 \le i < N\) , và con bò \(N\) chuyển sữa cho con bò \(1\). Tất cả các quá trình trao đổi diễn ra đồng thời (tức là nếu một con bò có thùng sữa đầy nhưng cho đi \(x\) lít sữa và cũng nhận được \(x\) lít thì sữa của nó được bảo toàn). Nếu tổng lượng sữa của con bò vượt quá \(a_i\), thì lượng sữa dư thừa sẽ bị mất.
Sau mỗi \(1,2,...,N\) phút, tổng số sữa bò còn lại là bao nhiêu?

Input

Dòng đầu chứa số \(N\).
Dòng tiếp theo chứa \(N\) số nguyên \(a_1,a_2,...,a_N\).

Output

In ra \(N\) dòng, trong đó dòng thứ \(i\) là tổng số sữa còn lại của tất cả các con bò sau \(i\) phút.

Scoring

  • Subtask \(1\): \(N \le 2000\)
  • Subtask \(2\): \(a_i \le 2\)
  • Subtask \(3\): Mọi \(a_i\) đều được tạo ra ngẫu nhiên với xác suất như nhau trong khoảng \([1,10^9]\)
  • Subtast 4: Không có điều kiện gì thêm.

Example

Test 1

Input 
6
2 2 2 1 2 1
Output 
8
7
6
6
6
6
Note

Ban đầu, lượng sữa trong mỗi thùng là \([2,2,2,1,2,1]\).
Sau \(1\) phút, lượng sữa trong mỗi thùng là \([1,2,2,1,1,1]\) nên tổng lượng sữa là \(8\).
Sau \(2\) phút, lượng sữa trong mỗi thùng là \([1,2,2,1,1,1]\) nên tổng lượng sữa là \(7\).
Sau \(3\) phút, lượng sữa trong mỗi thùng là \([1,2,2,1,1,1]\) nên tổng lượng sữa là \(6\).
Sau \(4\) phút, lượng sữa trong mỗi thùng là \([1,2,2,1,1,1]\) nên tổng lượng sữa là \(6\).
Sau \(5\) phút, lượng sữa trong mỗi thùng là \([1,2,2,1,1,1]\) nên tổng lượng sữa là \(6\).
Sau \(6\) phút, lượng sữa trong mỗi thùng là \([1,2,2,1,1,1]\) nên tổng lượng sữa là \(6\).

Test 2

Input 
8
3 8 6 4 8 3 8 1
Output 
25
20
17
14
12
10
8
8
Note

Sau \(1\) phút, lượng sữa trong mỗi xô là \([1,3,6,4,4,3,3,1]\) nên tổng lượng sữa là \(25\).

Test 3

Input 
10
9 9 10 10 6 8 2 1000000000 1000000000 1000000000
Output 
2000000053
1000000054
56
49
42
35
28
24
20
20

3. USACO 2024 February Contest, Gold, Quantum Moochanics

Điểm: 100 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Khi rảnh rỗi, Bessie thích nghiên cứu vật lý thực nghiệm. Gần đây cô đã phát hiện ra một cặp hạt hạ nguyên tử mới, được đặt tên là mootrinos và antimootrinos. Giống như các cặp vật chất-phản vật chất tiêu chuẩn, mootrinos và antimootrino tiêu hủy lẫn nhau và biến mất khi chúng gặp nhau. Nhưng điều làm cho những hạt này trở nên độc đáo là chúng thay đổi hướng chuyển động (trong khi vẫn giữ nguyên tốc độ) bất cứ khi nào Bessie nhìn vào chúng.
Đối với thí nghiệm mới nhất của mình, Bessie đã xếp một lượng chẵn \(N(2 \le N \le 10^5)\) các hạt này vào một dòng. Dòng bắt đầu bằng mootrino ở bên trái và sau đó xen kẽ giữa hai loại hạt, với hạt thứ i nằm ở vị trí \(p_i(0 \le p_1 < ... < p_n \le 10^18)\). Mootrinos di chuyển sang phải trong khi antimootrinos di chuyển sang trái, và hạt thứ \(i\) chuyển động với tốc độ không đổi là \(s_i\) đơn vị mỗi giây \((1 \le s_i \le 10^9)\).
Bessie quan sát vào các thời điểm sau:

  • Đầu tiên, \(1\) giây sau khi bắt đầu thí nghiệm.
  • Sau đó \(2\) giây sau lần quan sát đầu tiên.
  • Sau đó \(3\) giây sau lần quan sát thứ hai.
  • ...
  • Sau đó \(n+1\) giây sau lần quan sát thứ \(n\).
    Trong mỗi lần quan sát, Bessie ghi lại những hạt nào đã biến mất.
    Thí nghiệm này có thể mất rất nhiều thời gian để hoàn thành, vì vậy Bessie trước tiên muốn mô phỏng kết quả của nó. Với cách thiết lập thí nghiệm, hãy giúp Bessie xác định khi nào (tức là số lần) cô ấy sẽ quan sát thấy từng hạt biến mất! Nó có thể được chứng minh rằng tất cả các hạt cuối cùng sẽ biến mất.

Input

  • Mỗi bộ test chứa \(T (1\le T \le 10)\) test độc lập.
  • Mỗi trường hợp thử nghiệm bao gồm ba dòng. Dòng đầu tiên chứa \(N\), dòng thứ hai chứa \(p_1,p_2,...,p_N\), và dòng thứ ba chứa \(s_1,s_2,...,s_N\).
  • Tổng N không vượt quá \(2*10^5\)

Output

Đối với mỗi test, in ra số lần quan sát cho sự biến mất của từng hạt, cách nhau bằng dấu cách.

Scoring

  • Subtask \(1\): \(N=2\)
  • Subtask \(2\): \(N \le 2000\) và \(p_i \le 10^4\)
  • Subtask \(3\): \(N \le 2000\)
  • Subtask \(4\): Không có điều kiện gì thêm.

Example

Test 1

Input 
4
2
1 11
1 1
2
1 12
1 1
2
1 11
4 6
2
1 11
4 5
Output 
9 9
11 11
1 1
3 3
Note

Đối với test đầu tiên, Bessie quan sát trong \(8\) lần:
- Mootrino (di chuyển sang phải) xuất hiện ở các vị trí: \(2 → 0 → 3 → −1 → 4 → −2 → 5 → −3\).
- Antimootrino (di chuyển sang trái) xuất hiện ở các vị trí: \(10 → 12 → 9 → 13 → 8 → 14 → 7 → 15\).

Khi đó tại lần quan sát thứ \(9\), hai hạt gặp nhau ở vị trí \(6\) và biến mất.

Đối với thử nghiệm thứ hai, antimootrino di chuyển thên \(1\) đơn vị về bên phải, do đó hai hạt gặp nhau ở vị trí \(6.5\), nửa giây trước lần quan sát thứ \(11\).

Lưu ý rằng chúng ta chỉ quan tâm đến số lần quan sát chứ không quan tâm đến thời gian hay vị trí.

Test 2

Input 
2
4
1 3 5 8
1 1 1 1
4
1 4 5 8
1 1 1 1
Output 
1 1 3 3
7 2 2 7
Note

Đối với test đầu tiên:

  • Hai hạt ngoài cùng bên trái gặp nhau ở vị trí \(2\) ngay lần quan sát \(1\).
  • Hai hạt ngoài cùng bên phải gặp nhau ở vị trí \(6.5\), nửa giây trước lần quan sát \(3\).