NC15893. Dark♂游戏
描述
某一天夜晚，宇宙中一个名为star星球的行星遭受到了万年难得一遇的全球大停电，据居民说，是黑暗之神搞的鬼！每次他的到来都能够让全球感到恐慌，因为一旦回答不出他的问题，将永远置身于黑暗之中，而且，黑暗之神为了刁难所有的居民，竟然明确告诉他们，他会给出多少个关卡，必须有一个人站出来挑战，只有完全通过了，这个星球才能够恢复正常。
输入描述
首先输入一个T，代表有T个关卡
其次对于每一个关卡都有两个整数p和x。 (T<=100 , 0<p<1e15 , 0<x<100)
输出描述
对于任意一关，你都需要输出一个整数k。
如果无法找到k满足黑暗之神，那么请输出”impossible”
对于每一个k，你都需要输出k个符号，代表第i个数是正数还是负数，如果是正数，则输出’+’符号，反之输出’-’符号。如果存在多组答案，则输出符号最少的那一组。
示例1
输入:
2 5 3 3 3
输出:
3 +-- impossible
说明:
3^2-3^1-3^0=5C++14(g++5.4) 解法, 执行用时: 571ms, 内存消耗: 12496K, 提交时间: 2019-02-03 15:24:16
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int T, x, k;
ll p;
int fuckkkk[100];
int CNMBDSHABITI(ll p, int k) {
if (k == 1) {
if (p == 1) fuckkkk[k] = 1;
else if (p == -1) fuckkkk[k] = -1;
else return 0;
return 1;
}
ll t = 1;
for (int i = 0; i < k - 1; ++i) t *= x;
if (p >= 0) {
fuckkkk[k] = 1;
return CNMBDSHABITI(p - t, k - 1);
} else {
fuckkkk[k] = -1;
return CNMBDSHABITI(p + t, k - 1);
}
}
int main() {
scanf("%d", &T);
while (T--) {
scanf("%lld%d", &p, &x);
if (x == 1) {
printf("%d\n", p);
for (int i = 0; i < p; ++i) printf("+");
printf("\n");
continue;
}
k = 0;
ll t = 0, m = 1;
while (t < p) {k++;t += m;m *= x;}
memset(fuckkkk, 0, sizeof fuckkkk);
if (CNMBDSHABITI(p, k)) {
printf("%d\n", k);
for (int i = k; i; --i) printf("%c", fuckkkk[i] > 0 ? '+' : '-');
printf("\n");
}
else printf("impossible\n");
}
return 0;
}
C++11(clang++ 3.9) 解法, 执行用时: 240ms, 内存消耗: 12464K, 提交时间: 2018-05-13 16:38:08
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <cctype>
#include <vector>
#include <string>
using namespace std;
typedef long long ll;
char s[64], *sp;
bool calc_(ll p, ll x, ll mul) {
sp = s;
while(mul /= x)
if(p > 0)
*sp++ = '+', p -= mul;
else
*sp++ = '-', p += mul;
*sp = '\0';
return p == 0;
}
int main() {
int t;
scanf("%d", &t);
while(t--) {
ll p, x;
scanf("%lld%lld", &p, &x);
if(x == 1) {
printf("%lld\n", p);
for(int i = p; i--; )
putchar('+');
putchar('\n');
continue;
}
ll mul = 1;
while((mul *= x) <= p);
if(calc_(p - mul / x, x, mul / x) || calc_(p - mul, x, mul))
printf("%d\n+%s\n", (int)(sp - s + 1), s);
else
puts("impossible");
}
return 0;
}