首页 > 试题广场 >

投篮游戏

[编程题]投篮游戏

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

有一个投篮游戏。球场有p个篮筐，编号为0，1...，p-1。每个篮筐下有个袋子，每个袋子最多装一个篮球。有n个篮球，每个球编号x_i 。规则是将数字为x_i 的篮球投到x_i 除p的余数为编号的袋里。若袋里已有篮球则球弹出游戏结束输出i，否则重复至所有球都投完。输出-1。问游戏最终的输出是什么？

输入描述:

第一行两个整数p,n（2≤p,n≤300)。p为篮筐数，n为篮球数。接着n行为篮球上的数字x_i(0≤xi≤1e9)

输出描述:

输出游戏的结果

示例1

输入

输出

算法知识视频讲解

静牛


	import java.util.*;



	public class Main{



	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		while (sc.hasNext()) {
            boolean success = true;
            int ind = -1;
			int p = sc.nextInt();//篮筐数
            int n = sc.nextInt();//篮球数
            //记录篮袋里是否已有篮球
            int[]book = new int[p];
            //记录篮球上的数字
            int[]x = new int[n];
            for(int i=0;i<n;i++){
                x[i] = sc.nextInt();
            }
            for(int i=0;i<n;i++){
                if(book[x[i]%p]==1){
                    success = false;
                    ind = i+1;
                    break;
                }
                else
                    book[x[i]%p] = 1;
            }
            System.out.println(ind);
        }
    }



	}

编辑于 2016-10-25 17:40:11 回复(3)

小新没有蜡笔~

最直观的做法就是使用一个哈希表存储已经投过的篮筐，但是大部分同学都是开辟一个数组来做哈希表

此处可以使用一个位图，因为n<=300，java中一个int占4字节，也就是32位，所以使用10个int就足以作为300的位置的哈希表。空间复杂度为O（10），即O（1）。而普通的用数组来作为哈希表的空间复杂度为O（n）。不懂的同学们可以了解一下位图

import java.util.Scanner;
public class Main{
    
    public static void main(String[] args){
		
		Scanner in=new Scanner(System.in);
		while(in.hasNext()){
			int p = in.nextInt();//篮筐数
            int n = in.nextInt();//篮球数
            int[] arr=new int[n];
            for(int i=0;i<n;i++){
				arr[i]=in.nextInt();
			}
			
			int[] flag=new int[10];//作为哈希表的数组
			int end=-1;
			for(int i=0;i<n;i++){
				int index=arr[i]%p;
				int row=index/32;
				int column=index%32;
				
				if((flag[row]&(1<<column))!=0){
					end=i+1;
					break;
				}else{
					flag[row]=flag[row]|(1<<column);
				}
			}
			System.out.println(end);
		}
		
	

 
    }
}

发表于 2017-08-09 11:41:25 回复(0)

pein531

很简单，直接模拟，一个数除以p的余数只可能是0~p-1，因此开一个大小为p的boolean数组来记录某个篮框是否已经进过球，没进过就将值修改为true，否则就结束投篮直接返回i。

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String line;
        while((line = br.readLine()) != null){
            String[] params = line.split(" ");
            int p = Integer.parseInt(params[0]);
            int n = Integer.parseInt(params[1]);
            boolean[] bag = new boolean[p];    // 除以p的余数只有可能是0~p-1
            int[] x = new int[n + 1];
            for(int i = 1; i <= n; i++) x[i] = Integer.parseInt(br.readLine());
            int i = 1;
            while(i <= n){
                if(bag[x[i] % p]) break;
                else bag[x[i] % p] = true;
                i++;
            }
            System.out.println(i > n? -1: i);
        }
    }
}

发表于 2021-04-11 12:14:57 回复(0)

C/C++

nbgao

#include <bits/stdc++.h>

using namespace std;

int main()
{     int p,n,x[310],c[310];     while(cin>>p>>n)     {         int result=-1;         memset(c,0,sizeof(c));         for(int i=0;i<n;i++)             cin>>x[i];         for(int i=0;i<n;i++)         {             if(c[x[i]%p]==1)             {                 result = i+1;                             break;                          }else                 c[x[i]%p]++;         }         cout<<result<<endl;                 }     return 0;
}

发表于 2017-11-25 01:54:08 回复(0)

zy在路上

#include<iostream>

using namespace std;

int main()

{

int p,n;

while(cin>>p>>n)

{

int b=0;

int a[301];

for(int i=0;i<n;i++)

{

cin>>a[i];

}

for(int j=0;j<n;j++)

{

a[j]=a[j]%p;

}

for(int i=1;i<n;i++) //从后往前遍历

{

for(int k=i;k>0;k--)

{

if(a[i]==a[k-1])

{

cout<<i+1<<endl;

b=1;

break;

}

if(b==1)

{

break;

}

if(b==0)

{

cout<<-1<<endl;

}

发表于 2017-07-15 17:11:10 回复(0)

C/C++

Bachelor、

#include<iostream>
#include<stdlib.h>
#include<math.h>
#include<stdio.h>

using namespace std;

int main()
{
int p = 0, n = 0;
while (cin >> p >> n)
{
  int flag = 0;
  int *score = new int[n];
  int *yu = new int[p];
  for (int i = 0; i < n; i++)
  {
   cin >> score[i];
  }
  for (int j = 0; j < n; j++)
  {
   if (yu[score[j] % p] != 1)
   {
    yu[score[j] % p] = 1;
   }
   else if (yu[score[j] % p] == 1)
   {
    cout << j + 1 << endl;
    flag = 1;
    break;
   }
  }
  if (flag == 0)
  {
   cout << "-1" << endl;
  }
}
system("pause");
return 0;
}

发表于 2017-07-12 16:56:58 回复(0)

蓝魔4

#include<iostream>
#include<vector>
using namespace std;
int main()
{
	int p,n;
	while(cin>>p>>n)
	{
		vector<bool> basket(p);
		vector<int> ball(n);
		for(int i=0;i<n;i++)
		{
			cin>>ball[i];
		}
		int num=-1;
		for(int i=0;i<n;i++)
		{
			if(!basket[ball[i]%p])
				basket[ball[i]%p]=1;
			else
			{
				num=i;
				break;
			}
		}
		if(num!=-1)
			cout<<num+1<<endl;
		else
			cout<<-1<<endl;
	}
	return 0;
}

编辑于 2017-07-04 16:51:14 回复(0)

C/C++

cycleof

#include<iostream>
using namespace std;
int main(){
    int p,n;
    while( cin >> p >> n){
        int a[301],b[301]={0},i,x;
        for(i=0;i<n;i++){
            cin >> a[i];
        }
        for(i=0;i<n;i++){
            x = a[i] % p;
            if(b[x]!= 1){
                b[x] = 1;
            }
            else{
                cout << i+1<<endl;
                break;
            }
        }
        if(i == n)
            cout << -1 <<endl;
    }
    return 0;
}

发表于 2017-06-21 18:23:58 回复(0)

Aurora1

while 1:
    try:
        s = raw_input()
    except:
        break
    p, n = map(int, s.split())
    d = [0] * p
    x, flag = -1, True
    for i in range(n):
        s = raw_input()
        if flag:
            j = int(s) % p
            if d[j]:
                x = i + 1
                flag = False
            d[j] = True
    print x

发表于 2017-05-04 12:19:43 回复(0)

Java

hello__bin

import java.util.*;
 
public class Main{
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        while(in.hasNext()){
            int end = -1;
            int p = in.nextInt();
            int n = in.nextInt();
            int[] x = new int[n];
            for(int i = 0;i < n;i++){
                x[i] = in.nextInt();
            }
            int[] judge = new int[p];
            
            for(int i = 0;i < n;i++){
                if(judge[x[i] % p] == 1){
                    end = i + 1;
                    break;
                }
                else
                judge[x[i] % p] = 1;
                          
            }
                System.out.println(end);
            }
        }
    }

此题要点是要标记已装球的袋子的状态，程序中我用‘0’代表未装，‘1’代表已装。每一次装球前都要做出判断，如果为0则继续重复操作，如果为1则返回球的位标（注意循环的时候是以0开始的，所以位标应该加1），然后退出循环。假设碰巧每次装的袋子都是空的，那么所有球都装完了就返回-1。

发表于 2017-03-27 21:01:11 回复(0)

牛客883929号

#include <iostream>

using namespace std;

int main(){

int p,n;

while(cin>>p>>n){

int *data = new int[p];

for(int i=0;i<p;i++){

data[i] = 0;

}

int result = -1;

int flag = 1;

for(int i=0;i<n;i++){

int num;

cin>>num;

data[num%p]++;

if(data[num%p]>1&&flag){

result = i;

flag = 0;

}

if(flag==1)

cout<<-1<<endl;

else

cout<<result+1<<endl;

delete[] data;

}

return 0;

}

发表于 2016-10-05 21:38:15 回复(0)

Alex-大伟

import java.util.Scanner;


public class Mugu4 {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner scanner = new Scanner(System.in);
		while(scanner.hasNext()){
			int p = scanner.nextInt();
			int n = scanner.nextInt();
			int[] x = new int[n];
			for (int i = 0; i < n; i++) {
				x[i] = scanner.nextInt();
			}
			System.out.println(getIndexOfBas(p, n, x));
		}
	}
	public static int getIndexOfBas(int p, int n, int[] x) {
		boolean[] hasBas = new boolean[p];
		for(int i=0;i<n;i++){
			int index = x[i] % p;
			if(!hasBas[index]){
				hasBas[index] = true;
			}
			else{
				return i+1;
			}
		}
		return -1;
	}
}

发表于 2016-09-28 09:24:29 回复(0)

Python

小三爷zZ

while True:
    try:
        p,n=map(int,raw_input().split())
        x=[]
        flag=-1
        for i in range(n):
            x.append(int(raw_input().split()[0]))
        xx=[i%p for i in x]
        if set(xx)==xx:
            flag=-1
        else:
            for j in range(1,n):
                if xx[j] in xx[:j]:
                    flag=j+1
                    break
        print flag
    except:
        break

编辑于 2016-08-20 20:35:03 回复(0)

谁是谁的眼

#include <stdio.h>

int main()
{
	int i;
	int j;
	int temp;
	int num[10];
	int basket;
	int flag = 0;
	int blankNum;
	int basketNum;
	int record = -1;
	
	while((scanf("%d%d",&blankNum,&basketNum) == 2))
	{
            int num[blankNum];
        
            for(i = 0; i < blankNum; i++)
            {
                num[i] = 0;
            }
        
		for(i = 0; i < basketNum; i++)
		{
			scanf("%d",&basket);
			temp = basket%blankNum;
			
			if(num[temp])
			{
				flag++;
				
				if(1 == flag)
				{
					record = i+1;
				}
			}
			else
			{
				num[temp] = 1;
			}
		}
		
		if(flag != 0)
		{
			printf("%d\n",record);
			flag = 0;
		}
		else
		{
			printf("-1\n");
		}
	}
	
	return 0;
}

发表于 2016-08-08 14:04:51 回复(0)

VinerL

#include <iostream>
#include <string>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <string.h>
#define REP(i,n) for(int i=0;i<(n);i++)
#define FOR(i,a,b) for(int i=(a);i<(b);i++)

#define MAXN 400
using namespace std;

int p,n;
int x[MAXN];
bool empty[MAXN];
int main(){
    ios::sync_with_stdio(0);
    while(cin>>p>>n){
        REP(i,n) cin>>x[i];
        memset(empty,0,sizeof(empty));
        int re=-1;
        REP(i,n) if(empty[x[i]%p]){re=i+1; break;}else empty[x[i]%p]=1;
        cout<<re<<endl;
    }
    return 0;  
}

发表于 2016-07-08 11:44:04 回复(1)

老石基

import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNext()) {//注意while处理多个case
            int p = in.nextInt();
            int n = in.nextInt();
            int[] x = new int[n];
            int[] a = new int[p];
            boolean flag = true;
            for(int i = 0;i<n;i++){
                x[i] = in.nextInt();
            }
            for(int i = 0;i<n&&flag;i++){
                int mod = x[i]%p;
                if(a[mod]==0){
                    a[mod] = 1;
                }else{
                    System.out.println(i+1);
                    flag = false;
                }
            }
            if(flag)
           	  System.out.println(-1);
        }
    }
}

发表于 2016-04-10 21:51:41 回复(0)

哈

1 /必须先输入完再判断否则超时

2 测试用例含有 127 0 输出-1

所以需要加判断if(n==0){//测试用例含有 127 0 输出-1

System.out.println(-1);

continue;

}


import java.util.*;
public class Main{
   public static void main(String[] args){
       Scanner sc=new Scanner(System.in);
       while(sc.hasNextInt()){
           int p=sc.nextInt();
           int n=sc.nextInt();
           if(n==0){//测试用例含有 127 0 输出-1
               System.out.println(-1);
               continue;
           }
           int[] basketball=new int[n];
           boolean[] bl=new boolean[p];
           for(int i=0;i<n;i++){//必须先输入完再判断 否则超时
               basketball[i]=sc.nextInt();
           }
           for(int i=0;i<n;i++){
        	   int x=basketball[i]%p;
               if(bl[x]==true){
                   System.out.println(i+1);
                   break;
               }
               bl[x]=true;
               if(i==n-1)
                   System.out.println(-1);
           }
           
       
   
       }
    
    
} 
    
}

发表于 2016-03-10 10:14:11 回复(2)

牛客271511号

用哈希表实现，感觉还是蛮清晰的
#include <iostream>
using namespace std;

int main()
{
    int p,n;

    while(cin>>p>>n){
        int *data=new int[n];
        int *hash_table=new int[p];
        int val=-1;

        for(size_t i=0;i<n;i++)
            cin>>data[i];

        for(size_t i=0;i<p;i++)
            hash_table[i]=0;

        for(size_t i=0;i<n;i++){
            hash_table[data[i]%p]++;
            if(hash_table[data[i]%p]>1){
                val=i;
                break;
            }
        }

        if(val!=-1)
            cout<<val+1<<endl;
        else
            cout<<-1<<endl;

        delete[] data;
        delete[] hash_table;
    }
}

发表于 2015-09-29 19:28:28 回复(0)

darren_wang

为什么都写得这么长，用集合来解感觉很简短。
这一题挺简单的，但是写之前看到了下面的评论给坑了，以为如果出现重复，
要在数据输入完成前就终止此次xi的接收，实际上不是的，必须完整地接收 n 个 x，最后再给出结果。
#include<iostream>
#include <set>
using namespace std;

int main() {
	int p, n; //篮筐数，篮球数
	int x, i;
	
	while(cin >> p >> n){
        int flag=0; //作用：1.判断是否有冲突 2.如果有冲突则记录第一个冲突的序号
	    set<int> myset; //每一批输入样例构造一个空集合
	    for(i=1; i<=n; i++){ //以1开始，便于这个题目处理
	        cin >> x;
	        if(myset.find(x%p)!=myset.end() && !flag) flag = i; //注意输入示例，只记录第一次冲突的，后面再有冲突的并不记录
	        else myset.insert(x%p);
	    }
        if(flag) cout << flag << endl; // 有冲突
        else cout << -1 << endl; // 没有冲突
	}
	return 0;
}

编辑于 2015-09-28 01:38:20 回复(4)

Zenas

// 题比较简单，看到有人说没通过测试，是因为原题是在ACM上考的，要使用ACM“风格”--main里的while大循环。
// 本人水手较低，代码写的不好，轻拍！

#include <iostream>
using namespace std;

int main(int argc, const char * argv[]) {
    // insert code here...
    int p, n, t, i;
    long x[300];
    while (cin >> p >> n) {
        if (p < 2 || n < 2 || p > 300 || n > 300) {
            cout << -1 << endl;
            continue;
        }
        int a[300] = {0};
        for (i = 0; i < n; i++) {
            cin >> x[i];
        }
        for (i = 0; i < n; i++) {
            t = x[i]%p;
            if (a[t] == 0)
                a[t] = 1;
            else {
                cout << i+1 << endl;
                break;
            }
        }
        if (i == n)
            cout << -1 << endl;
        
    }
    
    return 0;
}

发表于 2015-09-22 17:31:49 回复(1)