QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#222612 | #6129. Magic Multiplication | ucup-team1001 | TL | 0ms | 3780kb | C++20 | 2.2kb | 2023-10-21 17:47:53 | 2023-10-21 17:47:54 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define irep(i,l,r) for(int i = (l); (i) <= (r); ++ (i))
#define ll long long
inline ll read(){
ll s = 0;
bool w = 0;
char ch = getchar();
while(! isdigit(ch)){
if(ch == '-')w = 1;
ch = getchar();
}
while(isdigit(ch)){
s = (s << 3) + (s << 1) + (ch ^ 48), ch = getchar();
}
return w ? -s : s;
}
string s;
int len;
int n,m;
vector<int>A,B;
vector<int>AA,BB;
void work(){
if(AA.size())return;
A.resize(n);
string opt[10];
int optlen[10];
for(int c = 0; c < 10; ++ c){
for(int i = 0; i < m; ++ i){
int val = c * B[i];
if(val < 10)opt[c] += val + '0';
else opt[c] += (val / 10) + '0', opt[c] += (val % 10) + '0';
}
optlen[c] = opt[c].length();
}
int match = 0, pos = 0, ok = 0;
for(int i = 0; i < n; ++ i){
int pas = 0;
irep(ch, 0, 9){
int fl = 0;
if(pos + optlen[ch] > len)continue;
if(i == 0 && ch == 0)continue;
for(int p = 0; p < optlen[ch]; ++ p){
if(opt[ch][p] != s[pos + p]){
fl = 1;
break;
}
}
if(fl == 0){
pos = optlen[ch] + pos;
A[i] = ch;
fl = 1, pas = 1;
break;
}
}
if(i == n - 1 && pos != len)return;
if(pas == 0)return;
}
if(AA.size() == 0){
AA = A;
BB = B;
}
}
void dfs(int x, int a0, int cur){
if(cur >= len)return;
if(x == m){
if(B[0])work();
return;
}
int op1 = s[cur] - '0', op2 = (s[cur] - '0') * 10 + s[cur + 1] - '0';
if(op1 % a0 == 0){
B[x] = op1 / a0;
dfs(x + 1, a0, cur + 1);
}
if(op2 % a0 == 0 && op2 / a0 < 10 && op2 != 0){
B[x] = op2 / a0;
dfs(x + 1, a0, cur + 2);
}
}
void solve(){
n = read(), m = read();
A.resize(n);
B.resize(m);
AA.clear();
BB.clear();
cin >> s;
len = s.length();
if(1ll * n * m > s.length() || 2ll * n * m < s.length()){
puts("Impossible");
return;
}
A.push_back(0);
for(int a0 = 1; a0 < 10; ++ a0){
A[0] = a0;
B.resize(m);
dfs(0, a0, 0);
}
if(AA.size() == 0){
puts("Impossible");
return;
}else{
for(int x : AA)printf("%d", x);
putchar(' ');
for(int x : BB)printf("%d",x);
putchar('\n');
}
}
int main(){
int T = read();
while(T --){
solve();
}
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3780kb
input:
4 2 2 8101215 3 4 100000001000 2 2 80101215 3 4 1000000010000
output:
23 45 101 1000 Impossible Impossible
result:
ok 4 lines
Test #2:
score: -100
Time Limit Exceeded
input:
1025 11 18 1461416814188088414188241035153540203545200202010354520510254921495628496328028281449632871435351535402035452002020103545205102500000000000000000000000000004000000063276372366381360363618638136918454921495628496328028281449632871435492149562849632802828144963287143514614168141880884141882...
output:
Impossible 3583 5 161650357972 65354104569 597523997017 7693 Impossible 406723924695110 973937089831524 59331138450754 554 Impossible 980565699171 84748728972992 Impossible 62155650672 4241405 9458752764004792353 8717596993614 Impossible 941952596 49242258343771276739 Impossible 64053045751 41394875...