問題
http://community.topcoder.com/stat?c=problem_statement&pm=12159&rd=15176
２つの色のレンガと、レンガの個数がそれぞれ与えられる。
レンガは違う色を交互にだけ積み重ねることができる。
このとき、とりうる高さの場合の数を求める。
解き方
いくつか例を出してみると、積み重ねたレンガの数が偶数のときは2通り存在し、
それ以外の場合は１通りしか存在しないことがわかる。
１）積み重ねたレンガが偶数のときの場合の数
２色のうち最小の数
２）レンガが奇数のときの場合の数
＜レンガの長さが違う時＞
レンガの数が２色とも同じ
その数×２
レンガの数が２色で異なる
少ない方×２＋１
＜レンガの長さが２色とも同じ時＞
レンガの数が２色とも同じ
その数
レンガの数が２色で異なる
少ない方＋１
コード
using namespace std;
#define FORE(i,d,e) for(int i=d;i<e;i++)
#define FOR(i,s,e) for (int i = int(s); i != int(e); i++)
#define FORIT(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ISEQ(c) (c).begin(), (c).end()
class TheBrickTowerEasyDivOne {
public: int find(int redCount, int redHeight, int blueCount, int blueHeight) {
int ret=min(blueCount,redCount)*2;
if(redHeight!=blueHeight)ret+=min(blueCount,redCount);
if(blueCount!=redCount)ret++;
return ret;
}
};
#define FORE(i,d,e) for(int i=d;i<e;i++)
#define FOR(i,s,e) for (int i = int(s); i != int(e); i++)
#define FORIT(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ISEQ(c) (c).begin(), (c).end()
class TheBrickTowerEasyDivOne {
public: int find(int redCount, int redHeight, int blueCount, int blueHeight) {
int ret=min(blueCount,redCount)*2;
if(redHeight!=blueHeight)ret+=min(blueCount,redCount);
if(blueCount!=redCount)ret++;
return ret;
}
};