CodeForces 82A Double Cola

ゞ浴缸里的玫瑰 2022-02-21 00:59 60阅读 0赞

>  
> 
> A. Double Cola
> 
> time limit per test
> 
> 1 second
> 
> memory limit per test
> 
> 256 megabytes
> 
> input
> 
> standard input
> 
> output
> 
> standard output
> 
> Sheldon, Leonard, Penny, Rajesh and Howard are in the queue for a "Double Cola" drink vending machine; there are no other people in the queue. The first one in the queue (Sheldon) buys a can, drinks it and doubles! The resulting two Sheldons go to the end of the queue. Then the next in the queue (Leonard) buys a can, drinks it and gets to the end of the queue as two Leonards, and so on. This process continues ad infinitum.
> 
> For example, Penny drinks the third can of cola and the queue will look like this: Rajesh, Howard, Sheldon, Sheldon, Leonard, Leonard, Penny, Penny.
> 
> Write a program that will print the name of a man who will drink the *n*\-th can.
> 
> Note that in the very beginning the queue looks like that: Sheldon, Leonard, Penny, Rajesh, Howard. The first person is Sheldon.
> 
> Input
> 
> The input data consist of a single integer *n* (1 ≤ *n* ≤ 109).
> 
> It is guaranteed that the pretests check the spelling of all the five names, that is, that they contain all the five possible answers.
> 
> Output
> 
> Print the single line — the name of the person who drinks the *n*\-th can of cola. The cans are numbered starting from 1. Please note that you should spell the names like this: "Sheldon", "Leonard", "Penny", "Rajesh", "Howard" (without the quotes). In that order precisely the friends are in the queue initially.

>  
> 
> Examples
> 
> input
> 
> Copy
> 
>     1
> 
> output
> 
> Copy
> 
>     Sheldon
> 
> input
> 
> Copy
> 
>     6
> 
> output
> 
> Copy
> 
>     Sheldon
> 
> input
> 
> Copy
> 
>     1802
> 
> output
> 
> Copy
> 
>     Penny

题目大意：五个人排队买喝的，一个人买完后，会变成两个他在队尾继续排队，例如：a b c d e aa bb cc dd ee aaaa bbbb cccc dddd eeee……问你第你n个人是谁  
思路:观察可得是个等比数列，第一个5，第二个10，第三个20，……公比是2，我们可以求出前n项和，找到这一轮是第几轮，再除以本轮的倍数即可，具体看代码（PS:貌似这题数据有点水，之前看到一篇博客上面n=7竟然输出的是Leonard，这样也能过！！！太水了。

/*
    题目大意：五个人排队买喝的，一个人买完后，会变成两个他在队尾继续排队，问你第你n个人是谁
    思路:观察可得是个等比数列，我们可以求出前n项和，找到这一轮是第几轮，再除以本轮的倍数即可，具体看代码
    */
    #include<map>
    #include<set>
    #include <vector>
    #include<stack>
    #include<queue>
    #include<cmath>
    #include<string>
    #include<cstdio>
    #include<cstring>
    #include<cstdlib>
    #include<iostream>
    #include<algorithm>
    using namespace std;
    #define ll unsigned long long
    #define inf 0x3f3f3f
    #define esp 1e-8
    #define bug {printf("mmp\n");}
    #define mm(a,b) memset(a,b,sizeof(a))
    #define T() int test,q=1;scanf("%d",&test); while(test--)
    const int maxn=2e5+10;
    const double pi=acos(-1.0);
    const int N=201;
    const int mod=1e9+7;
    ll a[maxn],b[maxn];
    void ff()
    {
        ll sum=5;
        for(int i=0; i<=100; i++)
        {
            a[i]=a[i-1]+sum;
            sum*=2;
           i>1? b[i]=b[i-1]*2:b[i]=2;
        }
    }
    void print(int n)
    {
        switch(n)
        {
        case 1:
            cout<<"Sheldon"<<endl;
            break;
        case 2:
            cout<<"Leonard"<<endl;
            break;
        case 3:
            cout<<"Penny"<<endl;
            break;
        case 4:
            cout<<"Rajesh"<<endl;
            break;
        case 5:
            cout<<"Howard"<<endl;
            break;
        }
    }
    int main()
    {
        ff();
        int n,index=0;
        cin>>n;
        if(n<6)
        {
            print(n);
            return 0;
        }
        for(int i=0; i<100; i++)
        {
            if(n<=a[i])
            {
                index=i;///找到他属于第几轮
                break;
            }
        }
        n-=a[index-1];
        int ans=(n-1)/b[index]+1;
        print(ans);
        return 0;
    }