列表

详情


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;
}

上一题