結果
問題 | No.438 Cwwプログラミング入門 |
ユーザー |
![]() |
提出日時 | 2016-10-28 22:48:11 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 171 ms / 2,000 ms |
コード長 | 2,123 bytes |
コンパイル時間 | 1,983 ms |
コンパイル使用メモリ | 169,696 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-11-27 21:43:19 |
合計ジャッジ時間 | 13,061 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 98 |
ソースコード
#include "bits/stdc++.h" using namespace std; #define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i)) #define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i)) #define reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i)) static const int INF = 0x3f3f3f3f; static const long long INFL = 0x3f3f3f3f3f3f3f3fLL; typedef vector<int> vi; typedef pair<int, int> pii; typedef vector<pair<int, int> > vpii; typedef long long ll; template<typename T, typename U> static void amin(T &x, U y) { if(y < x) x = y; } template<typename T, typename U> static void amax(T &x, U y) { if(x < y) x = y; } int exgcd(int a, int b, int &g) { int u = 1, v = 0; while(b) { int t = a / b; a -= t * b; swap(a, b); u -= t * v; swap(u, v); } g = a; return u; } int main() { const int MaxLen = 10000; int x; int y; int z; while(~scanf("%d%d%d", &x, &y, &z)) { string ans; if(z == 0) { ans = "wwW"; goto ok; } rer(aa, -MaxLen / 2, MaxLen / 2) rer(bb, -MaxLen / 2, MaxLen / 2) { ll a = aa, b = bb; if(a <= 0 && b <= 0) continue; ll len = (abs(a) + abs(b)) * 2 - 1; if(len > MaxLen) continue; if((ll)a * x + (ll)b * y != z) continue; if(a > 0) { ans += 'c'; -- a; } else { ans += 'w'; -- b; } string ansL; while(a != 0 || b != 0) { if(a > 0) ans += "cC", -- a; else if(a < 0) ansL += 'c', ans += "W", ++ a; else if(b > 0) ans += "wC", -- b; else ansL += 'w', ans += "W", ++ b; } reverse(ansL.begin(), ansL.end()); ans = ansL + ans; assert(ans.size() == len); goto ok; } ok:; if(ans.empty()) { puts("mourennaihasimasenn"); } else { puts(ans.c_str()); /* vector<ll> stk; for(char c : ans) { if(c == 'c') stk.push_back(x); if(c == 'w') stk.push_back(y); if(c == 'C') { ll t = stk.end()[-1] + stk.end()[-2]; stk.pop_back(); stk.pop_back(); stk.push_back(t); } if(c == 'W') { ll t = stk.end()[-1] - stk.end()[-2]; stk.pop_back(); stk.pop_back(); stk.push_back(t); } } cerr << z << " = " << stk.back() << endl; */ } } return 0; }