QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#593906 | #6129. Magic Multiplication | KDream | AC ✓ | 7ms | 5540kb | C++17 | 2.6kb | 2024-09-27 16:48:23 | 2024-09-27 16:48:26 |
Judging History
answer
#include <bits/stdc++.h>
#define ll long long
using namespace std;
void solve()
{
int n ,m;
cin >> n >> m;
string s;
cin >> s;
int sz = s.size();
vector<vector<int>> ans (15),ans2(15);
vector<int> c(sz);
for (int i = 0;i < sz;i ++)
{
c[i] = s[i] - '0';
}
int idx = 0;
auto work = [&] (int x) -> bool
{
ans[x].push_back(x);
for (int i = 0;i < m;i ++)
{
if (idx < sz && c[idx] % x == 0 && c[idx] / x <= 9)
{
ans2[x].push_back((c[idx]) / x);
idx ++;
}
else if (idx + 1 < sz && (c[idx] * 10 + c[idx + 1]) % x == 0 && (c[idx] * 10 + c[idx + 1]) / x <= 9)
{
ans2[x].push_back((c[idx] * 10 + c[idx + 1]) / x);
idx += 2;
}
else
{
return false;
}
}
return true;
};
auto check = [&] (int x) -> bool
{
for (int i = 1;i < n;i ++)
{
if (idx < sz && c[idx] % ans2[x][0] == 0 && c[idx] / ans2[x][0] <= 9)
{
ans[x].push_back(c[idx] / ans2[x][0]);
idx ++;
}
else if (idx + 1 < sz && (c[idx] * 10 + c[idx + 1]) % ans2[x][0] == 0 && (c[idx] * 10 + c[idx + 1]) / ans2[x][0] <= 9)
{
ans[x].push_back((c[idx] * 10 + c[idx + 1]) / ans2[x][0]);
idx += 2;
}
else
{
return false;
}
for (int j = 1;j < m;j ++)
{
if (idx < sz && ans[x][i] * ans2[x][j] == c[idx])
{
idx ++;
}
else if (idx + 1 < sz && ans[x][i] * ans2[x][j] == (c[idx] * 10 + c[idx + 1]))
{
idx += 2;
}
else
{
return false;
}
}
}
return idx == sz;
};
for (int i = 1;i <= 9;i ++)
{
idx = 0;
if (work(i) && check(i))
{
for (auto j:ans[i])
{
cout << j;
}
cout << " ";
for (auto j:ans2[i])
{
cout << j;
}
cout << "\n";
return;
}
}
cout << "Impossible\n";
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int _ = 1;
cin >> _;
while (_--)
{
solve();
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3868kb
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: 0
Accepted
time: 7ms
memory: 5540kb
input:
1025 11 18 1461416814188088414188241035153540203545200202010354520510254921495628496328028281449632871435351535402035452002020103545205102500000000000000000000000000004000000063276372366381360363618638136918454921495628496328028281449632871435492149562849632802828144963287143514614168141880884141882...
output:
Impossible 3583 5 161650357972 65354104569 597523997017 7693 Impossible 406723924695110 973937089831524 59331138450754 554 4 189401911962950 980565699171 84748728972992 Impossible 62155650672 4241405 9458752764004792353 8717596993614 Impossible 941952596 49242258343771276739 Impossible 64053045751 4...
result:
ok 1025 lines