POJ 3475 - Paper-, er, Transcript-Folding Game

http://poj.org/problem?id=3475

概要

縦横に半分に折りながら c * d の紙を a * b の封筒に入れるとき，必要な折る回数の最小値を答える．

制約

• 0 < a, b, c, d <= 2^31 - 1

解法

• a を折って c に，b を折って d に
• a を折って d に，b を折って c に

の二通りしかないので，それぞれ計算して小さいほうを答える．

 1 #include <iostream>
 2 using namespace std;
 3 
 4 int f(long long x, long long y)
 5 {
 6   int c = 0;
 7   while (y > x) {
 8     x *= 2LL;
 9     ++c;
10   }
11   return c;
12 }
13 
14 int main()
15 {
16   int a, b, c, d;
17   while (cin >> a >> b >> c >> d) {
18     cout << min(f(a, c) + f(b, d), f(b, c) + f(a, d)) << endl;
19   }
20   return 0;
21 }