NOI '13 P1 - Inner Product - DMOJ: Modern Online Judge

NOI '13 P1 - Inner Product

View as PDF

Submit solution

All submissions

Best submissions

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$ $d$ -dimensional vectors $A = [a_1, a_2, \dots, a_d]$ $A = [a_{1}, a_{2}, \dots, a_{d}]$ and $B = [b_1, b_2, \dots, b_d]$ $B = [b_{1}, b_{2}, \dots, b_{d}]$ is equal to the sum of products of their corresponding components. Specifically:

$\displaystyle (A,B) = \sum_{i=1}^d a_i b_i = a_1 b_1+a_2 b_2+\dots+a_d b_d$ $(A, B) = \sum_{i = 1}^{d} a_{i} b_{i} = a_{1} b_{1} + a_{2} b_{2} + \dots + a_{d} b_{d}$

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

Input Specification

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

Output Specification

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

Sample Input

Copy

Sample Output

Copy

2 3

Explanation

$(x_1, x_2) = 1$ $(x_{1}, x_{2}) = 1$
$(x_1, x_3) = 1$ $(x_{1}, x_{3}) = 1$
$(x_2, x_3) = 2$ $(x_{2}, x_{3}) = 2$

Constraints

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

Problem translated to English by Alex.

Comments

There are no comments at the moment.