2016 年青島網絡賽---Tea，2016青島賽---tea
題目鏈接
http://acm.hdu.edu.cn/showproblem.php?pid=5881
Problem Description
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 L.
The exact volume of tea is at most R.
Alice put two empty cups between you and her.
Alice wants the two cups filled by almost equal volume of tea.
Yours cannot be 1 unit more than hers.
Hers cannot be 1 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 1 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
There are multiple cases.
For each case, there is one line of two integers L and R, separated by single space.
Here are some analyses about sample cases.
For the first case, pouring 1 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.5 units into one cup, then you attempt to pour another 1.5 units into the other cup.
Since the lower bound is 2, at least 0.5 unit remains in the pot after the first pouring.
If the initial volume is in range [2,3], the second cup will have volume in range [0.5,1.5] which is balanced with 1.5 unit in the first cup, and at most 1 unit remain after these two attempts.
About 1000 test cases, and 0≤L≤R≤1016.
Output
For each case, there should be a single integer in a single line, the least number of pouring attempts.
Sample Input
2 2
2 4
Sample Output
1
2
Source
2016 ACM/ICPC Asia Regional Qingdao Online
Recommend
wange2014 | We have carefully selected several similar problems for you: 5891 5890 5889 5887 5886
題意：輸入L,R 表示一壺茶的茶的體積的范圍L~R，不確定精確量（整數）， 現在往兩個茶杯中倒茶（不考慮茶杯容量） ，要求使兩個茶杯中茶相差不超過1 ，而茶壺中剩余的茶不能超過1， 求最少倒茶的次數；
樣例解釋一下：2 2 答案是1 ，我們可以往第一個茶杯中倒1 ，第二杯不倒， 那麼兩個茶杯相差為1 ，茶壺剩余量為0~1 ， 符合題目要求； 2 4 答案是2 ，我們可以往第一杯倒入1.5 那麼第二杯按1.5 到，如果茶壺 茶量為2，那麼第二杯倒入0.5 兩倍相差1 茶壺為0 符合題目要求，如果茶壺 茶量為4， 第二杯倒入1.5 兩杯量相同， 茶壺剩余1， 符合題目要求；
思路： 先考慮普通情況，第一杯倒入（L+1）/2, 第二杯按照（L+1）/2+1倒， 那麼如果茶壺量為L<=茶壺<=L+2 ,則茶壺為0 了，兩杯茶相差0~1 ；如果情況糟糕茶壺不空，那麼接下來往第一杯中倒入2 ，第二杯中倒入2 ，第一杯中倒入2 ......知道茶壺不足2 （即茶壺剩余量為0或者1） ，這樣兩杯茶始終相差1，符合題意；
代碼如下：
#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <queue>
#include <cmath>
#include <string.h>
using namespace std;
int main()
{
long long L,R;
while(scanf("%lld%lld",&L,&R)!=EOF)
{
if(L==R)
{
if(R<=1) puts("0");
else if(R==2) puts("1");
else puts("2");
continue;
}
if(L==0)
{
if(R==1) puts("0");
else if(R==2) puts("1");
else printf("%lld\n",(R+1)/2);
}
else
{
if(L==1&&R==2) puts("1");
else{
if(L+2>=R-1) puts("2");
else printf("%lld\n",(R-L+2)/2);
}
}
}
return 0;
}
