QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #411800 | #3791. Interesting Calculator | 23lpx | 0 | 0ms | 0kb | C++20 | 1.2kb | 2024-05-15 19:42:50 | 2024-05-15 19:42:51 |
answer
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e2+9;
int idx=1,a[10][N],st[N];
struct PII{
int x,cnt,sum;
};
void bfs(int X,int Y)
{
for(int i=1;i<=Y;i++)st[i]=1e9;
queue<PII>q;
q.push({X,0,0});
pair<int,int>ans;
ans={1e9,0};
while(q.size())
{
PII t=q.front();
q.pop();
if(t.x==Y)
{
if(t.sum<ans.first||(t.sum==ans.first&&t.cnt<ans.second))
{
ans={t.sum,t.cnt};
}
continue;
}
for(int o=1;o<=3;o++)
{
for(int i=0;i<=9;i++)
{
int yy=t.sum+a[o][i];
if(o==1)
{
int xx=t.x*10+i;
if(xx<=Y&&yy<st[xx])q.push({xx,t.cnt+1,yy}),st[xx]=yy;
}
else if(o==2)
{
int xx=t.x+i;
if(xx<=Y&&yy<st[xx])q.push({xx,t.cnt+1,yy}),st[xx]=yy;
}
else
{
int xx=t.x*i;
if(xx<=Y&&yy<st[xx])q.push({xx,t.cnt+1,yy}),st[xx]=yy;
}
}
}
}
printf("Case %lld: %lld %lld\n",idx++,ans.first,ans.second);
}
void solve(int x,int y)
{
for(int o=1;o<=3;o++)
for(int i=0;i<=9;i++)
{
cin>>a[o][i];
}
bfs(x,y);
}
signed main()
{
ios::sync_with_stdio(0);cin.tie(0);
int x,y;
while(cin>>x>>y)
{
solve(x,y);
}
}
详细
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...