D.Tea--ACM-ICPC 2016 Qingdao Preliminary Contest

https://nanti.jisuanke.com/t/29368
Tea is good.

Tea is life.

Tea is everything.

The balance of tea is a journey of pursuing balance of the universe.

Alice knows that.

Alice wants to teach you the art of pouring tea.

Alice has a pot of tea.

The exact volume of tea is not important.

The exact volume of tea is at least LL.

The exact volume of tea is at most RR.

Alice put two empty cups between you and her.

Alice wants the two cups filled by almost equal volume of tea.

Yours cannot be 11 unit more than hers.

Hers cannot be 11 unit more than yours.

Alice wants you to pour the tea.

Alice wants you to pour until the pot is almost empty.

Alice wants no more than 11 unit volume of tea remaining in the pot.

You cannot read the residue volume of tea remaining in the pot.

You can only know the tea status in the pot, empty or not.

Alice does not want you to pour the tea too many times.

You better pour as few times as possible.

Input Format

There are multiple cases.

For each case, there is one line of two integers LL and RR, separated by single space.

Here are some analyses about sample cases.

For the first case, pouring 11 unit into one cup will satisfy Alice.

For the second case, it is clearly that you cannot only pour once to reach the desired balance, but she can achieve it by pouring twice.

First you pour 1.51.5 units into one cup, then you attempt to pour another 1.51.5 units into the other cup.

Since the lower bound is 22, at least 0.50.5 unit remains in the pot after the first pouring.

If the initial volume is in range [2,\ 3][2, 3], the second cup will have volume in range [0.5,\ 1.5][0.5, 1.5] which is balanced with 1.51.5 unit in the first cup, and at most 11 unit remain after these two attempts.

About 10001000 test cases, and 0\le L\le R \le 10^{16}0≤L≤R≤10
16
.

Output Format

For each case, there should be a single integer in a single line, the least number of pouring attempts.

样例输入

1
2
2 2
2 4

样例输出

1
2
1
2

题目来源
ACM-ICPC 2016 Qingdao Preliminary Contest

题解:

一开始的策略有点问题,第一杯倒 l/2 第二杯倒 l/2+1 这样不一定是最优的;

举个例子(4 9)这组数据,第一杯2,第二杯3,第一杯2+2,第二杯还需要再加一次;

而第一杯倒(l+1)/2 ,第二杯倒(l+1)/2+1的话,(4 9),第一杯2.5 第二杯3.5 第一杯 2.5 +2,达成要求;

所以最优策略是第一杯倒(l+1)/2 ,第二杯倒(l+1)/2+1 ,然后剩下的轮流加2,直至壶中水小于等于1;

特判几个特殊情况,具体见代码,需要注意的是,如果l=0,那么一开始(0+1)/2=0,显然不倒水是不划算的,所以如果特判结束后l=0则l=1;


###代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <fstream>
#include <map>
#include <queue>
#include <string>
#include <set>
#include <cmath>
#include <list>
#include <vector>
using namespace std;

#define LL long long
int main(){
LL l,r;
while(~scanf("%lld%lld",&l,&r)){
if(r==0||r==1)puts("0");
else if(r==2)puts("1");
else if(l==r||l==r-1)puts("2");
else{
if(l==0)l=1;
printf("%lld\n",(r-l+2)/2);
}
}
return 0;
}
打赏
  • 版权声明: 本博客所有文章除特别声明外,著作权归作者所有。转载请注明出处!
  • Copyrights © 2018-2021 LeFlacon

奶茶一杯 快乐起飞

支付宝
微信