ボックス(Box)
Box
Time limit: 3.000 seconds
Ivan works at a factory that produces heavy machinery. He hasa simple job -- he knocks up wooden boxes of different sizesto pack machinery for delivery to the customers. Each boxis a rectangular parallelepiped. Ivan uses six rectangular wooden palletsto make a box. Each pallet is used for one side of the box.
Joe delivers pallets for Ivan. Joe is not very smart andoften makes mistakes -- he brings Ivan pallets that do not fittogether to make a box. But Joe does not trust Ivan. It alwaystakes a lot of time to explain Joe that he has made a mistake.Fortunately, Joe adores everything related to computers and sincerelybelieves that computers never make mistakes. Ivan has decided touse this for his own advantage. Ivan asks you to writea program that given sizes of six rectangular palletstells whether it is possible to make a box out of them.
Input Input file contains several test cases. Each of them consists of six lines. Each line describes one pallet andcontains two integer numbers
w and
h (
1w,h10 000) --width and height of the pallet in millimeters respectively.
Output For each test case, print one output line. Write a single word ` POSSIBLE' to the output file if it is possibleto make a box using six given pallets for its sides. Write a single word` IMPOSSIBLE' if it is not possible to do so.
Sample Input
Sample Output
【分析】
長さと幅の異なる長方形を異なる配列に配置し、異なる長方形の数が3より大きい場合、残りの異なる長方形を同じ配列に配置します.具体的には、ソースコードを表示できます.1つの直方体については、最大3つの異なる矩形、すなわち3つの対向面が異なることができ、また、2つの同じ上下底面と4つの同じ側面からなることができ、また、6つの面が同じすなわち正方形であり、特殊な直方体である場合もある.まず4つの2次元配列を作成し、配列の第1行の第1列の値は矩形の幅を表し、第1行の第2列の値はこの矩形の高さを表す.同様に、第2行の第1列、第2列は第2矩形を表す......(高さ>幅)異なる矩形を異なる配列に保存する.1つの矩形が前の3つの配列内の矩形(前提:3つの配列内に矩形がある)と異なると仮定すると、4番目の配列に配置されます.実は、最初の3つの配列は直方体の向こうに保存されています.入力した6つの矩形を保存した後、4番目の配列に要素があるかどうかを判断し、1番目の配列に要素がある場合は、この6つの面が直方体を構成できないことを示します.(1つの直方体は最大3つの異なる矩形で構成されるため)現在の3つの配列のうち1つの配列内の要素の個数は奇数であり、同様に直方体を構成することはできない.(考えてみればなぜかわかる)(いずれも奇数でなければ、3つの配列要素の個数は以下の組み合わせがある可能性がある:[6,0,0],[2,2,2],[2,4,0],[4,2,0]であり、その他はない)次に、前の3つの配列内の要素個数を分類して議論する:1、最初の配列の要素個数が6である場合、6つの矩形が同じであることを説明し、直方体を構成することができる.2、配列要素の個数がいずれも2の場合.(異なるアスペクトを重複要素を含まない配列に加え、配列の要素個数を判断することによって条件に合致するか否かを分析し、要素個数が3の場合、3つの異なる面が存在し、3つの対面組成直方体を形成できることを示す)3、配列要素個数がそれぞれ2、4、0または4、2、0(この場合、直方体の上下地面はすべて正方形であり、正方形でなければ直方体を構成できない)
Java言語でプログラムを作成します.コードは次のとおりです.
Time limit: 3.000 seconds
Ivan works at a factory that produces heavy machinery. He hasa simple job -- he knocks up wooden boxes of different sizesto pack machinery for delivery to the customers. Each boxis a rectangular parallelepiped. Ivan uses six rectangular wooden palletsto make a box. Each pallet is used for one side of the box.
Joe delivers pallets for Ivan. Joe is not very smart andoften makes mistakes -- he brings Ivan pallets that do not fittogether to make a box. But Joe does not trust Ivan. It alwaystakes a lot of time to explain Joe that he has made a mistake.Fortunately, Joe adores everything related to computers and sincerelybelieves that computers never make mistakes. Ivan has decided touse this for his own advantage. Ivan asks you to writea program that given sizes of six rectangular palletstells whether it is possible to make a box out of them.
Input Input file contains several test cases. Each of them consists of six lines. Each line describes one pallet andcontains two integer numbers
w and
h (
1w,h10 000) --width and height of the pallet in millimeters respectively.
Output For each test case, print one output line. Write a single word ` POSSIBLE' to the output file if it is possibleto make a box using six given pallets for its sides. Write a single word` IMPOSSIBLE' if it is not possible to do so.
Sample Input
1345 2584
2584 683
2584 1345
683 1345
683 1345
2584 683
1234 4567
1234 4567
4567 4321
4322 4567
4321 1234
4321 1234
Sample Output
POSSIBLE
IMPOSSIBLE
【分析】
長さと幅の異なる長方形を異なる配列に配置し、異なる長方形の数が3より大きい場合、残りの異なる長方形を同じ配列に配置します.具体的には、ソースコードを表示できます.1つの直方体については、最大3つの異なる矩形、すなわち3つの対向面が異なることができ、また、2つの同じ上下底面と4つの同じ側面からなることができ、また、6つの面が同じすなわち正方形であり、特殊な直方体である場合もある.まず4つの2次元配列を作成し、配列の第1行の第1列の値は矩形の幅を表し、第1行の第2列の値はこの矩形の高さを表す.同様に、第2行の第1列、第2列は第2矩形を表す......(高さ>幅)異なる矩形を異なる配列に保存する.1つの矩形が前の3つの配列内の矩形(前提:3つの配列内に矩形がある)と異なると仮定すると、4番目の配列に配置されます.実は、最初の3つの配列は直方体の向こうに保存されています.入力した6つの矩形を保存した後、4番目の配列に要素があるかどうかを判断し、1番目の配列に要素がある場合は、この6つの面が直方体を構成できないことを示します.(1つの直方体は最大3つの異なる矩形で構成されるため)現在の3つの配列のうち1つの配列内の要素の個数は奇数であり、同様に直方体を構成することはできない.(考えてみればなぜかわかる)(いずれも奇数でなければ、3つの配列要素の個数は以下の組み合わせがある可能性がある:[6,0,0],[2,2,2],[2,4,0],[4,2,0]であり、その他はない)次に、前の3つの配列内の要素個数を分類して議論する:1、最初の配列の要素個数が6である場合、6つの矩形が同じであることを説明し、直方体を構成することができる.2、配列要素の個数がいずれも2の場合.(異なるアスペクトを重複要素を含まない配列に加え、配列の要素個数を判断することによって条件に合致するか否かを分析し、要素個数が3の場合、3つの異なる面が存在し、3つの対面組成直方体を形成できることを示す)3、配列要素個数がそれぞれ2、4、0または4、2、0(この場合、直方体の上下地面はすべて正方形であり、正方形でなければ直方体を構成できない)
Java言語でプログラムを作成します.コードは次のとおりです.
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
while(input.hasNext()) {
int[][] a = new int[6][2]; int a0 = 0;
int[][] b = new int[6][2]; int b0 = 0;
int[][] c = new int[6][2]; int c0 = 0;
int[][] d = new int[6][2]; int d0 = 0;
for(int i = 0; i < 6; i++) {
int w = input.nextInt();
int h = input.nextInt();
if(w > h) {
int t = w;
w = h;
h = t;
}
if(a0 == 0 || w == a[a0 - 1][0] && h == a[a0 - 1][1]) {
a[a0][0] = w;
a[a0][1] = h;
a0++;
}
else if(b0 == 0 || w == b[b0 - 1][0] && h == b[b0 - 1][1]) {
b[b0][0] = w;
b[b0][1] = h;
b0++;
}
else if(c0 == 0 || w == c[c0 - 1][0] && h == c[c0 - 1][1]) {
c[c0][0] = w;
c[c0][1] = h;
c0++;
}
else {
d[d0][0] = w;
d[d0][1] = h;
d0++;
}
}
if(d0 != 0 || a0 % 2 == 1 || b0 % 2 == 1 || c0 % 2 == 1)
System.out.println("IMPOSSIBLE");
else {
if(a0 == 6)
System.out.println("POSSIBLE");
else if(a0 == 2 && b0 == 2 && c0 == 2) {
if(a[0][0] == a[0][1] || b[0][0] == b[0][1] || c[0][0] == c[0][1])
System.out.println("IMPOSSIBLE");
else {
int[] e = new int[6];
int start = 0;
e[start++] = a[0][0];
if(a[0][1] != e[0])
e[start++] = a[0][1];
start = add(e, start, b[0][0]);
start = add(e, start, b[0][1]);
start = add(e, start, c[0][0]);
start = add(e, start, c[0][1]);
if(start == 3)
System.out.println("POSSIBLE");
else
System.out.println("IMPOSSIBLE");
}
} else if(a0 == 2 && b0 == 4) {
if(a[0][0] == a[0][1] && (a[0][0] == b[0][0] || a[0][0] == b[0][1]))
System.out.println("POSSIBLE");
else
System.out.println("IMPOSSIBLE");
} else if(a0 == 4 && b0 == 2) {
if(b[0][0] == b[0][1] && (b[0][0] == a[0][0] || b[0][0] == a[0][1]))
System.out.println("POSSIBLE");
else
System.out.println("IMPOSSIBLE");
}
else
System.out.println("IMPOSSIBLE");
}
}
}
public static int add(int[] e, int start, int temp) {
for(int x = 0; x < start; x++) {
if(temp == e[x])
return start;
}
e[start++] = temp;
return start;
}
}