#1947821

Solution for 2305: Beautiful Currency by btk

Source Code Status Test Cases
    Policy: public     Reviewed: 21    
00.20 sec    40588 KB    35 lines     716 bytes    2016-08-02 16:23
#include<bits/stdc++.h>

using namespace std;

struct I{I(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout<<fixed<<setprecision(10);
}}init;

const int M=2*114514;
const double INF=M*100;
typedef vector<double> V;
typedef vector<V> VV;
double diff(double a,double b){
    return abs(a-b)/a;
}
int main(){
    int N;cin>>N;
    V a(N);for(auto &it:a)cin>>it;
    VV dp(N,V(M,INF));
    for(int i=1;i<M;i++)dp[0][i]=diff(a[0],i);
    for(int i=1;i<N;i++){
        for(int j=1;j<M;j++){
            for(int k=j;k<M;k+=j)
                dp[i][k]=min(dp[i][k],max(dp[i-1][j],diff(a[i],k)));
        }
    }
    double res=INF;
    for(auto &it:dp.back())res=min(res,it);
    cout<<res<<endl;
    return 0;
}


Compile Error Logs:
You are not authorized to see the message.

Status
Judge: 51/51 C++11 CPU: 00.20 sec Memory: 40588 KB Length: 716 B 2016-08-02 16:23 2016-08-02 16:23
Results for testcases
Case # Verdict CPU Time Memory In Out Case Name
Case #1: : Accepted 00.02 sec 9880 KB
Case #2: : Accepted 00.02 sec 10096 KB
Case #3: : Accepted 00.02 sec 10044 KB
Case #4: : Accepted 00.00 sec 6576 KB
Case #5: : Accepted 00.01 sec 8084 KB
Case #6: : Accepted 00.02 sec 9984 KB
Case #7: : Accepted 00.00 sec 6660 KB
Case #8: : Accepted 00.01 sec 8268 KB
Case #9: : Accepted 00.02 sec 9932 KB
Case #10: : Accepted 00.03 sec 11916 KB
Case #11: : Accepted 00.04 sec 13608 KB
Case #12: : Accepted 00.05 sec 15528 KB
Case #13: : Accepted 00.06 sec 17008 KB
Case #14: : Accepted 00.07 sec 18908 KB
Case #15: : Accepted 00.08 sec 20740 KB
Case #16: : Accepted 00.09 sec 22736 KB
Case #17: : Accepted 00.10 sec 24612 KB
Case #18: : Accepted 00.11 sec 26104 KB
Case #19: : Accepted 00.12 sec 28096 KB
Case #20: : Accepted 00.13 sec 29912 KB
Case #21: : Accepted 00.14 sec 31632 KB
Case #22: : Accepted 00.18 sec 33300 KB
Case #23: : Accepted 00.16 sec 35176 KB
Case #24: : Accepted 00.19 sec 36824 KB
Case #25: : Accepted 00.17 sec 38708 KB
Case #26: : Accepted 00.19 sec 40588 KB
Case #27: : Accepted 00.00 sec 6568 KB
Case #28: : Accepted 00.01 sec 8220 KB
Case #29: : Accepted 00.02 sec 9932 KB
Case #30: : Accepted 00.03 sec 11856 KB
Case #31: : Accepted 00.04 sec 13704 KB
Case #32: : Accepted 00.05 sec 15460 KB
Case #33: : Accepted 00.06 sec 17220 KB
Case #34: : Accepted 00.07 sec 18892 KB
Case #35: : Accepted 00.08 sec 20892 KB
Case #36: : Accepted 00.09 sec 22816 KB
Case #37: : Accepted 00.12 sec 24416 KB
Case #38: : Accepted 00.11 sec 26104 KB
Case #39: : Accepted 00.12 sec 28020 KB
Case #40: : Accepted 00.13 sec 29784 KB
Case #41: : Accepted 00.16 sec 31580 KB
Case #42: : Accepted 00.15 sec 33240 KB
Case #43: : Accepted 00.17 sec 35196 KB
Case #44: : Accepted 00.19 sec 36976 KB
Case #45: : Accepted 00.18 sec 38604 KB
Case #46: : Accepted 00.20 sec 40452 KB
Case #47: : Accepted 00.01 sec 8160 KB
Case #48: : Accepted 00.03 sec 11832 KB
Case #49: : Accepted 00.10 sec 35080 KB
Case #50: : Accepted 00.01 sec 8136 KB
Case #51: : Accepted 00.08 sec 22568 KB
< prev | / | next >  
 
Judge Input #  ( | ) Judge Output #  ( | )


Comments
 
 Under Construction.
 
Categories
 
 
Free Tags