2013ACM/ICPC亞洲區南京站現場賽---Poor Warehouse Keeper(貪心)，icpc---poor

2013ACM/ICPC亞洲區南京站現場賽---Poor Warehouse Keeper(貪心)，icpc---poor

題目鏈接

http://acm.hdu.edu.cn/showproblem.php?pid=4803

 

Problem Description Jenny is a warehouse keeper. He writes down the entry records everyday. The record is shown on a screen, as follow:

There are only two buttons on the screen. Pressing the button in the first line once increases the number on the first line by 1. The cost per unit remains untouched. For the screen above, after the button in the first line is pressed, the screen will be:

The exact total price is 7.5, but on the screen, only the integral part 7 is shown.
Pressing the button in the second line once increases the number on the second line by 1. The number in the first line remains untouched. For the screen above, after the button in the second line is pressed, the screen will be:

Remember the exact total price is 8.5, but on the screen, only the integral part 8 is shown. 
A new record will be like the following:

At that moment, the total price is exact 1.0.
Jenny expects a final screen in form of:

Where x and y are previously given.
What’s the minimal number of pressing of buttons Jenny needs to achieve his goal?     Input There are several (about 50, 000) test cases, please process till EOF.
Each test case contains one line with two integers x(1 <= x <= 10) and y(1 <= y <= 10⁹) separated by a single space - the expected number shown on the screen in the end.     Output For each test case, print the minimal number of pressing of the buttons, or “-1”(without quotes) if there’s no way to achieve his goal.     Sample Input 1 1 3 8 9 31     Sample Output 0 5 11     Hint For the second test case, one way to achieve is: (1, 1) -> (1, 2) -> (2, 4) -> (2, 5) -> (3, 7.5) -> (3, 8.5)   Source 2013ACM/ICPC亞洲區南京站現場賽——題目重現  

 

Recommend liuyiding   |   We have carefully selected several similar problems for you:  5901 5899 5898 5897 5896        題意：有一種顯示器帶有兩個按鈕，顯示器上有兩個數 ，顯示器只能顯示整數，小數部分不顯示（實際上是小數，只是小數部分不顯示出來），顯示器上的的初始數為x=1.0  y=1.0  ，如果按上面一個按鈕，第一個數x加一，y變為y=(y/x)*(x+1),  如果按下面一個按鈕，x不變，y加一，現在輸入兩個數，求最小的步數使得1 1 變到這兩個數；   思路： (1, 1) -> (1, 2) -> (2, 4) -> (2, 5) -> (3, 7.5) -> (3, 8.5)  分析這個樣例，設輸入的兩個數為x  y  s1=1.0  s2=1.0 我們可以先增加s2值，盡可能的增加s2值，但要保證增加後的s2值滿足s2/s1<=y/x  為什麼呢？ 這樣做是為了保證增加s1 的時候不會讓s2 大於y  然後增加一次s1，再回到上面的過程增加s2 ...... s1小於10 所以復雜度很低的。 最後要注意一下精度，因為顯示器不顯示小數部分，所以可以把y加上0.99999999 ；   代碼如下：

#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
#include <set>
#include <queue>
#include <vector>
using namespace std;
const double esp=1e-8;

int main()
{
    double x,y,s1,s2;
    while(scanf("%lf%lf",&x,&y)!=EOF)
    {
        y+=0.9999999;
        long long sum=0;
        if(x>y) { puts("-1"); continue; }
        s1=1.0; s2=1.0;
        while(1)
        {   if(s1-x+esp>=esp&&s1-(x+1)<esp) break;
            long long t=(long long)(y*s1/x-s2);
            sum+=t;
            s2=s2+t;

            s2=s2*(s1+1)/s1;
            s1=s1+1;
            sum++;
            if(s1>=x&&s1-(x+1)<esp) break;
        }
        sum+=(long long)(y-s2);
        printf("%lld\n",sum);
    }
    return 0;
}