SWEA 13240正方形フォント



これは看板のある横、縦および記録する字句であり、使用可能な最大文字数を求める問題である.
サイズが徐々に大きくなり、条件が合えば更新し、合わなければ終了します.
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class Solution {
	static BufferedReader br;
	static BufferedWriter bw;
	static StringTokenizer st;
	static int size = 0, H, W, N;
	static int[] str_length;

	static int calc() {
		size = 1;

		while (true) {
			boolean pass = true;
			
			int[] tmp = new int[H];
			for (int i = 0; i < H; i++) {
				tmp[i] = W;
			}
			int i = 0, j = 0;
			while (true) {
				if (W < str_length[j] * size) {
					pass = false;
					break;
				}
				if (tmp[i] >= str_length[j] * size) {
					tmp[i] -= ((str_length[j] + 1) * size);
					j++;
				} else {
					i++;
				}
				if (j == N) {
					break;
				}
				if ((i + 1) * size > H) {
					pass = false;
					break;
				}
			}
			if (!pass) {
				return size - 1;
			}
			size++;
		}
	}

	public static void main(String[] args) throws IOException {
		br = new BufferedReader(new InputStreamReader(System.in));
		bw = new BufferedWriter(new OutputStreamWriter(System.out));

		int T = Integer.parseInt(br.readLine());
		for (int test_case = 1; test_case <= T; test_case++) {
			st = new StringTokenizer(br.readLine(), " ");
			H = Integer.parseInt(st.nextToken());
			W = Integer.parseInt(st.nextToken());
			N = Integer.parseInt(st.nextToken());
			str_length = new int[N];
			if(N == 0 || H == 0 || W == 0) {
				bw.write(String.format("#%d 0\n", test_case));
				continue;
			}
			st = new StringTokenizer(br.readLine(), " ");
			for (int i = 0; i < N; i++) {
				str_length[i] = st.nextToken().length();
			}

			size = calc();
			
			bw.write(String.format("#%d %d\n", test_case, size));
		}
		bw.flush();
		bw.close();
	}
}