[PA2015]Hazard

Time Limit: 10 Sec  Memory Limit: 512 MB

Submit: 69  Solved: 19

[][][]

Description

有n个人在轮流玩赌博机，一开始编号为i的人有a[i]元钱。赌博机可以抽象为一个长度为m的仅包含1和-1的序列，若抽到1，那么你将得到1块钱；若抽到-1，你将输掉1块钱。

第1局，第1个人会抽到序列中的第1项；第2局，第2个人会抽到序列中的第2项；第3局，第3个人会抽到序列中的第3项......即：第i个人抽完后轮到第i+1个人去抽，特别地，第n个人抽完后轮到第1个人去抽。序列第i项被抽到之后，下一个被抽到的将会是第i+1项，特别地，序列第m项被抽到之后，下一个被抽到的将会是第1项。

如果在某一轮，有个人输光了所有的钱，那么这场赌博游戏就会结束，请求出游戏在哪一轮结束，或者判断这个游戏会永远进行下去。

Input

第一行包含一个正整数n(1<=n<=1000000)，表示玩家的个数。

第二行包含n个正整数a[1],a[2],...,a[n](1<=a[i]<=1000000)，依次表示每个玩家一开始持有的钱数。

第一行包含一个正整数m(1<=m<=1000000)，表示序列的长度。

第四行包含一个长度为m的仅包含W和P的字符串，表示这个序列，其中W表示1，P表示-1。

Output

若游戏会永远进行下去，输出-1。否则输出游戏在哪一轮结束。

Sample Input

4

2 3 2 1

3

WPP

Sample Output

12

HINT

 

Source

 

 

题解：发现最大的

f(n)不会超过9∗9∗18=1458，因此我们枚举f(n)，O(logn)Check即可

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 #include
          
            6 #include
           
             7 8 #define ll long long 9 using namespace std;10 inline ll read()11 {12 ll x=0,f=1;char ch=getchar();13 while(ch<'0'||ch>'9'){ if (ch=='-') f=-1;ch=getchar();}14 while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}15 return x*f;16 }17 18 ll n,m;19 ll k,a,b;20 21 ll F (ll x)22 {23 ll res=0;24 while(x)25 {26 res+=(x%10)*(x%10);27 x/=10;28 }29 return res;30 }31 int main()32 {33 ll ans=0;34 k=read(),a=read(),b=read();35 for (int i=min(1458ll,b/k);i>=1;i--)36 {37 ll n=i*k;38 if (n>=a&&i==F(n)) ans++;39 }40 printf("%lld\n",ans);41 }