Problem Statement
Right before the day of the final exam, a teacher is busy coming up with a seating assignment for the venue. The seats in the exam venue are arranged as m rows, each containing n seats, i.e., an m by n grid. The total number of students is exactly the same as the total number of seats, so all the seats will be occupied.
The teacher's task is complicated by the fact that there are k students who are suspected cheaters. In order to prevent cheating, the teacher will not allow any two suspected cheaters to sit in adjacent seats. Two seats are adjacent if and only if they are in adjacent columns of the same row, or adjacent rows of the same column.
The teacher's method for assigning the seats is simple. She finds a random seating assignment. Then, she checks if there are any suspected cheaters assigned to adjacent seats. If so, she repeats the process by finding another random assignment, and otherwise, she is done.
Your job is to determine the expected number of random seating assignments the teacher must generate before she finishes her task. Return this expected number as a String formatted "p/q" (quotes for clarity only), where p and q are relatively prime positive integers with no leading zeros. If there is no valid seating assignment, return "Impossible!" (quotes for clarity only).
Definition
- Class:
- SeatingPlan
- Method:
- expectedTrial
- Parameters:
- int, int, int
- Returns:
- String
- Method signature:
- String expectedTrial(int m, int n, int k)
- (be sure your method is public)
Constraints
- m will be between 1 and 80, inclusive.
- n will be between 1 and 80, inclusive.
- m*n will be less than or equal to 80.
- k will be between 0 and 20, inclusive, and less than or equal to m*n.
Examples
1
1
0
Returns: "1/1"
1
1
1
Returns: "1/1"
1
2
0
Returns: "1/1"
2
1
1
Returns: "1/1"
1
2
2
Returns: "Impossible!"
1
3
0
Returns: "1/1"
3
1
1
Returns: "1/1"
3
1
2
Returns: "3/1"
3
1
3
Returns: "Impossible!"
4
1
0
Returns: "1/1"
4
1
1
Returns: "1/1"
1
4
2
Returns: "2/1"
1
4
3
Returns: "Impossible!"
1
4
4
Returns: "Impossible!"
80
1
0
Returns: "1/1"
80
1
1
Returns: "1/1"
1
80
2
Returns: "40/39"
1
80
3
Returns: "1580/1463"
80
1
10
Returns: "20271005/5684749"
1
80
11
Returns: "1439241355/297231162"
80
1
19
Returns: "211129131824/779964483"
1
80
20
Returns: "6545003086544/11546031609"
2
2
0
Returns: "1/1"
2
2
1
Returns: "1/1"
2
2
2
Returns: "3/1"
2
2
3
Returns: "Impossible!"
2
2
4
Returns: "Impossible!"
2
3
0
Returns: "1/1"
Since there is no cheater, the teacher can finish the task with the first trial.
3
2
1
Returns: "1/1"
2
3
2
Returns: "15/8"
Let S represent a suspected cheater, and N a non-cheater. All possible acceptable seating plans: SNS SNN SNN NSN NSN NNS NNS NNN NNN NSN NNS SNN NNS SNN NSN SNS And all possible unacceptable seating plans: SSN NSS NNN NNN SNN NSN NNS NNN NNN SSN NSS SNN NSN NNS
3
2
3
Returns: "10/1"
2
3
4
Returns: "Impossible!"
3
2
5
Returns: "Impossible!"
2
3
6
Returns: "Impossible!"
2
4
3
Returns: "14/3"
4
2
4
Returns: "35/1"
3
3
2
Returns: "3/2"
3
3
4
Returns: "21/1"
4
4
2
Returns: "5/4"
4
4
3
Returns: "140/69"
4
4
4
Returns: "364/81"
4
4
7
Returns: "572/1"
1
79
17
Returns: "13353917587868/169252292811"
79
1
18
Returns: "580605112516/3899822415"
1
79
3
Returns: "1027/950"
2
40
2
Returns: "1580/1521"
40
2
1
Returns: "1/1"
2
40
0
Returns: "1/1"
2
40
12
Returns: "30123321560150/1718196876321"
40
2
18
Returns: "7722047996462800/5806958881047"
2
39
17
Returns: "1363576829755140/2035283779457"
3
24
12
Returns: "5121094767152/149421848643"
24
3
20
Returns: "2557779139540548/30379961477"
10
8
0
Returns: "1/1"
8
10
1
Returns: "1/1"
10
8
2
Returns: "1580/1509"
8
10
3
Returns: "4108/3573"
10
8
10
Returns: "823246055060/84792114361"
8
10
11
Returns: "2619419266100/157449204509"
8
10
15
Returns: "1658967454185140/5954036187321"
10
8
16
Returns: "26958221130508525/40109160071369"
10
8
18
Returns: "44401775979661100/9072201836281"
8
10
19
Returns: "289780011656735600/19550372084197"
8
10
20
Returns: "441914517776521790/9099256279121"
9
8
19
Returns: "29438590096598760/560890327267"
8
7
18
Returns: "70775996591300/172086661"
7
9
17
Returns: "337658324157945/17825492303"
7
6
16
Returns: "83254860801/77948"
6
8
15
Returns: "273315019836/10366429"
5
9
14
Returns: "166871334960/15062843"
9
4
13
Returns: "144424350/5429"
5
8
12
Returns: "5586853480/3130171"
4
5
20
Returns: "Impossible!"
5
8
20
Returns: "68923264410/1"
9
8
1
Returns: "1/1"
8
10
20
Returns: "441914517776521790/9099256279121"
10
8
20
Returns: "441914517776521790/9099256279121"
7
8
20
Returns: "392806781081715/28115278"
1
80
20
Returns: "6545003086544/11546031609"
7
11
15
Returns: "1175976929548960/3344320203781"
20
4
20
Returns: "3535316142212174320/112117346265581"
3
3
5
Returns: "126/1"