Churu Criteria for stability of Imaginary Gases
All submissions for this problem are available.
For Idea gases, we have Ideal Gas equation. For real gases, we have Vander-Waals Equation. Inspired from these, nowadays, Churu is doing research on Imaginary Gases and found many interesting equations and criteria for Imaginary Gases.
He performs all the experiments in his lab, which can be represented as a cuboid of dimension - X x Y x Z . Co-ordinate system is standard 3-dimentional Cartesian co-ordinate system. Co-ordinate of the (bottommost, leftmost, front) point is (0,0,0). As we move right X-cordinate increases. As we move up Z-cordinate increases. As we move away Y-cordinate increases. Moreover, he has recently published a paper on Imaginary gases, according to which Imaginary gases have the following properties -
- Imaginary Gases are made up of very tiny particles. It is quite safe to assume that they are point sized. That means it is possible to observe more than one particle at a point at the same time.
- These particles move randomly inside the container in which they are kept. The probability of finding a particular particle at any point inside the container is equal. Note that in this problem we will only focus on points with Integer co-ordinates.
- Mass of all gas particles is same, which is universal constant.
- Collision between these particles is perfectly elastic.
- Partcles are very rigid. That means they do not break while collision happens.
- These particles posses potential energy by virtue of C-field (C for Churu, just like Electric field or magnetic field, there is C-field).
- If value of C-field at a point is c0, then the potential energy of any Imaginary gas particle will be pe = Kc * c0 (Kc greater than 0). Where Kc is called Churu constant, is universal constant.
- If a container containes Ni gas particles, then total potential energy (Ptot) due to all the particles will be sum of the average potential energies due to all the individual particles.
- Total Energy of all those particles will be
E = Kk * Ptot(d - k).
Where d is a constant which will be given in the input. And k depends on the co-ordinates of the container, where it is kept ! Kk is universal constant. Kk is greater than 0.
- In this question, you will be given the dimensions of a cuboidal container (Lc x Bc x Hc ) containing Imaginary Gas. And a cuboidal region will also be given. You will need to find the most stable location for the container completely inside the given region.
- If we want to find the most stable location for the container inside the region (xmn, ymn, zmn) to (xmx, ymx, zmx) [Both inclusive], then
k = (xmn + ymn + zmn + xmx + ymx +zmx) / 6.0 .
Note that, (xmn ≤ xmx, ymn ≤ ymx, zmn ≤ zmx).
- A container containing Imaginary gas is more stable if it has less Total Energy. So, if such container is left to float in a region, then it will stop at a location where total energy is minimum. As we all know, this low-energy stability is seen many times in physics, so it follws here as well !
In this problem you will be given the dimension of the room (X, Y, Z ) and the dimension of the container (Lc, Bc, Hc ) and the constant d. You will also be given an integer, D. Also the value of C-field at all the points in Churu's lab will be given (Integer points). Then there will be several queries. Each query will be contaning three space separated integers, Xq, Yq and Zq . For each query you will need to find the best location for the container to be kept inside the cuboidal region - ( Xq, Yq, Zq ) to ( Xq + D - 1, Yq + D - 1, Zq + D - 1 ) [Both Inclusive]. By best location Churu means, location which is most stable. Formally, for each query you need to find co-ordinates of a point ( Xr, Yr, Zr ). such that if the container is kept such that its (xmn, ymn, zmn) coincides with this point, its total energy will be minimum. Note that container should be completely inside (touching the boudry is allowed) the allowed region - ( Xq, Yq, Zq ) to ( Xq + D - 1, Yq + D - 1, Zq + D - 1 ) [Both Inclusive]. Also note that container can only be translated and can't be rotated which means, Lc should be parallel to X-axis, Bc should be parallel to Y-axis and Hc should be parallel to Z-axis. You need to report ( Xr, Yr, Zr ). If there are many such points which give same stability then, report the one with least X co-ordinate. If there are still many then report the one with least Y. If there are still many, then report the one with least Z.
Since the dimension of the room can be large, value of C-field at all the points can not be given as input. However, value of C-field at Q particular points will be given. And Value of C-field at all other points will can be calculated by the formula -
Cx,y,z = (x * x + y * y + z * z + Num) % P at point (x, y, z).
Value of Num and P and Q will also be given in the input. Please note that this function is nothing special. It is just for avoiding huge Input size.
Container / Churu's lab can be thought as a grid (3 - dimensional). Example, X = 1, Y= 2, Z = 3, represents a grid containing 1 * 2 * 3 = 6 points. Also, since a gas particle can be seen anywhere in the container with equal probability, average potential energy will be equal to, assuming a gas particle at each point and sum the potential energies at all the points then divide by number of points inside the container.
Please note that we only consider points with integer cordinates in this problem everywhere. Whenever point is written anywhere, it means point with integer co-ordinates.
- First line of the input contains three space separated integers X, Y, Z , in order, denoting the dimension of Churu's lab.
- Next line contains three space separated integers Lc, Bc, Hc , in order, denoting the dimension of the container.
- Next line contains three space separated integers P , Q and Numrespectively. Q denotes number of points where value of C-field will be given as input. P and Num are as described in the problem statement.
- Next Q lines each contains 4 space separated integers, xi, yi, zi and Ci, in order. First three integers denote the co-ordinate of a point and last integer denotes the value of C-field at that point.
- Next line contains the value of the constant d. Note that this is not an integer! However, (d * 100) will be integer, which means there will be atmost 2 significant digits after the decimal point in decimal representation of d.
- Next line contains two space separated integers D and queries respectively. D is already described in the problem statement. Meaning of queries is that there will be queries queries.
- Next queries lines each contains three space separated integers Xq, Yq, Zq , in order as described in the problem statement. You can assume that these queries are valid, meaning, the region ( Xq, Yq, Zq ) to ( Xq + D - 1, Yq + D - 1, Zq + D - 1 ) lies inside the lab.
- Please note that input file size is less than 10 MB, but comparable in some files, so please be careful while reading input.
- For each query, output a single line containing three space separated integers, Xr, Yr, Zr , denoting the best place to keep the container so as to achieve lowest Total Energy.
- 1 ≤ X, Y, Z ≤ 107
- 1 ≤ X * Y * Z ≤ 107
- 1 ≤ Lc ≤ X
- 1 ≤ Bc ≤ Y
- 1 ≤ Hc ≤ Z
- 1 ≤ P, Num ≤ 109
- 0 ≤ Q, queries ≤ 3 * 105
- max(Lc, Hc, Hc) ≤ D ≤ min(X, Y, Z)
- 1 ≤ Ci ≤ 109
- 0 ≤ d * 100 ≤ 109
- 0 ≤ Xq < X
- 0 ≤ Yq < Y
- 0 ≤ Zq < Z
- 0 ≤ Xq + D ≤ X
- 0 ≤ Yq + D ≤ Y
- 0 ≤ Zq + D ≤ Z
Input: 3 2 1 1 1 1 1 6 1 0 0 0 1 1 0 0 2 2 0 0 3 0 1 0 4 1 1 0 5 2 1 0 6 100.12 1 2 0 0 0 2 1 0 Output: 0 0 0 2 1 0
|Time Limit:||7 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.5, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.