# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
742488 | irmuun | Brunhilda’s Birthday (BOI13_brunhilda) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define ll long long
#define ff first
#define ss second
#define all(s) s.begin(),s.end()
const int MAX=1e9;
int main(){
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
int m,q;
cin>>m>>q;
int p[m+5];
for(int i=1;i<=m;i++){
cin>>p[i];
}
sort(p+1,p+m+1);
if(q==1){
cin>>n;
int ans=0;
while(n>0){
int nxt=n;
for(int i=1;i<=m;i++){
nxt=min(nxt,n/p[i]*p[i]);
}
if(nxt==n){
cout<<"oo";
return 0;
}
ans++;
n=nxt;
}
cout<<ans;
return 0;
}
int ans[10005];
ans[0]=0;
for(int i=1;i<p[m];i++){
ans[i]=1;
}
for(int i=p[m];i<=10000;i++){
ans[i]=MAX;
for(int j=1;j<=m;j++){
ans[i]=min(ans[i],ans[i/p[j]*p[j]]+1);
}
}
while(q--){
int n;
cin>>n;
if(ans[n]==MAX){
cout<<"oo\n";
}
else{
cout<<ans[n]<<"\n";
}
}
}