Created
January 13, 2017 21:08
-
-
Save ss1h2a3tw/77230a157243e4f557427d9e90c5fbcf to your computer and use it in GitHub Desktop.
Codeforces 100800G
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| /* | |
| Codeforces 100800G | |
| United Kingdom and Ireland Subregional Contest 2015 pG | |
| 今天有學生想把錢花完並且喝到一定單位的酒精 | |
| 給你酒的種類和價格和單位酒精含量 | |
| 然後輸出可不可行 可行的話輸出方法 | |
| 思路 | |
| 因為酒精含量與價格其實可以乘上一個數就變成整數 | |
| 所以就便成了一個無限背包問題 | |
| 所以dp[價格][酒精含量] 刷一遍 大約10^6 即可AC | |
| */ | |
| #include <cstdio> | |
| #include <algorithm> | |
| bool can[1010][610]; | |
| int from[1010][610]; | |
| char name[8][30]; | |
| int str[8]; | |
| int val[8]; | |
| int cnt[8]; | |
| int m,u,d; | |
| int main (){ | |
| { | |
| int tm; | |
| scanf("%d",&tm); | |
| m+=tm*100; | |
| scanf(".%d",&tm); | |
| m+=tm; | |
| } | |
| { | |
| int tu; | |
| scanf("%d",&tu); | |
| u+=30*tu; | |
| scanf(".%d",&tu); | |
| u+=3*tu; | |
| } | |
| scanf("%d",&d); | |
| for(int i = 0 ; i< d ; i ++){ | |
| scanf("%s",name[i]); | |
| scanf("%d",str+i); | |
| str[i]*=30; | |
| int tmp; | |
| scanf(" 1/%d",&tmp); | |
| str[i]/=tmp; | |
| scanf("%d",&tmp); | |
| val[i]=tmp*100; | |
| scanf(".%d",&tmp); | |
| val[i]+=tmp; | |
| } | |
| can[0][0]=true; | |
| for(int i = 0 ; i <= m ; i ++){ | |
| for(int j = 0 ; j <= u ; j ++){ | |
| for(int k = 0 ; k < d && (!can[i][j]) ; k ++){ | |
| if(str[k] <= j && i>=val[k] ){ | |
| if(can[i-val[k]][j-str[k]]){ | |
| can[i][j]=true; | |
| from[i][j]=k; | |
| } | |
| } | |
| } | |
| } | |
| } | |
| if(can[m][u]){ | |
| int nowm=m,nowu=u; | |
| while(nowm!=0||nowu!=0){ | |
| int nowd=from[nowm][nowu]; | |
| cnt[nowd]++; | |
| nowm-=val[nowd]; | |
| nowu-=str[nowd]; | |
| } | |
| for(int i = 0 ; i < d ; i ++){ | |
| if(cnt[i])printf("%s %d\n",name[i],cnt[i]); | |
| } | |
| } | |
| else{ | |
| printf("IMPOSSIBLE\n"); | |
| } | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment