SRM 585 Div1 250 TrafficCongestion

2013-07-20

16:37 |

高さ TH の完全二分木がある。適当な２頂点を選んで２点間のエッジを塗る。
１つのエッジは２回塗らないようにしたい。最低何回塗れば全エッジを塗れるか。
1≦TH≦1,000,000

とりあえず長いのということで一番左の葉から一番右の葉まで塗ってみるも、結局余る点がちらほら出る
分かりやすそうな塗り方ということで下から∧状に塗ってみる
(証明なしｗ)

accepted

class TrafficCongestion {
	public:
	int theMinCars(int TH) {
		ll ans = 1;
		REP(i, TH-1) ans = (2 * ans + (i%2==0 ? 1 : -1)) % 1000000007LL;
		return ans;
	}
};

↓ちなみに modulo の数をコピペしてもコンパイル通る（けど 0 か 1 しか返らない）のでややこしい。。

class TrafficCongestion {
	public:
	int theMinCars(int TH) {
		ll ans = 1;
		REP(i, TH-1) ans = (2 * ans + (i%2==0 ? 1 : -1)) % 1,000,000,007LL;
		return ans;
	}
};