Hatena::Grouptopcoder

hama_DU@TopCoderへの道

2011-08-06SRM300台を練習していく part8

SRM 321 Chocolate

|  SRM 321 Chocolate - hama_DU@TopCoderへの道 を含むブックマーク はてなブックマーク -  SRM 321 Chocolate - hama_DU@TopCoderへの道

http://www.topcoder.com/stat?c=problem_statement&pm=6598

長方形でない形には分割できないので、 x * y = nTiles となる形に分割できるかどうか考える。分割は高々2回。

x か y のどちらかが width もしくは height と等しければ分割は1回で済む。


public class Chocolate {

	public int minSplitNumber(int width, int height, int nTiles) {
		if (1L * width * height == (long)nTiles) {
			return 0;
		}
		
		int root = (int)Math.sqrt(nTiles);
		int mintry = 9999999;
		for (int x = 1 ; x <= root ; x++) {
			if (nTiles % x == 0) {
				int y = nTiles / x;
				if ((x < width && y < height) || (x < height && y < width)) {
					mintry = Math.min(mintry, 2);
				}
				if ((x == width && y < height) || (x == height && y < width)) {
					mintry = Math.min(mintry, 1);					
				}
				if ((x < width && y == height) || (x < height && y == width)) {
					mintry = Math.min(mintry, 1);					
				}
			}
		}
		
		if (mintry == 9999999) {
			mintry = -1;
		}
		return mintry;
	}

}