Problem 3035 --Getting Your Money Back

3035: Getting Your Money Back

"
Time Limit $1$ 秒/Second(s) Memory Limit $512$ 兆字节/Megabyte(s)
提交总数 $1$ 正确数量 $1$
裁判形式 标准裁判/Standard Judge 我的状态 尚未尝试
难度 分类标签
For some weird security reason, Cuber Bank now shuts down the interface where you can check your balance on your bank account. From now on, when you click the "check" button on your interface, they will show you a range, saying that the money in your account has to be one of the integers between xx and yy, inclusive. Yes, less informative, but more secure. 

Perhaps you are not convinced of their explanation, and you get annoyed as much as I do. Moreover, you are the kind of person who won't get a good sleep until you see from your screen that your beloved money is lying right in your bank account, safe and sound. Since Cuber Bank can't provide this service any more, it's time to withdraw all your money and go for another bank. 

However, when you went to the bank the other day, the manager Cuber QQ told you that, there have been so many people trying to close their account recently, so that they have to do something: to make the rule that you have to pay an extra fee each time you attempt to withdraw money from your account. 

There is a machine you can interact with. After you insert your card, the proceses goes in an interactive way, just like playing a game. The machine first tells you a range, [x,y][x,y], which your balance is currently between. Then at each attempt, you type in the amount of money (also an integer) you want to withdraw; the machine then tell you whether your operation is successful or not (successful if and only if the amount fits your balance). In order to prevent excessive requests that cause great pressure on the system, if successful you have to pay aa dollars for this attempt; if fail you have to pay bb dollars. You pay these fees with cash, brought by yourself. You can do more attempts until you are very convinced that there is no more money on your account. The machine will not disclose any further information about any range after the first attempt. 

Devise a strategy that will cost you the least dollars of extra fees in the worst case, in order to retrieve all the money from your account.
The first line of the input is an integer tt (1≤t≤1041≤t≤104), which means tt test cases will follow. 

The follows tt test cases, each is one line of space-separated integers xxyyaabb (0≤x≤y≤2⋅1050≤x≤y≤2⋅1050≤a,b≤1090≤a,b≤109). 

The sum of yy in all test cases does not exceed 8⋅1068⋅106.
For each test case, output the extra dollars you have to prepare in one line. 

Here are some notes for the sample below. 

In sample 1, the first attempt should be a retrieval of 11 dollar. If this works, there might be one more dollar (or not), for which you need to pay 2+max(2,3)=52+max(2,3)=5altogether; if it fails, then you are done, for which you need to pay 33 dollars. 

In sample 2, try 22 dollars first, pay 33 dollars if succeeded; otherwise, the balance could be 00 or 11 dollars, for which you will need to pay 2+max(2,3)=52+max(2,3)=5 dollars altogether.
2
0 2 2 3
0 2 3 2
5
5

推荐代码 查看3035 所有题解 上传题解视频得图灵币

本题记录 用 户(点击查看用户) 运行号(点击购买题解) 时 间
算法最快[$396 $ms] 淡意的温柔 588061 2020-05-27 09:49:21
内存最少[$0 $KB] 淡意的温柔 588061 2020-05-27 09:49:21
第一AC 淡意的温柔 588061 2020-05-27 09:49:21
第一挑战 淡意的温柔 588061 2020-05-27 09:49:21

赛题来源/所属竞赛 2019 Multi-University Training Contest 7 N/A

竞赛编号 竞赛名称 竞赛时间 访问比赛