Hdu 1203 I NEED A OFFER!

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <cstdlib>
 4 #include <cmath>
 5 #include <iostream>
 6 #include <map>
 7 #include <list>
 8 #include <queue>
 9 #include <stack>
10 #include <string>
11 #include <algorithm>
12 #include <iterator>
13 using namespace std;
14 #define MAXN 10010
15 #define INF 0x3f3f3f3f
16 #define MOD 1000000007
17 #define eps 1e-6
18 #define LL long long
19 double dp[MAXN];
20 int w[MAXN];
21 double v[MAXN];
22 int n , m;
23 void solve()
24 {
25     for(int i = 0; i < m; i ++)
26         scanf("%d %lf",&w[i] , &v[i]);
27     for(int i = 0; i <= n; i ++) dp[i] = 1;
28     for(int i = 0; i < m; i ++)
29         for(int j = n; j >= w[i]; j --)
30             dp[j] = min(dp[j] , dp[j - w[i]] * (1.0 - v[i]));    
31     printf("%.1lf%%\n",(1.0 - dp[n]) * 100);
32 }
33 
34 int main()
35 {
36     while(scanf("%d %d",&n,&m) && (n+m))
37     {
38         solve();
39     }
40     return 0;
41 }