首页 > 试题广场 >

兔子藏洞

[编程题]兔子藏洞

热度指数：10027 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

一只兔子藏身于20个圆形排列的洞中（洞从1开始编号），一只狼从x号洞开始找,下次隔一个洞找(即在x＋2号洞找)，在下次个两个洞找(即在x＋5号洞找)，它找了n次仍然没有找到。问兔子可能在那些洞中。

输入描述:

输入有多组数据，每组数据一行两个整数分别为x和n(x <= 20,n <= 100000)

输出描述:

每组数据一行按从小到大的顺序输出兔子可能在的洞，数字之间用空格隔开。若每个洞都不肯能藏着兔子，输出-1。

算法知识视频讲解

fight灬奋斗

#include <iostream>
#include <set>
using namespace std;
int main(){
    int x,n;
    while(cin>>x>>n){
        int i=2;
        set<int> s;
        x=x-1;
        while(n>0){
            s.insert(x);
            x=(x+i)%20;
            i++;
            n--;
        }
        for(int i=0;i<20;i++)
            if(s.find(i)==s.end())
            	cout<<i+1<<" ";
        cout<<endl;
    }
    return 0;
}

发表于 2016-08-25 21:51:05 回复(3)

lzytj

奇葩，居然还要在最后输出一个空格后再换行，我还特意去掉最后一个空格了呢

发表于 2016-07-01 09:45:16 回复(9)

无大范围亲阿飞啊啊

出的烂题，下次隔一个，再下次隔两个，那再下次隔多少个？？？题目都没表达清楚，怎么做

发表于 2017-03-04 15:27:10 回复(2)

Python

华科平凡

python解法

**题目，“数字之间用空格隔开”出题的人仔细看一下你写的东西。最后还要加一个空格才能通过，故意坑人？

while True:
    try:
        x, n = map(int, input().split())
        arr = [True] * 20
        for i in range(2, n + 2):
            arr[x - 1] = False
            x = (x + i) % 20
        res = [str(i + 1) for i, v in enumerate(arr) if v == True]
        print(" ".join(res)+" " if res else -1)
    except:
        break

发表于 2018-04-13 19:35:16 回复(0)

击水3千

#include<iostream>
using namespace std;
int main(){
    int x,n;
   while(cin>>x>>n){
        int a[21]={0},j=2;
        for(int i=0;i<n;++i){
            if(x%20==0)a[20]=1;
            a[x%20]=1;
            x+=j;
            j++;
        }
        int f=0;
        for(int i=1;i<21;++i){
            if(a[i]==0){
                f=1;
                cout<<i<<" ";
            }
        }
       if(f==0)cout<<-1;
        cout<<endl;
    }
}

发表于 2017-02-28 21:09:30 回复(0)

龙虾姐夫

真是狡兔三窟啊，输出咋多了一段尾巴，原来在每组数据结束的时候加上换行符！

import java.util.*;
public class Main{
    public static void main(String[] args)
    {
        Scanner scan=new Scanner(System.in);               
        while(scan.hasNext())
        {
            int[] home=new int[20];
            for(int i=0;i<20;i++)
            {
                home[i]=1;
            }           
            int x=scan.nextInt();
            int n=scan.nextInt();
            
            int index=x-1;
            for(int i=1;i<=n;i++)
            {
                if(index>19)
                {
                   index=index%20;
                }                                           
                home[index]=0;
                
                index=index+i+1;  
            }
            
            boolean flage=false;
            for(int i=0;i<20;i++)
            {
                if(home[i]==1)
                {
                    System.out.print(i+1+" ");
                    flage=true;
                }
            }    
            if(flage==false)
            {
                System.out.println(-1);
            }
            System.out.println();    
        }
    }
}

编辑于 2016-09-09 13:01:46 回复(0)

kestars

import java.util.*;

public class Main{
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        while(sc.hasNext()){
            int x=sc.nextInt();
            int n=sc.nextInt();
            boolean[] hide=new boolean[21];
            for(int i=1;i<=20;i++)
                hide[i]=true;
            hide[x]=false;
            for(int i=0;i<n;i++){
                int index=nextHole(i);
                index=(x+index)%20;
                if(index==0)
                    index=20;
                hide[index]=false;
            }
            ArrayList<Integer> list=new ArrayList<Integer>();
            for(int i=1;i<=20;i++){
                if(hide[i])
                    list.add(i);
            }
            if(list.size()>0){
                for(int i=0;i<list.size()-1;i++)
                    System.out.print(list.get(i)+" ");
                System.out.println(list.get(list.size()-1)+" ");
            }else{
                System.out.println("-1"+" ");
            }
        }
    }

    public static int nextHole(int n){
        int sum=0;
        for(int i=2;i<=n+2;i++){
            sum+=i;
        }
        return sum;
    }
}

发表于 2018-10-06 11:42:15 回复(0)

wumingde110

#include <iostream>
using namespace std;
int main()
{

    int x, n;
    int dong;
    int *result=new int[20]();
    int mm = 0;
    while(cin>>x>>n)
    {

        dong = x - 1;
        for (int i = 1; i <= n; i++)
        {
            dong = dong + i + 1;
            result[dong % 20] = 1;
        }

        for (int i = 0; i < 20; i++)
        {
            if (result[i] == 0)
            {
                cout << i + 1 << " ";
            }
            else {
                result[i] = 0;
                mm++;
            }
        }
        if (mm == 20) cout << -1;
        mm = 0;
        cout << endl;
    }

}

发表于 2018-08-27 15:51:01 回复(0)

VagrantYang

package com.special.first;

import java.util.Scanner;

/**
 * CVTE01-兔子藏洞
 *
 * 又是哈希思想哦
 * 我们用一个数组来表示20的洞
 * 然后对于狼访问过得洞设置一个值，数组索引为洞的编号减一
 * 之所以我们处理洞的编号从0开始到19
 * 是为了循环处理方便，因为是个圆形排列，超过数组大小时势必要从头开始
 * 引入从0开始，我们可以直接把当前的索引与洞的数量取余即可得到当前合法的洞号
 *
 * 另一个变量count则记录着下一次需要走的间隔
 * Create by Special on 2018/3/4 14:14
 */
public class Pro037 {
    static final int SIZE = 20;

    public static void findRabbit(boolean[] map, int x, int n){
        int index = x - 1, count = 2;
        for(int i = 1; i <= n; i++){
            map[index] = true;
            index += count;
            if(index >= SIZE){
                index %= SIZE;
            }
            count++;
        }
    }
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        while(input.hasNext()){
            int x = input.nextInt();
            int n = input.nextInt();
            boolean[] map = new boolean[SIZE];
            findRabbit(map, x, n);
            boolean flag = false;
            for(int i = 0; i < SIZE; i++){
                if(!map[i]) {
                    System.out.print((i + 1) + " ");
                    flag = true;
                }
            }
            System.out.println(!flag ? "-1" : "");
        }
    }
}

发表于 2018-03-04 14:36:53 回复(0)

C/C++

nbgao

#include <bits/stdc++.h>

using namespace std;

int main()
{     int x,n;     while(cin>>x>>n){         int i = 2;         set<int> s;         x--;         while(n){             s.insert(x);             x = (x+i)%20;             i++;             n--;         }         for(int i=0;i<20;i++)             if(s.find(i) == s.end())                 cout<<i+1<<" ";         cout<<endl;     }     return 0;
}

发表于 2017-11-26 02:07:07 回复(0)

C/C++

void12

使用类似于钟表的时、分、秒换算方法，20个兔子洞形成一个环，在超出20的时候会重新从1开始计算，这时就只需计算该数与20的模即可。
另外就是依次隔一个、隔两个、隔三个的实现，纸上画出来就很容易找到规律，模拟出来即可。
调试过程中出错地方在于提示vector越界，经检查发现是两个for循环的上界错写为n，实际上应该是兔子洞圈的标号上界。

#include "stdafx.h"    
#include
#include
using namespace std;
int x, n;
int main() {
    while (cin >> x >> n) {
        vectorbook(21);
        vectorans;
        int flag = 0;
        for (int i = 1; i <= n; i++) {
            if (x%20==0) book[20]=1;
            book[x%20] = 1;
            x = x + i + 1;
        }
        int bookedNum = 0;
        for (int i = 1; i <= 20; i++) {
            if (book[i] == 0) {
                ans.push_back(i);
            }
            else {
                bookedNum++;
            }
        }
        if (bookedNum == 20) {
            flag = 1;
            cout << -1 << endl;
            break;
        }
        else if (flag == 0) {
            for (int i = 0; i<ans.size(); i++) {
                cout << ans[i] << " ";
            }
            cout << endl;
        }
        ans.clear();
    }
    return 0;
}

发表于 2017-08-21 15:51:04 回复(0)

蓝魔4

#include<iostream>
#include<vector>
using namespace std;
const int Size=20;
int main()
{
	//vector<bool> hole(Size);
	int x,n;
	while(cin>>x>>n)
	{
        vector<bool> hole(Size);
        int index=x-1;
		for(int i=1;i<=n;i++)
        {
            if(index>19)
                index=index%20;
            hole[index]=1;
            index=index+i+1;
        }
        int count=0;
		for(int i=0;i<20;i++)
		{
			if(!hole[i])
            {
                count++;
				cout<<i+1<<" ";
            }
		}
        if(count)
			cout<<endl;
        else
            cout<<-1<<endl;
	}
	return 0;
}

发表于 2017-07-06 10:00:12 回复(0)

MaiFree

这- -绝对是最运算速度最快的AC代码- -
哈哈哈哈，还有谁

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String s = null;
        while((s = br.readLine()) != null){
           String ch[]=s.split(" ");
           int x=Integer.parseInt(ch[0]);
           int n=Integer.parseInt(ch[1]);
           boolean sb[]=new boolean[20];
           int start=x+1;
           int diaoni[]=new int[8];
           for(int i=0;i<8;i++){
               if(start>20)
                   start=start-20;
               diaoni[i]=start;
               if(i%2==0)
                   start=start+2;
               else
                   start=start+3;
           }
             Arrays.sort(diaoni);
            for(int i=0;i<8;i++){
                System.out.print(diaoni[i]+" ");
            }
            System.out.println();
                    
            
           
        }

发表于 2017-06-14 21:55:35 回复(1)

谁是谁的眼

//pass~
#include <stdio.h>
#include <stdlib.h>

struct node
{
	int num;
	struct node* next;
};

typedef struct node Node;
typedef Node* Link;

void createLink(Link *head)
{
	*head = NULL;
}

void tailInsert(Link *head,Link *newNode)
{
	if(NULL == *head)
	{
		(*newNode)->next = *head;
		*head = *newNode;
	}
	else
	{
		Link temp = *head;
		
		while(temp->next != NULL)
		{
			temp = temp->next;
		}
		
		temp->next = *newNode;
		(*newNode)->next = NULL;
	}
}

Link findHole(Link head,int begin)
{
	Link temp = head;
	
	while(temp->num != begin)
	{
		temp = temp->next;
	}
	
	return temp;
}

void printResult(Link head)
{
	int i;
	Link temp = head;
	
	for(i = 0; i < 20; i++)
	{
		if(temp->num != 0)
		{
			printf("%d ",temp->num);
		}
		
		temp = temp->next;
	}
	printf("\n");
}

int procress(Link head,int begin,int times)
{
	int i;
	int j = 1;
	Link temp = findHole(head,begin);
	
	while(times>0)
	{
		temp->num = 0;
		
		for(i = 0; i <= j; i++)
		{
			temp = temp->next;
		}
		
		j++;
		
		times--;
	}
	
	printResult(head);
	
	return 0;
}

int main()
{
	int i;
	int begin;
	int times;
	Link head;
	Link newNode;
	
	while(scanf("%d%d",&begin,&times) != EOF)
	{
		createLink(&head);
	
		for(i = 1; i <= 20; i++)
		{
			newNode = (Link)malloc(sizeof(Node));
			if(newNode == NULL)
			{
				printf("malloc error!\n");
				exit(1);
			}
			
			newNode->num = i;
			
			tailInsert(&head,&newNode);
		}
		
		newNode->next = head;	
		
		procress(head,begin,times);
	}
	
	return 0;
}

发表于 2016-08-18 20:49:27 回复(0)

小刀初试

max(n)=10000，所以可以暴力循环，不需要快速判断跳出循环。

用bit的第1~20位作为兔子洞，1表示未被狼访问，0表示已经被狼访问。

当bit=0表示全部被访问，直接跳出循环。

#include <stdio.h>
int main(){
    for(int x,n,bit=(1<<21)-2;~scanf("%d%d",&x,&n);bit=(1<<21)-2){
        for(int i=2;bit&&n--;bit&=~(1<<(x==0?20:x)),x=(x+i++)%20);
        for(int i=1;bit && i<=20;++i){
            if (bit&(1<<i)) printf("%d ",i);
        }
        printf("%s\n",bit?"":"-1");
    }
    return 0;
}

编辑于 2016-08-13 17:57:39 回复(3)

牛客991536号

import java.util.Scanner;


public class RabbitHide {

	public static void main(String[] args) {
		Scanner input=new Scanner(System.in);
		while (input.hasNext()) {
			int x=input.nextInt();	//	从x开始找
			int n=input.nextInt();
			if (n>100000||x>20) {	//	找了n次
				continue;
			}
			int[] holes=new int[20];
			for (int i = 0; i < holes.length; i++) {
				holes[i]=0;
			}
			int i=0;
			while (n>0) {
				if (holes[(x+i)%20]==0) {
					holes[(x+i)%20]=1;
				}
				i++;
				n--;
				x=(x+i)%20;
			}
			int flag=0;	// 不可能藏着兔子
			for (int j = 1; j < holes.length; j++) {
				if (holes[j]==0) {
					flag=1;
					System.out.print((j)+" ");
				}
			}
			if (holes[0]==0) {
				flag=1;
				System.out.print("20 ");
			}
			if(flag==1){
				System.out.println();
			}else{
				System.out.println("-1");
			}
		}
	}
}

发表于 2016-08-04 09:31:22 回复(0)

奇吉木纳

#include<set>
#include<iostream>
using namespace std;

int main(){
    int x, n,interval,seq;
    set<int> iset;
    while (cin >> x >> n)
    {
        interval = 0;
        seq=x;
        while (n--){
            seq += interval;
            seq %= 20;
            iset.insert(seq);
            if (interval == 0)
                interval += 2;
            else
                interval++;
        }
        if(iset.size()==20){
             cout<<-1<<" ";
            break;
        }
        for (int i = 1; i <= 20; i++)
        {   seq=i%20;
            if (!iset.count(seq)){
                if(seq==0)
                    cout<<20<<" ";
                else
                    cout<<seq<<" ";
            }

        }
        cout<<endl;
        iset.clear();
    }
    return 0;
}

发表于 2016-05-16 22:38:29 回复(0)

披萨大叔

每组数据输出完毕后，别忘记输出换行符！！输出 换行符 ！！ 换行符 ！！

发表于 2016-09-06 11:20:45 回复(0)

Java

JustYoung

就说两点，找过的洞可以继续找，每一行最后得有一个空格。之前想复杂了，哎。。

import java.util.*;

public class Main {
    
	public static void find(int[] circle, int x, int n) {
		int step = 0;
		int current = x;
		while (n-- > 0) {
			int index = (current + step) % circle.length;
			circle[index] = 1;
			step += 1;
			current = (index + 1) % circle.length;
		}
	}

	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		while (scanner.hasNext()) {
			int x = scanner.nextInt();
			int n = scanner.nextInt();
			int[] circle = new int[20];
			find(circle, x - 1, n);
			boolean can = false;
			for (int i = 0; i < circle.length; ++i) {
				if (circle[i] != 1) {
					System.out.print(i + 1);
					System.out.print(" ");
					can = true;
				}
			}
			if (can) {
				System.out.println();
			} else {
				System.out.println("-1");
			}
		}
		scanner.close();
	}
    
}

发表于 2016-08-28 16:55:34 回复(0)

C/C++

NB响当当

这道题……只能说从题目上看的出这个公司的这次校招慢慢的不正规。出题人的问题表述能力很有问题。错别字就不提了，首先，第一个隔一个，第二次隔两个。然后呢？？我写了半天的的隔一个隔两个，再隔一个隔两个……就是不对……；然后就是末尾的空格，如果为了减轻测试判定的难度，那您就在题目中描述的清楚些，第一次说空格不对，我还是怀着猜测的态度误打误撞中了……吐槽完题目开始正式说下解题思路。

其实就是一个环链，然后按照要求进行填充即可。但是考虑到数据量，暴力破解是肯定不可能的，很容易超时。所以我们不妨看一下。当第一个环填充结束后，重新开始查洞。我们不难发现我出现这个洞上次看过了个情况，此时有两种情况：

1.再下一次的洞没有查过；

2.再下一次的洞同样查过了

因此，当第三次到达同样的洞穴时，下一次是一定查过的。举个例子，我们缩小测试集，假设洞穴为5，从头开始查起，找出所有情况。我们设dp[i]为第i个洞查看过的次数：

当到达3位置后，此洞以查询3次，当下次再次查询时，上述两种情况都已经遇见过，因此只能为上述的情况2的情况。因此，设置动态数组，然后按照要求进行计数，当查询次数耗完或者发现某个时刻所有的洞都查看过了或者有一个洞已经查看了3次，结束计数，统计动态数组中查看次数为0的对应索引即可。此算法在最坏的情况下需要查询60次数组，时间复杂度O(N)。参考代码如下：

#include <iostream>
#include <vector>
using namespace std;

int main(void)
{
    int x, n;
    while (cin >> x >> n)
    {
        vector<int> core(20, 0), res;
        int step = 1, find = x - 1, cont = 0;
        while (core[find] < 3 && cont < 20 && n--)
        {
            if (core[find] == 0) cont++;
            core[find]++;
            find = (find + ++step) % 20;
        }
        if (cont < 20)
        {
            for (int i = 1; i <= core.size(); i++)
            {
                if (core[i - 1] == 0)
                    cout << i << " ";
            }
        }
        else
            cout << -1 << " ";
        cout << endl;
    }
    return 0;
}

发表于 2018-05-17 12:30:34 回复(0)