USACO 2020 - Tháng 1 - 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 2020 - Time is Mooney 100 (p) 4.0s 512M
2 USACO Jan/20 Gold - 3SUM 100 (p) 1.0s 512M
3 USACO 2020 - Springboards 100 (p) 4.0s 512M

1. USACO 2020 - Time is Mooney

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

Bessie đang đi công tác tại Bovinia, nơi có \(N\) thành phố (\(2\le N\le 1000\)) được đánh số \(1\ldots N\) và nối với nhau bằng \(M\) con đường một chiều (\(1\le M\le 2000\)). Mỗi lần ghé thăm thành phố \(i\), Bessie kiếm được \(m_i\) mooney (\(0\le m_i\le 1000\)). Khởi hành từ thành phố \(1\), Bessie muốn ghé thăm các thành phố để kiếm được nhiều mooney nhất có thể rồi kết thúc hành trình tại thành phố \(1\). Để tránh nhầm lẫn, \(m_1=0\).

Di chuyển giữa hai thành phố qua một con đường mất một ngày. Việc chuẩn bị cho chuyến đi rất tốn kém; một hành trình dài \(T\) ngày tiêu tốn \(C\cdot T^2\) mooney (\(1\le C\le 1000\)).

Số mooney lớn nhất Bessie có thể kiếm được trong một chuyến đi là bao nhiêu? Lưu ý rằng phương án tối ưu có thể là Bessie không ghé thăm thành phố nào ngoài thành phố \(1\); trong trường hợp đó, đáp án là \(0\).

Dữ liệu vào

Dữ liệu vào được đọc từ tệp time.in.

Dòng đầu tiên chứa ba số nguyên \(N\), \(M\) và \(C\).

Dòng thứ hai chứa \(N\) số nguyên \(m_1,m_2,\ldots,m_N\).

Mỗi dòng trong \(M\) dòng tiếp theo chứa hai số nguyên \(a\) và \(b\) (\(a\neq b\)), cách nhau bởi dấu cách, biểu thị một con đường một chiều từ thành phố \(a\) đến thành phố \(b\).

Dữ liệu ra

Ghi ra tệp time.out một dòng chứa đáp án.

Phân nhóm

Tất cả các test tuân theo các ràng buộc đã nêu.

Ví dụ

Ví dụ 1

Input 
3 3 1
0 10 20
1 2
2 3
3 1
Output 
24
Giải thích

Hành trình tối ưu là \(1\to 2\to 3\to 1\to 2\to 3\to 1\). Tổng số mooney Bessie kiếm được là \(10+20+10+20-1\cdot 6^2=24\).

Nguồn

2. USACO Jan/20 Gold - 3SUM

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

Cho mảng \(S = [s_1, s_2, \dots, s_N]\) có \(N\) phần tử.

Cho \(Q\) truy vấn có dạng \((a_i, b_i)\), trên mảng con \(S[a_i \dots b_i]\), bạn hãy đếm số bộ ba \(i < j < k\) sao cho \(s_i + s_j + s_k = 0\).

Dữ liệu đầu vào

  • Dòng đầu tiên lần lượt chứa hai số \(N\) và \(Q\). \((N \leq 5000, Q \leq 10^5)\)
  • Dòng thứ hai chứa \(N\) số nguyên \(s_1, s_2, \dots, s_n\) \((\forall i: -10^6 \leq s_i \leq 10^6)\).
  • \(Q\) dòng cuối cùng, dòng thứ \(i\) chứa hai số \(a_i, b_i\) \((1 \leq a_i \leq b_i \leq N)\)

Định dạng đầu ra

  • In ra \(Q\) dòng, dòng thứ \(i\) chứa một số nguyên 64-bit là đáp án cho truy vấn thứ \(i\).

Điểm số

  • Test 1 là test ví dụ
  • Test 2-4 thỏa mãn \(N \leq 500\)
  • Test 5-7 thỏa mãn \(N \leq 2000\)
  • Test 8-15 không có điều kiện nào khác.

Ví dụ

Ví dụ 1

Đầu vào 
7 3
2 0 -1 1 -2 3 3
1 5
2 4
1 7
Đầu ra 
2
1
4
Giải thích

Với truy vấn đầu tiên, có \((A_1, A_2, A_5)\) và \((A_2, A_3, A_4)\)

3. USACO 2020 - Springboards

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

Bessie đang ở trong một lưới hai chiều, nơi cô chỉ được phép đi theo các hướng song song với một trong hai trục tọa độ. Cô bắt đầu tại điểm \((0,0)\) và muốn đến \((N,N)\) (\(1\le N\le 10^9\)). Để giúp cô, trên lưới có \(P\) ván bật (\(1\le P\le 10^5\)). Mỗi ván bật nằm tại một điểm cố định \((x_1,y_1)\) và nếu sử dụng nó, Bessie sẽ đáp xuống điểm \((x_2,y_2)\).

Bessie là một cô bò luôn hướng tới phía trước, vì vậy cô chỉ cho phép mình đi lên hoặc sang phải, không bao giờ sang trái hay đi xuống. Tương tự, mỗi ván bật đều được thiết lập để không bao giờ đưa cô sang trái hay đi xuống. Khoảng cách nhỏ nhất Bessie cần đi bộ là bao nhiêu?

Phân nhóm

  • Các test từ \(2\) đến \(5\) thỏa mãn \(P\le 1000\).
  • Các test từ \(6\) đến \(15\) không có ràng buộc bổ sung.

Dữ liệu vào

Dữ liệu vào được đọc từ tệp boards.in.

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

Mỗi dòng trong \(P\) dòng tiếp theo chứa bốn số nguyên \(x_1\), \(y_1\), \(x_2\), \(y_2\), trong đó \(x_1\le x_2\) và \(y_1\le y_2\).

Tất cả vị trí ván bật và vị trí đích đều phân biệt.

Dữ liệu ra

Ghi ra tệp boards.out một số nguyên là khoảng cách nhỏ nhất Bessie cần đi bộ để đến \((N,N)\).

Ví dụ

Ví dụ 1

Input 
3 2
0 1 0 2
1 2 2 3
Output 
3
Giải thích

Đường đi tốt nhất của Bessie là:

  • Bessie đi bộ từ \((0,0)\) đến \((0,1)\) (\(1\) đơn vị).
  • Bessie bật đến \((0,2)\).
  • Bessie đi bộ từ \((0,2)\) đến \((1,2)\) (\(1\) đơn vị).
  • Bessie bật đến \((2,3)\).
  • Bessie đi bộ từ \((2,3)\) đến \((3,3)\) (\(1\) đơn vị).

Tổng chiều dài đi bộ trên đường đi của Bessie là \(3\) đơn vị.

Nguồn