#PU1404. USACO 2024 February Contest, Platinum — Problem 1. Lazy Cow

    ID: 1421 传统题 2000ms 256MiB 尝试: 0 已通过: 0 难度: 省选/NOI- 上传者: 标签>USACO赛事:feb24来源:usaco.orgscoring:equal_test_cases贪心数学

USACO 2024 February Contest, Platinum — Problem 1. Lazy Cow

USACO 2024 February Contest, Platinum — Problem 1. Lazy Cow

题目描述

Bessie is hard at work preparing test cases for the USA Cowmputing Olympiad February contest. Each minute, she can choose to not prepare any tests, expending no energy; or expend 3a−13^{a-1} energy preparing aa test cases, for some positive integer aa. Farmer John has DD (1≤D≤2⋅1051\le D\le 2\cdot 10^5) demands. For the iith demand, he tells Bessie that within the first mim_i minutes, she needs to have prepared at least bib_i test cases in total (1≤mi≤106,1≤bi≤10121\le m_i\le 10^6, 1 \leq b_i \leq 10^{12}). Let eie_i be the smallest amount of energy Bessie needs to spend to satisfy the first ii demands. Print e1,…,eDe_1,\dots,e_D modulo 109+710^9+7.

输入格式

The first line contains DD. The iith of the next DD lines contains two space-separated integers mim_i and bib_i.

输出格式

(见题面原文)

数据范围

Inputs 4-5: D≤100D\le 100 and mi≤100m_i \le 100 for all ii Inputs 6-8: D≤3000D\le 3000 Inputs 9-20: No additional constraints. Problem credits: Brandon Wang and Claire Zhang

样例

样例 1

4
5 11
6 10
10 15
10 30
21
21
25
90
For the first test case,
$i=1$: If Bessie creates $[2, 3, 2, 2, 2]$ test cases on the first $5$
days, respectively, she would have expended $3^1 + 3^2 + 3^1 + 3^1 + 3^1 = 21$
units of energy and created $11$ test cases by the end of day $5$.
$i=2$: Bessie can follow the above strategy to ensure $11$ test cases are
created by the end of day $5$, and this will automatically satisfy the second
demand.
$i=3$: If Bessie creates $[2, 3, 2, 2, 2, 0, 1, 1, 1, 1]$ test
cases on the first $10$ days, respectively, she would have expended $25$ units
of energy and satisfied all demands. It can be shown that she cannot expend less
energy.
$i=4$: If Bessie creates 3 test cases on each of the first
$10$ days she would have expended $3^{2}\cdot 10 = 90$ units of energy and
satisfied all demands.
For each $i$, it can be shown that Bessie cannot satisfy the first $i$ demands using
less energy.

样例 2

2
100 5
100 1000000000000
5
627323485

样例 3

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
108753959
108753959
108753959
148189797
148189797
148189797
148189797
32884410
32884410
32884410
32884410
32884410
32884410
32884410
3883759
3883759
3883759
3883759
3883759
3883759