Topcoderの過去問 - A0Paper
今日すること
こんにちはふるてつです。
今日は Topcoder の過去問です。
問題について
今日の問題は A0Paper。
A3、A4 などお馴染みの用紙サイズを使った問題です。
引数で A1 が何枚、A2 が何枚 A3 が何枚と指定され、指定された用紙を組み合わせて、 A0 サイズの用紙1枚分が作れれば "Possible" を返します。
作れなければ "Impossible" を返すという問題です。
英語の原文はこちらです
Problem Statement
"Letter", "Legal", and "Tabloid" are examples of paper sizes. Both Letter and Legal are 8 and half inches wide, but while Legal has length 14 inches, Letter is 11 inches long. This means that 14 letters have the same total length as 11 legals. Unless, of course, by "Letter" we mean "Government Letter" or instead of "Legal" we want "Junior Legal". In the days of manual paper making, the length of 11 inches was quite practical, as it is reportedly about a quarter of "the average maximum stretch of an experienced vatman's arms". Luckily for you, this problem is about a much more systematic way of cutting paper: the A series.
The papers in the A series are numbered A0, A1, A2, and so on until infinity. A0 is the largest of these papers. The area of an A0 paper is exactly 1 square meter.
All paper sizes in the A series have the same aspect ratio. More precisely, the ratio between the longer side and the shorter side of any paper in the A series is exactly equal to the square root of 2.
For each i, the longer side of the A(i+1) paper is equal to the shorter side of the A(i) paper.
From the previous two definitions it follows that the A series has the following useful property: Whenever you take an A(i) paper and you cut it in half (using a cut that passes through the centers of its longer sides), you will get two pieces of an A(i+1) paper. In other words, A1 is one half of A0, A2 is one half of A1, and so on.
You are given a A. A[i] represents the number of papers of size A(i) you have in stock. For example, A[4] is the number of A4 papers you currently have.
You are not allowed to cut paper in any way. You can only connect papers (seamlessly and without any waste) by taping them together. The papers you connect this way must not overlap. Can you take some of the papers you have and assemble a paper of size A0? Return "Possible" if it can be done and "Impossible" otherwise.
Definition
Class: A0Paper
Method: canBuild
Parameters: int[]
Returns: String
Method signature: String canBuild(int[] A)
(be sure your method is public)
Limits
Time limit (s): 2.000
Memory limit (MB): 256
Notes
- The return value is case-sensitive. Make sure you return the string exactly as shown in the problem statement.
Constraints
- A will contain between 1 and 21 elements, inclusive.
- Each element of A will be between 0 and 220, inclusive.
Examples
0)
{0,3}
Returns: "Possible"
We have 0 pieces of A0 paper and 3 pieces of A1 paper. We can combine the two of the three A1 papers to get an A0.
1)
{0,1,2}
Returns: "Possible"
This time, we can combine two A2 papers to get a second A1. Afterwards, the two of A1s (the original one and the one we made from the two A2s) can be combined to obtain an A0.
2)
{0,0,0,0,15}
Returns: "Impossible"
An A0 paper can be assembled from 16 A4 papers, but here we only have 15.
3)
{2,0,0,0,0,0,0,3,2,0,0,5,0,3,0,0,1,0,0,0,5}
Returns: "Possible"
We already have two pieces of A0 paper, so we can just take one of them and we are done.
This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved.
わたしの解答
わたしの解答コードは下記になります。
用紙の組み合わせを総当たりでチェックするようにしました。
ちょうどA01枚分になったときにループを抜けます。
import java.math.BigDecimal;
import java.util.Arrays;
public class A0Paper {
private static final String MSG_POSSIBLE = "Possible";
private static final String MSG_IMPOSSIBLE = "Impossible";
public String canBuild(int[] A) {
System.out.println("A:" + Arrays.toString(A));
// 引数なし
if (A.length == 0) {
return MSG_IMPOSSIBLE;
}
// A0をすでに手にしている場合
if (A[0] > 0) {
System.out.println("A[0] > 0");
return MSG_POSSIBLE;
}
// 紙の総数を計算する
int combinationSumOfPapers = sumarizeCombinationsOfPapers(A);
System.out.println("sumOfPapers:" + combinationSumOfPapers);
// 計算用のバッファ
int[] buf = new int[A.length];
// 判定とインクリメント
for (int i = 0; i <= combinationSumOfPapers; i++) {
System.out.println("buf:" + Arrays.toString(buf));
if (isValid(buf)) {
System.out.println("Possible");
return MSG_POSSIBLE;
}
System.out.println("Invalid");
increment(A, buf);
}
System.out.println("impossible");
return MSG_IMPOSSIBLE;
}
/*
* 紙の組合せ総数を計算する。
*/
private int sumarizeCombinationsOfPapers(int[] A) {
int count = 1;
for (int i = 0; i < A.length; i++) {
count *= A[i] + 1;
System.out.println("A["+ i +"]:" + (A[i]));
System.out.println("count:" + count);
}
return count;
}
/*
* Papersがちょうど1枚分になるか判定する。
*/
private boolean isValid(int[] buf) {
BigDecimal count = BigDecimal.valueOf(0);
for (int i = 0; i < buf.length; i++) {
if (buf[i] > 0) {
count = count.add(BigDecimal.valueOf(Math.pow(2, -i) * buf[i]));
}
}
System.out.println("count:" + count);
if (BigDecimal.valueOf(1).compareTo(count) == 0) {
return true;
}
return false;
}
/*
* bufをインクリメントする。
*/
private void increment(int[] A, int[] buf) {
for (int i = buf.length - 1; i >= 0; i--) {
if (buf[i] < A[i]) {
buf[i]++;
return;
}
buf[i] = 0;
}
}
}
下はテストコードです。
import static org.hamcrest.CoreMatchers.*;
import static org.junit.Assert.*;
import org.junit.jupiter.api.Test;
import practice.A0Paper2;
class A0PaperTest extends A0Paper2 {
@Test
void testCanBuild_01() {
assertThat(canBuild(new int[] { 0, 3 }), is("Possible"));
}
@Test
void testCanBuild_02() {
assertThat(canBuild(new int[] { 0, 1, 2 }), is("Possible"));
}
@Test
void testCanBuild_03() {
assertThat(canBuild(new int[] { 0, 0, 0, 0, 15 }), is("Impossible"));
}
@Test
void testCanBuild_04() {
assertThat(canBuild(new int[] { 2, 0, 0, 0, 0, 0, 0, 3, 2, 0, 0, 5, 0, 3, 0, 0, 1, 0, 0, 0, 5 }),
is("Possible"));
}
}
今日の感想
今日の問題も難易度は低く「easy」でした。
今回もStream APIは使用していません（いま勉強中）
今日もいい頭の体操になりました。
ではまた。
