QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #411831 | #3791. Interesting Calculator | 23lpx | 0 | 0ms | 0kb | C++20 | 1.4kb | 2024-05-15 20:20:01 | 2024-05-15 20:20:02 |
answer
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e6+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.sum>st[t.x])continue;
st[t.x]=t.sum;
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);
}
}
//1 100000
//100000 100000 100000 100000 100000 100000 100000 100000 100000 100000
//100000 100000 100000 100000 100000 100000 100000 100000 100000 100000
//100000 100000 100000 100000 100000 100000 100000 100000 100000 100000
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Time Limit Exceeded
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...