OR48. 兔子藏洞
描述
一只兔子藏身于20个圆形排列的洞中(洞从1开始编号),一只狼从x号洞开始找,下次隔一个洞找(即在x+2号洞找),在下次个两个洞找(即在x+5号洞找),它找了n次仍然没有找到。问兔子可能在那些洞中。输入描述
输入有多组数据,每组数据一行两个整数分别为x和n(x <= 20,n <= 100000)输出描述
每组数据一行按从小到大的顺序输出兔子可能在的洞,数字之间用空格隔开。若每个洞都不肯能藏着兔子,输出-1。C++ 解法, 执行用时: 1ms, 内存消耗: 220KB, 提交时间: 2017-07-20
//7.05 #include<iostream> #include<vector> #include<algorithm> using namespace std; int main() { int x,n; while (cin>>x>>n) { x--; vector<int> v(20,0); v[x]++; //int j = x; for (int i = 1;i < n;i++) { v[(x+i+1) % 20]++; x = x + i + 1; } vector<int> res; for (int j = 0;j < 20;j++) { if (v[j] == 0) res.push_back(j); } if (res.empty()) cout<<-1<<endl; else { for (int j = 0;j < res.size();j++) cout<<res[j]+1<<' '; } cout<<endl; res.clear(); v.clear(); } return 0; } //7.45
C 解法, 执行用时: 2ms, 内存消耗: 368KB, 提交时间: 2020-11-08
#include<stdio.h> int main(){ int x,n; while(scanf("%d %d",&x,&n)!=EOF){ int a[21]={0}; int i=x,j,k=2,c=20; while(n--){ if(a[i]==0){ a[i]=1; c--; } i+=k; k++; if(i>20) i%=20; } if(c==0) printf("-1\n"); else{ for(j=1;j<=20;j++){ if(a[j]==0 && c>1){ printf("%d ",j); } } printf("\n"); } } return 0; }