結果
問題 | No.2426 Select Plus or Minus |
ユーザー |
|
提出日時 | 2023-08-18 22:15:38 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 3 ms / 2,000 ms |
コード長 | 1,837 bytes |
コンパイル時間 | 3,922 ms |
コンパイル使用メモリ | 197,976 KB |
最終ジャッジ日時 | 2025-02-16 10:14:15 |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 41 |
ソースコード
#include <iostream> #include <vector> #include <iomanip> #include <algorithm> #include <map> #include <cmath> #include <bitset> #include <string> #include <queue> #include <stack> #include <set> #include <tuple> #include <atcoder/all> #include <sstream> // std::stringstream #include <regex> #include <fstream> using namespace atcoder; using mint = modint998244353; //using mint = modint1000000007; using namespace std; using ll = long long; static const double pi = 3.141592653589793; const int INF = (1 << 29); const ll mod = 998244353; // ifstream ifs(""); ファイルはワークスペースのトップにおく template<class T> void print(T& a){cout<<a<<'\n';} const ll MAX = 1000000000000000000; int main() { ll n; cin >> n; string ans; priority_queue< pair<unsigned long long,string>, vector<pair<unsigned long long,string>>, greater<pair<unsigned long long,string>> > Q; Q.push({n,""}); string S; map<pair<ll,char>,bool> mp; while(!Q.empty()){ auto now = Q.top();Q.pop(); if(MAX<now.first) continue; if(10000<now.second.size()) continue; if(now.first==1){ ans = now.second; break; } if(now.first%2==0) { if(mp.find({now.first/2,'/'})!=mp.end()) continue; mp[{now.first/2,'/'}] = true; Q.push({now.first/2,now.second+'/'}); }else{ if(mp.find({3*now.first+1,'+'})!=mp.end()) continue; mp[{3*now.first+1,'+'}] = true; Q.push({3*now.first+1,now.second+'+'}); if(mp.find({3*now.first-1,'-'})!=mp.end()) continue; mp[{3*now.first-1,'-'}] = true; Q.push({3*now.first-1,now.second+'-'}); } } std::cout << ans.size() << endl; std::cout << ans << endl; }