Codeforces Round #461 (Div. 2)
A - Cloning Toys
#include <iostream> using namespace std; int main(void) { int x, y; cin >> x >> y; int copy = y - 1; if(copy > x || (x - copy) % 2 != 0) { cout << "No" << endl; } else { cout << "Yes" << endl; } }
上のコード提出したけど速攻Hackされた.
(生活こわれる時間帯で頭まわらなかったからね, しょうがないね)
editorialによると,
x = (奇数), y = 0の場合誤って"Yes"になるのでダメ.
x = (偶数), y = 1の場合も"Yes"になってしまうのでダメ.
y = 0, 1については別に場合分けする必要がある.
#include <iostream> using namespace std; int main(void) { int x, y; cin >> x >> y; if(y == 0) { cout << "NO" << endl; return 0; } if(y == 1) { if(x == 0) { cout << "Yes" << endl; } else { cout << "No" << endl; } return 0; } int copy = y - 1; if(copy > x || (x - copy) % 2 != 0) { cout << "No" << endl; } else { cout << "Yes" << endl; } }
B - Magic Forest
n <= 2500で更に制約がかかるので3重for文で全探索しても大丈夫.
1 <= i <= j <= k <= nなのでjは i <= j <= n の範囲で探索.
3つの数が三角形の辺の長さにならないといけないので, (i + j) > kとなる.
よってkの最大値は(i + j - 1)とnの小さい方になるので, j <= k < min(i + j, n + 1).
i, j, kをbitsetにしてexorをとって0なら数える.
0 ⊕ 0 ⊕ 0 = 0なので上の方の桁は気にせず32bitとってよい.
#include <iostream> #include <bitset> #include <algorithm> #include <utility> using namespace std; int main(void) { int n; cin >> n; int count = 0; for(int i = 1; i <= n; i++) { for(int j = i; j <= n; j++) { for(int k = j; k < min(i + j, n + 1); k++) { bitset<32> a, b, c; a = (bitset<32>) i; b = (bitset<32>) j; c = (bitset<32>) k; a ^= b; a ^= c; if(a == 0) { count++; } } } } cout << count << endl; }