首页 > 代码库 > Counting Game
Counting Game
There are n people standing in a line, playing a famous game called ``counting". When the game begins, the leftmost person says ``1" loudly, then the second person (people are numbered 1 to n from left to right) says ``2" loudly. This is followed by the 3rd person saying ``3" and the 4th person say ``4", and so on. When the n-th person (i.e. the rightmost person) said ``n" loudly, the next turn goes to his immediate left person (i.e. the (n - 1)-th person), who should say ``n + 1" loudly, then the (n - 2)-th person should say ``n + 2" loudly. After the leftmost person spoke again, the counting goes right again.
There is a catch, though (otherwise, the game would be very boring!): if a person should say a number who is a multiple of 7, or its decimal representation contains the digit 7, he should clap instead! The following tables shows us the counting process for n = 4 (`X‘ represents a clap). When the 3rd person claps for the 4th time, he‘s actually counting 35.
Person | 1 | 2 | 3 | 4 | 3 | 2 | 1 | 2 | 3 |
Action | 1 | 2 | 3 | 4 | 5 | 6 | X | 8 | 9 |
Person | 4 | 3 | 2 | 1 | 2 | 3 | 4 | 3 | 2 |
Action | 10 | 11 | 12 | 13 | X | 15 | 16 | X | 18 |
Person | 1 | 2 | 3 | 4 | 3 | 2 | 1 | 2 | 3 |
Action | 19 | 20 | X | 22 | 23 | 24 | 25 | 26 | X |
Person | 4 | 3 | 2 | 1 | 2 | 3 | 4 | 3 | 2 |
Action | X | 29 | 30 | 31 | 32 | 33 | 34 | X | 36 |
Given n, m and k, your task is to find out, when the m-th person claps for the k-th time, what is the actual number being counted.
Input
There will be at most 10 test cases in the input. Each test case contains three integers n, m and k ( 2n100, 1mn, 1k100) in a single line. The last test case is followed by a line with n = m = k = 0, which should not be processed.
Output
For each line, print the actual number being counted, when the m-th person claps for the k-th time. If this can never happen, print ` -1‘.
Sample Input
4 3 14 3 24 3 34 3 40 0 0
Sample Output
17212735
分析:报数问题,凡是7的倍数或者含7的数就不喊出来。n个人,当第m个人喊这类数p次后输出他们一共喊了多少次。
n+n-2代表循环报数是一个循环有这么多次 如12345432 少了一个5和一个1 换为n也是如此比较
代码:
#include<stdio.h>#include<string.h>#define N 1000001int pu(int x){ if(x%7==0) return 1; while(x) { if(x%10==7) return 1; x/=10; } return 0;}int main(){ int n,m,k,i,j,sum,count[10001]; while(~scanf("%d %d %d",&n,&m,&k)) { sum=0; if(n==0&&m==0&&k==0) break; for(i=1;i<=n;i++) count[i]=i; j=n-1; for(i=n+1;i<n+n-2;i++) { count[i]=j; j--; } for(i=1;i<N;i++) { if(pu(i)==1) { if(i%(n+n-2)==0) { if(count[n+n-2]==m) sum++; } else { if(count[i%(n+n-2)]==m) sum++; } } if(sum==k) { printf("%d\n",i); break; } } if(i==N) printf("-1\n"); } return 0;}
可参考的代码:
#include<set>#include<map>#include<stack>#include<queue>#include<ctime>#include<cmath>#include<vector>#include<string>#include<cstdio>#include<cstdlib>#include<cstring>#include<iostream>#include<algorithm>using namespace std;int n, m, t;bool seven(int k){ if (!(k % 7))return 1; while (k){ if ((k % 10) == 7)return 1; k /= 10; } return 0;}void solve(){ int x = m; int cnt=0; int step = 0; int k1 = 2 * (n - m);//如果向右走回到自己 步数是2*(n-m) int k2 = 2 * (m - 1);//向左走回到自己是2*(m-1) if (seven(x))cnt++; if (t == cnt){ printf("%d\n", x); return;} while (x <= 100000000){ step++; if (step % 2 && k1 == 0)continue; if (!(step % 2) && k2 == 0)continue; if (step % 2)x += k1; else x += k2; if (seven(x))cnt++; if (cnt == t){ printf("%d\n", x); return; } }}int main(){ while (1){ scanf("%d%d%d", &n, &m, &t); if (!n)break; solve(); } return 0;}