Problem A
Lights inside a 3D Grid
Input: Standard Input
Output: Standard Output
You are given a 3D
grid, which have dimensions N, M and P. Each of the M x
N x P cells has a light. Initially all lights are off. You will have K
turns. In each of the K turns,
-
You
will select a cell A randomly from the grid
-
You
will select a cell B randomly from the grid
-
Toggle
the states of all the bulbs bounded by cell A and cell B, ie make all the ON
lights OFF and make all the OFF lights ON which are bounded by A and B. To be
more clear, consider cell A is (x1, y1, z1) and cell B is (x2, y2, z2). Then
you have to toggle all the bulbs in grid cell (x, y, z) where
min(x1,x2)<=x<=max(x1,x2) , min(y1,y2)<=y<=max(y1,y2) and min(z1,
z2)<=z<=max(z1, z2).
How many bulbs are
expected to be ON after K turns?
Note:
-
A and B can be the same
cell.
Input
First line of the input is an integer T(T<101)
which denotes the number of test cases. Each of the next T lines
represents one test case by 4 integers N, M, P (0 < M, N, P < 101) and
K (0<=K<=10000) separated
by spaces.
Output
Output one line for each test cases
giving the expected number of ON lights. Up to 1E-6 error in your output will
be acceptable. Print the case number
followed by the output. Look at the
sample output for exact format.
Sample Input Output
for Sample Input
|
2 2 3 4 1 |
Case 1: 6.3750000000 Case 2: 9.0976562500 |
Problem Setter: Md. Arifuzzaman Arif
Special Thanks: Manzurur Rahman Khan