SRM639 div1 easy AliceGame
考えたこと
- 奇数の和は平方数なのでx+yが平方数でなければ不可能
- sqrt(x+y) でターン数は求められる
- できるだけ少ない個数の奇数の和で表したいので大きい奇数から貪欲に使っていけばいい気がした
- この貪欲でつくれない数が存在しない気がしたので出したら落ちた
- 2を異なる奇数の和で表すことができないので以下の二つで引っかかっていた
- 大きい数で引いた後 x=2 になるとき
- x = 2, y = 2
相変わらず嘘貪欲とかコーナーケースで落とし続けるのでいい加減止めたい…
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef vector<int> VI; typedef vector<VI> VVI; typedef vector<ll> VL; typedef vector<VL> VVL; typedef pair<int, int> PII; #define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i) #define REP(i, n) FOR(i, 0, n) #define ALL(x) x.begin(), x.end() #define IN(a, b, x) (a<=x&&x<b) #define MP make_pair #define PB push_back const int INF = (1LL<<30); const ll LLINF = (1LL<<60); const double PI = 3.14159265359; const double EPS = 1e-12; const int MOD = 1000000007; //#define int ll template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); } template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); } int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0}; class AliceGame { public: long long findMinimumValue(long long x, long long y) { ll sq = (ll)sqrt(x+y); if(sq*sq != x+y) { return -1; } if(x == 2 || y == 2) return -1; ll ret = 0; for(ll i=sq; i>=1; --i) { if(x >= i*2-1) { x -= i*2-1; ret++; } } if(x == 1) ret++; assert(x<=1); return ret; } };