USACO 2024 - Tháng 2 - Hạng Bạch Kim

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, Platinum, Lazy Cow 100 (p) 1.0s 256M
2 USACO 2024 February Contest, Platinum, Minimum Sum of Maximums 100 (p) 1.0s 256M
3 USACO 2024 February Contest, Platinum, Infinite Adventure 100 (p) 1.0s 512M

1. USACO 2024 February Contest, Platinum, Lazy Cow

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

Bessie đang chuẩn bị bài tập cho cuộc thi USA Cowmputing Olympiad vào tháng \(2\). Mỗi phút, cô ấy có thể chọn không chuẩn bị bài tập nào và không tốn sức lực; hoặc dùng \(3^{a-1}\) năng lượng để chuẩn bị \(a\) bài, \(a > 0\).

Nông dân John có \(D (1\le D \le 2*10^5)\) yêu cầu. Với yêu cầu thứ \(i\), Bessie cần phải chuẩn bị ít nhất \(b_i\) bài trong \(m_i\) phút. \((1 \le m_i \le 10^6, 1 \le b_i \le 10^{12})\).

Gọi \(e_i\) là lượng năng lượng tiêu thụ ít nhất Bessie cần để hoàn thành yêu cầu thứ \(i\). In ra \(e_1,…,e_D\) \(mod\) \(10^9+7\).

Input

Dòng đầu chứa số tự nhiên \(D\). Dòng thứ \(i\) trong \(d\) dòng tiếp theo chứa 2 số nguyên \(m_i\) và \(b_i\) cách nhau bởi dấu cách.

Output

In ra \(D\) dòng, dòng thứ \(i\) chứa \(e_i\) \(mod\) \(10^9+7\)

Scoring

  • Subtask \(1\): \(D\le100\) và \(m_i \le 100\)
  • Subtask \(2\): \(D\le3000\)
  • Subtask \(3\): Không có điều kiện gì thêm

Example

Test 1

Input 
4 
5 11 
6 10 
10 15 
10 30
Output 
21 
21 
25 
90
Note

Với test mẫu thứ nhất.

  • \(i=1\): Nếu Bessie tạo ra \([2,3,2,2,2]\) bài tập vào \(5\) ngày đầu, mỗi ngày cô ấy sẽ tốn \(3^1+3^2+3^1+3^1+3^1=21\) đơn vị năng lượng để tạo ra 11 bài vào cuối ngày thứ \(5\)
  • \(i=2\): Bessie có thể làm giống ngày \(1\).
  • \(i=3\): Nếu Bessie tạo \([2,3,2,2,2,0,1,1,1,1]\) trong \(10\) ngày đầu, cô ấy sẽ tiêu tốn \(25\) đơn vị năng lượng và hoàn thành yêu cầu. Có thể thấy không có chiến thuật nào tốt hơn.
  • \(i=4\): Nếu 10 ngày đầu, mỗi ngày Bessie tạo 3 bài thì cô ấy sẽ tiêu tốn \(3^2*10=90\) đơn vị năng lương và hoàn thành yêu cầu.

Với mỗi \(i\), Bessie sẽ không thể thỏa mãn yêu cầu nếu dùng ít năng lượng hơn.

Test 2

Input 
2 
100 5 
100 1000000000000
Output 
5 
627323485

Test 3

Input 
20
303590 482848034083
180190 112716918480
312298 258438719980
671877 605558355401
662137 440411075067
257593 261569032231
766172 268433874550
8114 905639446594
209577 11155741818
227183 874665904430
896141 55422874585
728247 456681845046
193800 632739601224
443005 623200306681
330325 955479269245
377303 177279745225
880246 22559233849
58084 155169139314
813702 758370488574
929760 785245728062
Output 
108753959
108753959
108753959
148189797
148189797
148189797
148189797
32884410
32884410
32884410
32884410
32884410
32884410
32884410
3883759
3883759
3883759
3883759
3883759
3883759

2. USACO 2024 February Contest, Platinum, Minimum Sum of Maximums

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

Bessie có \(N(2 \le N \le 300)\) miếng gạch trên một hàng với độ xấu lần lượt là \(a_1,a_2,…,a_N\), \((1 \le a_i \le 10^6)\). \(K(0 \le K \le min(N,6))\) miếng gạch ở các vị trí \(x_1,…,x_K \space (1\le x_1 < x_2...<x_K \le N)\) bị kẹt.

Bessie muốn tổng độ xấu của viên gạch có độ xấu lớn hơn trong 2 cặp viên gạch liên tiếp: \(\sum_{i=1}^{n-1} max(a_i,a_i+1)\) là nhỏ nhất. Cô ấy có thể thực hiện việc tráo đổi hai viên gạch không bị kẹt bất kì vô số lần.

Hãy tính tổng độ xấu nhỏ nhất có thể nếu Bessie thực việc tráo đổi một cách tối ưu.

Input

  • Dòng đầu chứa hai số \(N\) và \(K\).
  • Dòng tiếp theo chứa \(a_1,…,a_N\).
  • Dòng cuối chứa \(K\) chỉ số \(x_1,…,x_K\).

Output

In ra tổng độ xấu nhỏ nhất có thể.

Scoring

  • Subtask \(1\): \(K=0\)
  • Subtask \(2\): \(K=1\)
  • Subtask \(3\): \(N \le 50\)
  • Subtask \(4\): Không có điều kiện gì thêm.

Example

Test 1

Input 
3 0
1 100 10
Output 
110
Note

Bessie có thể tráo đổi viên gạch thứ \(2\) và \(3\) và có \(a=[1,10,100]\), tổng độ xấu là \(max(1,10)+max(10,100)=110\). Hoặc cô ấy có thể tráo đổi viên gạch thứ \(1\) và \(2\) và có \(a=[100,1,10]\), cũng có tổng độ xấu là \(max(100,1)+max(1,10)=110\).

Test 2

Input 
3 1
1 100 10
3
Output 
110
Note

Bessie có thể tráo đổi viên gạch thứ \(2\) và \(1\) và có \(a=[100,1,10]\), tổng độ xấu là \(max(100,1)+max(1,10)=110\).

Test 3

Input 
3 1
1 100 10
2
Output 
200
Note

Tổng độ xấu ban đầu là \(max(1,100)+max(100,10)=200\). Bessie chỉ có thể tráo đổi viên gạch thứ \(3\) và \(1\), và không thể giảm độ xấu thấp hơn.

Test 4

Input 
4 2
1 3 2 4
2 3
Output 
9

3. USACO 2024 February Contest, Platinum, Infinite Adventure

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

Bessie đang lên kế hoạch cho chuyến thám hiểm tại một vùng đấy có \(N(1 \le N \le 10^5)\) thành phố. Tại mỗi thành phố \(i\), có một cái cổng, cũng như một chu kỳ \(T_i\). Tất cả \(T_i\) đều là lũy thừa của \(2\), và \(T_1+...+T_N \le 10^5\). Nếu bạn đến cổng của thành phố \(i\) vào ngày \(t\), bạn sẽ ngay lập tức thoát ra tại cổng của thành phố \(c_{i,t \space mod \space T_i}\).

Bessie có \(Q(1 \le Q \le 5*10^4)\) kế hoạch cho chuyến đi, mỗi kế hoạch được thể hiện bởi bộ ba số \((v,t,Δ)\). Với mỗi kế hoạch, cô ấy sẽ bắt đầu tại thành phố \(v\) vào ngày \(t\). Cô ấy sẽ làm hành động sau \(Δ\) lần: Cô ấy sẽ đi theo cổng của thành phố hiện tại, sau đó đợi một ngày. Với mỗi kế hoạch, cô ấy muốn biết mình sẽ kết thúc tại thành phố nào.

Input

  • Dòng đầu chứa hai số nguyên cách nhau bởi dấu cách: \(N\) - số đỉnh, và \(Q\) - số truy vấn.

  • Dòng thứ hai chứa \(N\) số nguyên cách nhau bởi dấu cách: \(T_1,T_2,...,T_N(1 \le T_i, \space T_i\) là một lũy thừa của \(2\), \(T_1+...+T_N \le 10^5)\).

  • Với \(i=1,2,…,N\), dòng thứ \(i+2\) chứa \(T_i\) số nguyên dương được ngăn cách bởi dấu cách: \(c_{i,0},…,c_{i,Ti−1}(1≤c_{i,t} \le N)\).

  • Với \(j=1,2,…,Q\), dòng thứ \(j+N+2\) chứa ba số nguyên dương được ngăn cách bởi dấu cách: \(v_j,t_j,Δ_j(1 \le v_j \le N, \space 1 \le t_j \le 10^{18},\space 1 \le Δ_j \le 10^{18})\) của truy vấn thứ \(j\).

Output

In ra \(Q\) dòng. Dòng thứ \(j\) chứa đáp án của truy vấn thứ \(j\).

Scoring

  • Subtask \(1\): \(Δ_j \le 2*10^2\).
  • Subtask \(2\): \(N,\sum T_j \le 2*10^3\).
  • Subtask \(3\): \(N,\sum T_j \le 10^4\).
  • Subtask \(4\): Không có điểu kiện gì thêm.

Example

Test 1

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

Ba chuyến thám hiểm đầu của Bessie diễn ra như sau:

  • Tại chuyến thám hiểm thứ nhất, cô ấy đi từ thành phố \(2\) tại thời điểm \(4\), đến thành phố \(3\) tại thời điểm \(5\), đến thành phố \(4\) tại thời điểm \(6\), đến thành phố \(2\) tại thời điểm \(7\).
  • Tại chuyến thám hiểm thứ hai, cô ấy đi từ thành phố \(3\) tại thời điểm \(3\), đến thành phố \(4\) tại thời điểm \(4\), đến thành phố \(2\) tại thời điểm \(5\), đến thành phố \(4\) tại thời điểm \(6\), đến thành phố \(2\) tại thời điểm \(7\), đến thành phố \(4\) tại thời điểm \(8\), đến thành phố \(2\) tại thời điểm \(9\).
  • Tại chuyến thám hiểm thứ ba, cô ấy đi từ thành phố \(5\) tại thời điểm \(3\), đến thành phố \(5\) tại thời điểm \(4\), đến thành phố \(5\) tại thời điểm \(5\).

Test 2

Input 
5 5
1 2 1 2 8
2
3 4
4
2 3
5 5 5 5 5 1 5 5
2 4 3
3 2 6
5 3 2
5 3 7
5 3 1000000000000000000
Output 
2
3
5
4
2