NOI '13 P1 - Inner Product

View as PDF

Submit solution

Points: 20 (partial)
Time limit: 2.5s
Memory limit: 256M

Problem type
National Olympiad in Informatics, China, 2013

The inner product (a.k.a. dot product) of two d-dimensional vectors A = [a_{1}, a_{2}, \ldots, a_{d}] and B = [b_{1}, b_{2}, \ldots, b_{d}] is equal to the sum of products of their corresponding components. Specifically:

\displaystyle (A,B)=\sum_{i=1}^{d}a_ib_i=a_1b_1+a_2b_2+\cdots +a_db_d

Given n such d-dimensional vectors, x_{1}, \ldots, x_{n}, Little Meow-Meow would like to know if there exists two vectors whose inner product is a multiple of k. Please help her solve this problem.

Input Specification

The first line of input contains 3 positive integers n, d, and k, respectively representing the number of vectors, the number of dimensions, and the number of which a inner product could be a multiple.
The next n lines each contains d nonnegative integers. On the i-th of these lines, the j-th integer represents x_{i,j}, the j-th component of vector x_{i}.

Output Specification

Output two integers, separated by a space.
If there exists two vectors x_{p} and x_{q} whose inner product is an integer multiple of k, then output their indices p and q (p < q). If there are multiple answers, output any one of them.
If an answer does not exist, then output two -1's separated by a space.

Sample Input

3 5 2
1 0 1 0 1
1 1 0 1 0
0 1 0 1 1

Sample Output

2 3

Explanation

(x_{1}, x_{2}) = 1
(x_{1}, x_{3}) = 1
(x_{2}, x_{3}) = 2

Constraints

Test Case n d k x_{i,j}
1 2 20 2 \le 10
2 5 20 2 \le 10
3 10 20 3 \le 10
4 20 20 2 \le 100
5 50 20 3 \le 100
6 50 50 2 \le 1\,000
7 50 50 3 \le 3\,000\,000
8 80 80 2 \le 2\,000\,000
9 100 100 3 \le 3\,000\,000
10 500 100 3 \le 3\,000\,000
11 1\,000 100 2 \le 2\,000\,000
12 1\,000 100 3 \le 3\,000\,000
13 10\,000 100 2 < 10
14 10\,000 100 3 < 10
15 15\,000 100 2 < 10
16 18\,000 100 2 < 10
17 20\,000 100 2 < 10
18 50\,000 30 3 < 10
19 80\,000 30 3 < 10
20 100\,000 30 3 < 10

Problem translated to English by Alex.


Comments

There are no comments at the moment.