DS '19 Day 1 P1 - Arithmetic Square

View as PDF

Submit solution

Points: 15 (partial)
Time limit: 5.0s
Memory limit: 1G

Author:
Problem type

You are given a 3\times 3 grid which contains integers.

Some of the 9 elements in the grid will have a value already, and the remaining elements will be unspecified. Every element, including those which are unspecified, must be an integer from -1\ 000\ 000 to 1\ 000\ 000, inclusive.

Your task is to determine the number of ways to fill the grid so that each row, when read from left-to-right is an arithmetic sequence, and that each column, when read from the top-down, is an arithmetic sequence. There is guaranteed to be at least one way. As this number may be large, please output it modulo 10^9 + 7.

Two ways of filling the grid are distinct if there is some cell which contains a different number in each way of filling the grid.

Recall that an arithmetic sequence of length three is a sequence of integers of the form

\displaystyle a,a+d,a+2d

for integer values of a and d. Note that d may be any integer, including zero or a negative integer.

Input Specification

The input will be 3 lines long. Each line will have three space-separated values. Each given value will either be an integer in the range from -1\ 000 to 1\ 000, inclusive, or the symbol X. However, the unspecified values may be integers in the range from -1\ 000\ 000 to 1\ 000\ 000, inclusive.

For 10 of the 100 marks available, there will be 9 X symbols in the input.

For an additional 40 of the 100 marks available, there will be 8 X symbols in the input.

For an additional 40 of the 100 marks available, there will be 7 X symbols in the input.

For the final 10 of the 100 marks available, there will be 4 X symbols in the input.

Output Specification

Output a single integer, the number of valid ways to fill the grid taken modulo 10^9+7.

Sample Input 1

8 9 10
16 X 20
24 X 30

Sample Output 1

1

Sample Input 2

X 0 X
0 0 0
X 0 X

Sample Output 2

2000001

Comments

There are no comments at the moment.