QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #391902 | #3791. Interesting Calculator | ucup-team1251 | 0 | 0ms | 0kb | C++17 | 2.1kb | 2024-04-16 21:39:21 | 2024-04-16 21:39:22 |
answer
#include <bits/stdc++.h>
#define int long long
#define endl "\n"
using namespace std;
const int N = 1e6 + 10, mod = 1e9 + 7;
int a[11][111], st[11111];
struct node
{
int val, step, sum;
bool operator<(const node &b) const
{
if (val != b.val)
return val > b.val;
return step > b.step;
}
};
int n, m, ans, mns, mnv;
void bfs()
{
memset(st, 0, sizeof st);
mns = 30, mnv = ans;
priority_queue<node> p;
p.push({0ll, 0ll, n});
while (p.size())
{
node t = p.top();
p.pop();
if (st[t.sum])
continue;
st[t.sum] = 1;
if (t.sum == m)
{
if (mnv > t.val)
{
mnv = t.val;
mns = t.step;
}
if (mnv == t.val)
{
mns = min(mns, t.step);
}
}
int sum = 0;
for (int i = 1; i <= 3; i++)
{
for (int j = 0; j < 10; j++)
{
if (i == 1)
{
sum = t.sum * 10 + j;
}
if (i == 2)
{
sum = t.sum + j;
}
if (i == 3)
{
sum = t.sum * j;
}
if (sum <= m && st[sum] == 0 && (t.step + 1) <= mns && (t.val + a[i][j]) <= mnv)
{
p.push({t.val + a[i][j], t.step + 1, sum});
}
}
}
}
}
void solve()
{
int cnt = 1;
while (cin >> n >> m)
{
ans = 0;
memset(a, 0, sizeof(a));
for (int i = 1; i <= 3; i++)
{
for (int j = 0; j < 10; j++)
{
cin >> a[i][j];
ans = ans + a[i][j];
}
}
bfs();
cout << "Case " << cnt++ << ": " << mnv << " " << mns << '\n';
}
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int t = 1;
// scanf("%lld", &t);
// cin >> t;
while (t--)
{
solve();
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Runtime Error
input:
12 256 100 100 100 1 100 100 100 100 100 100 6 5 4 3 2 1 2 3 4 5 100 100 10 100 100 100 100 100 100 100 12 256 100 100 100 1 100 100 100 100 100 100 100 100 100 100 100 1 100 100 100 100 100 100 10 100 100 100 100 100 100 100 1 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 10...