302320: CF447A. DZY Loves Hash

Memory Limit:256 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

DZY Loves Hash

题意翻译

题目描述 zyk正在学哈希,将某个数字通过取模运算,存储到相应位置。具体做法,设置一个存储位置长度p,对于一个数字xi,xi将存放在xi mod p 位置,如:p=3, xi=14,那么xi将存放在 14 mod 3 = 2的位置。 然而,这样的哈希肯定会存在冲突,比如p=3, x1=14经过哈希后要放在2位置, x2=5经过哈希后也要放在2位置,那么就存在冲突了。 现在给你整数p以及n,然后输入n个整数xi,如果第一个冲突的数字是xi,那么就输出i,然后结束。如果没有冲突,就输出-1。 输入 输入p, n 然后n行每行输入xi 输出 输出相应答案 样例输入 10 5 0 21 53 41 53 样例输出 4 提示 【样例说明】 41 mod 10 = 21 mod 10 【数据规模和约定】 2<= p, n <=300 0<= xi <= 10^9

题目描述

DZY has a hash table with $ p $ buckets, numbered from $ 0 $ to $ p-1 $ . He wants to insert $ n $ numbers, in the order they are given, into the hash table. For the $ i $ -th number $ x_{i} $ , DZY will put it into the bucket numbered $ h(x_{i}) $ , where $ h(x) $ is the hash function. In this problem we will assume, that $ h(x)=x mod p $ . Operation $ a mod b $ denotes taking a remainder after division $ a $ by $ b $ . However, each bucket can contain no more than one element. If DZY wants to insert an number into a bucket which is already filled, we say a "conflict" happens. Suppose the first conflict happens right after the $ i $ -th insertion, you should output $ i $ . If no conflict happens, just output -1.

输入输出格式

输入格式


The first line contains two integers, $ p $ and $ n $ $ (2<=p,n<=300) $ . Then $ n $ lines follow. The $ i $ -th of them contains an integer $ x_{i} $ $ (0<=x_{i}<=10^{9}) $ .

输出格式


Output a single integer — the answer to the problem.

输入输出样例

输入样例 #1

10 5
0
21
53
41
53

输出样例 #1

4

输入样例 #2

5 5
0
1
2
3
4

输出样例 #2

-1

Input

题意翻译

题目描述 zyk正在学哈希,将某个数字通过取模运算,存储到相应位置。具体做法,设置一个存储位置长度p,对于一个数字xi,xi将存放在xi mod p 位置,如:p=3, xi=14,那么xi将存放在 14 mod 3 = 2的位置。 然而,这样的哈希肯定会存在冲突,比如p=3, x1=14经过哈希后要放在2位置, x2=5经过哈希后也要放在2位置,那么就存在冲突了。 现在给你整数p以及n,然后输入n个整数xi,如果第一个冲突的数字是xi,那么就输出i,然后结束。如果没有冲突,就输出-1。 输入 输入p, n 然后n行每行输入xi 输出 输出相应答案 样例输入 10 5 0 21 53 41 53 样例输出 4 提示 【样例说明】 41 mod 10 = 21 mod 10 【数据规模和约定】 2<= p, n <=300 0<= xi <= 10^9

加入题单

上一题 下一题 算法标签: