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)2010, TopCoder, Inc. All rights reserved.
$width \times height$個のタイルで構成されるチョコレートが与えられて，ここから$nTiles$個で構成されるチョコレートを作りたい．操作として板チョコを割るように任意の場所でチョコレートを分断することができる．最小何回でできるか．
長方形になっていなければならないので，$nTiles$の約数を長方形の高さとして決めると，幅も決まる．これが与えられるチョコレートから切り出せるを考える．チョコレートより長ければ切り出せず，同じ長さであれば切る必要がなく，短ければその場所で分断してあげれば良い．
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include <iostream>
#include <sstream>
#include <vector>
#include <string>
#include <cstring>
#include <algorithm>
#include <queue>
#include <map>
#include <set>
#define REP(i,k,n) for(int i=k;i<n;i++)
#define rep(i,n) for(int i=0;i<n;i++)
#define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)
#define INF 1<<30
#define mp make_pair
using namespace std ;
typedef long long ll ;
typedef pair < int , int > P ;
vector < ll > divisor ( ll n ) {
vector < ll > res ;
for ( ll i = 2 ; i * i <= n ; i ++ ) {
if ( n % i == 0 ) {
res . push_back ( i );
if ( i != n / i ) res . push_back ( n / i );
}
}
return res ;
}
class Chocolate {
public :
int minSplitNumber ( int width , int height , int nTiles ) {
int ans = INF ;
vector < ll > ret = divisor ( nTiles );
ret . push_back ( 1 );
ret . push_back ( nTiles );
rep ( i , ret . size ()) {
int h = ret [ i ];
int w = nTiles / h ;
if ( h > height || w > width ) continue ;
ans = min ( ans , ( h != height ) + ( w != width ));
}
if ( ans == INF ) return - 1 ;
else return ans ;
}
};