[NOI2013]向量内积

成绩 开启时间 2014年09月19日 星期五 10:07
折扣 0.8 折扣时间 2014年09月26日 星期五 10:07
允许迟交 关闭时间 2014年09月26日 星期五 10:07
输入文件 meow.in 输出文件 meow.out

【问题描述】

两个d维向量A=[a1,a2,…,ad]与B=[b1,b2,…,bd]的内积为其相对应维度的权值的乘积和,即:

(A,B)=sum(aibi)(1<=i<=d)=a1b1+a2b2+…+adbd
现有n个d维向量x1…,xn,小喵喵想知道是否存在两个向量的内积为k的倍数。请帮助她解决这个问题。

【输入格式】
输入文件meow.in的第一行包含3个正整数n,d,k,分别表示向量的个数,维数以及待检测的倍数。
接下来n行每行有d个非负整数,其中第i行的第j个整数表示向量xi的第j维权值xi,j

【输出格式】
输出文件meow.out包含两个整数,用空格隔开。
如果存在两个向量Xp,Xq的内积为k的整数倍,则输出两个向量的编号p与q(要求p<q)。如果存在多组这样的向量组合,输出其中任意一组即可。
若不存在这样的向量组合,则输出两个-1。

【样例输入】
3 5 2
1 0 1 0 1
1 1 0 1 0
0 1 0 1 1

【样例输出】
2 3

【样例说明】
(x1,x2)=1
(x1,x3)=1
(x2,x3)=2

【数据规模】

测试点编号 n d k xi,j
1 2 20 2 <=10
2 5 20 2 <=10
3 10 20 3 <=10
4 20 20 2 <=100
5 50 20 3 <=100
6 50 50 2 <=1000
7 50 50 3 <=3000000
8 80 80 2 <=2000000
9 100 100 3 <=3000000
10 500 100 3 <=3000000
11 1000 100 2 <=2000000
12 1000 100 3 <=3000000
13 10000 100 2 <=10
14 10000 100 3 <=10
15 15000 100 2 <=10
16 18000 100 2 <=10
17 20000 100 2 <=10
18 50000 30 3 <=10
19 80000 30 3 <=10
20 100000 30 3 <=10