## 2-D Permutations

View as PDF

Points: 10 (partial)
Time limit: 2.0s
Memory limit: 1G

Author:
Problem type

Edward spent the whole weekend brainstorming problems involving 2-D arrays. Unfortunately, they were all too hard, so he came up with this instead:

You are given integers, numbered from to . You would like to arrange these numbers into an array . The rows are numbered from to and the columns from to . Denote the number assigned to the -th cell from the top and the -th cell from the left . An arrangement is called valid if for all cells with , , and for all cells with , . You are also given queries. For each query, a number is given, and you must return the number of different cells can be placed in all valid arrangements.

#### Input Specification

The first line will contain three integers , , and , the dimensions of the array and the number of queries.

The next lines will each contain one integer , as specified in the problem statement.

#### Output Specification

Output lines, the -th line containing the number of different cells can be placed in all valid arrangements.

#### Sample Input 1

2 2 4
1
2
3
4

#### Sample Output 1

1
2
2
1

#### Explanation for Sample 1

The two valid arrangements are:

 1 2 3 4
 1 3 2 4

and can be placed in two different cells, while and can only be placed in one.

#### Sample Input 2

1 3 3
1
2
3

#### Sample Output 2

1
1
1

#### Explanation for Sample 2

The only valid arrangement is:

 1 2 3

Since there is only 1 valid arrangement, each number can only be placed in 1 unique cell.

#### Sample Input 3

5 5 1
18

#### Sample Output 3

11

#### Explanation for Sample 3

The following diagram shows the 11 possible cells can be placed in. Green cells denote possible cells, while red cells denote otherwise:

• commented on Dec. 31, 2020, 4:49 a.m. edited

i am certain that python is not being able to handle this, got all the answer correct but always TLE for part 3.

edit; it can, but only with pypy3 or pypy2

• commented on Aug. 14, 2020, 11:57 a.m.

Are all queries distinct?

• commented on Aug. 14, 2020, 12:35 p.m.

Not necessarily.