AOJ1028 ICPC: Ideal Coin Payment and Change
問題
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1028
前に各クエリに対してO(1)で返答する方法を考える問題だと思ってしまい病的な現象が起こってわからなくなったものを考え直す。
よくみたら、別にO(1)で処理しなくてもいいことがわかった。
#include<stdio.h> #include<algorithm> #include<vector> #include<queue> using namespace std; int main() { for(;;) { int pri,n1,n5,n10,n50,n100,n500; scanf("%d%d%d%d%d%d%d",&pri,&n1,&n5,&n10,&n50,&n100,&n500); if(pri==0) { break; } int mini=100000000; for(int i=pri;i<=pri+200;i++) { int mon=i; int u1,u5,u10,u50,u100,u500; u500=min(n500,mon/500); mon-=u500*500; u100=min(n100,mon/100); mon-=u100*100; u50=min(n50,mon/50); mon-=u50*50; u10=min(n10,mon/10); mon-=u10*10; u5=min(n5,mon/5); mon-=u5*5; u1=min(n1,mon/1); mon-=u1*1; int bil=(u500*500+u100*100+u50*50+u10*10+u5*5+u1*1)-pri; if(mon>0) { break; } int b1,b5,b10,b50,b100,b500; b500=bil/500; bil-=b500*500; b100=bil/100; bil-=b100*100; b50=bil/50; bil-=b50*50; b10=bil/10; bil-=b10*10; b5=bil/5; bil-=b5*5; b1=bil/1; bil-=b1*1; mini=min(mini,u1+u5+u10+u50+u100+u500+b1+b5+b10+b50+b100+b500); } printf("%d\n",mini); } }
ひどいソースだなぁ。
問題文でThe end of input is denoted by a case where P = 0. You should output nothing for this data set.ってかいてあるのにサンプルが"0 0 0 0 0 0 0"で終わってるとか悪質すぎだろ・・・(これのせいで無限ループに陥り謎TLEしていた)