結果
| 問題 | No.2426 Select Plus or Minus |
| ユーザー |
 Manuel1024
|
| 提出日時 | 2023-08-18 23:18:37 |
| 言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 1,234 bytes |
| コンパイル時間 | 1,173 ms |
| コンパイル使用メモリ | 97,024 KB |
| 実行使用メモリ | 99,248 KB |
| 最終ジャッジ日時 | 2023-08-18 23:18:44 |
| 合計ジャッジ時間 | 6,162 ms |
|
ジャッジサーバーID （参考情報） |
judge11 / judge9 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 1 ms
8,756 KB |
| testcase_01 | AC | 1 ms
4,380 KB |
| testcase_02 | AC | 2 ms
4,380 KB |
| testcase_03 | AC | 2 ms
4,380 KB |
| testcase_04 | AC | 723 ms
99,248 KB |
| testcase_05 | TLE | - |
| testcase_06 | -- | - |
| testcase_07 | -- | - |
| testcase_08 | -- | - |
| testcase_09 | -- | - |
| testcase_10 | -- | - |
| testcase_11 | -- | - |
| testcase_12 | -- | - |
| testcase_13 | -- | - |
| testcase_14 | -- | - |
| testcase_15 | -- | - |
| testcase_16 | -- | - |
| testcase_17 | -- | - |
| testcase_18 | -- | - |
| testcase_19 | -- | - |
| testcase_20 | -- | - |
| testcase_21 | -- | - |
| testcase_22 | -- | - |
| testcase_23 | -- | - |
| testcase_24 | -- | - |
| testcase_25 | -- | - |
| testcase_26 | -- | - |
| testcase_27 | -- | - |
| testcase_28 | -- | - |
| testcase_29 | -- | - |
| testcase_30 | -- | - |
| testcase_31 | -- | - |
| testcase_32 | -- | - |
| testcase_33 | -- | - |
| testcase_34 | -- | - |
| testcase_35 | -- | - |
| testcase_36 | -- | - |
| testcase_37 | -- | - |
| testcase_38 | -- | - |
| testcase_39 | -- | - |
| testcase_40 | -- | - |
| testcase_41 | -- | - |
| testcase_42 | -- | - |
| testcase_43 | -- | - |
ソースコード
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <map>
#include <queue>
using namespace std;
using ll = long long;
using P = pair<int, int>;
int main(){
ll n; cin >> n;
map<ll, int> mem;
map<ll, ll> pre;
queue<ll> Q;
Q.emplace(n);
mem[n] = 0;
while(!Q.empty()){
ll cur = Q.front(); Q.pop();
if(cur == 1) break;
if(cur%2 == 0){
if(mem.count(cur/2) == 1) continue;
mem[cur/2] = mem[cur]+1;
pre[cur/2] = cur;
if(cur/2 == 1) break;
Q.emplace(cur/2);
}else{
for(auto &it: {cur*3+1, cur*3-1}){
if(1000000000000000000 < it) continue;
if(mem.count(it) == 1) continue;
mem[it] = mem[cur]+1;
pre[it] = cur;
if(it == 1) break;
Q.emplace(it);
}
}
}
string ans = "";
ll x = 1;
while(x != n){
ll p = pre[x];
if(x*2 == p) ans += "/";
else if(p*3+1 == x) ans += "+";
else ans += "-";
x = p;
}
reverse(ans.begin(), ans.end());
cout << ans.size() << endl;
cout << ans << endl;
return 0;
}