大力dp练习

2016.04.13 13:32 Wed | 198次阅读 | 旧日oi | 固定链接 | 源码

SRM 498 DIV1 1000pt

先不考虑限制,那么就可以对两维分别搞,dp[i][j]表示跳i步调到j的方案数,前缀和优化一下可以做到O(n^2)。
然后令f[i][j]表示跳了i步跳到(j,j),每次只能跳bad集合中的长度,转移是O(50n^2)
然后容斥一下就好了。

// BEGIN CUT HERE

// END CUT HERE
#line 5 "FoxJumping.cpp"
#include <bits/stdc++.h>
using namespace std;
#define mod 10007
int f[1601][801],g[1601][801],dp[1601][801],sum[1601][801],c[1601][1601];
class FoxJumping
{
public:
    int getCount(int Tx, int Ty, int Mx, int My, int R, vector <int> bad)
    {
        f[0][0]=1;
        for(int i=0;i<=Tx;i++) sum[0][i]=1;
        for(int i=1;i<=R;i++)
        {
            for(int j=0;j<=Tx;j++)
                f[i][j]=(sum[i-1][j]-(j<=Mx?0:sum[i-1][j-Mx-1])+mod)%mod;
            sum[i][0]=f[i][0];
            for(int j=1;j<=Tx;j++) 
                sum[i][j]=(sum[i][j-1]+f[i][j])%mod;
        }
        g[0][0]=1;
        for(int i=0;i<=Ty;i++) sum[0][i]=1;
        for(int i=1;i<=R;i++)
        {
            for(int j=0;j<=Ty;j++)
                g[i][j]=(sum[i-1][j]-(j<=My?0:sum[i-1][j-My-1])+mod)%mod;
            sum[i][0]=g[i][0];
            for(int j=1;j<=Ty;j++) 
                sum[i][j]=(sum[i][j-1]+g[i][j])%mod;
        }
        sort(bad.begin(),bad.end());
        dp[0][0]=1;
        for(int i=1;i<=R;i++)
        for(int j=0;j<=min(Tx,Ty);j++)
        {   
            dp[i][j]=dp[i-1][j];
            for(int k=0;k<bad.size();k++)
            if(j>=bad[k]) dp[i][j]=(dp[i][j]+dp[i-1][j-bad[k]])%mod;
        }
        int ans=0;
        c[0][0]=1;
        for(int i=1;i<=R;i++)
        {
            c[i][0]=1;
            for(int j=1;j<=i;j++) 
            c[i][j]=(c[i-1][j-1]+c[i-1][j])%mod;
        }
        for(int i=0;i<=R;i++)
        for(int j=0;j<=min(Tx,Ty);j++)
        {
            int tmp=dp[i][j]*c[R][i]%mod*f[R-i][Tx-j]%mod*g[R-i][Ty-j]%mod;
            ans=(ans+((i&1)?mod-tmp:tmp))%mod;
        }
        return ans;
    }

// BEGIN CUT HERE
public:
    void run_test(int Case) { if ((Case == -1) || (Case == 0)) test_case_0(); if ((Case == -1) || (Case == 1)) test_case_1(); if ((Case == -1) || (Case == 2)) test_case_2(); if ((Case == -1) || (Case == 3)) test_case_3(); if ((Case == -1) || (Case == 4)) test_case_4(); if ((Case == -1) || (Case == 5)) test_case_5(); }
private:
    template <typename T> string print_array(const vector<T> &V) { ostringstream os; os << "{ "; for (typename vector<T>::const_iterator iter = V.begin(); iter != V.end(); ++iter) os << '\"' << *iter << "\","; os << " }"; return os.str(); }
    void verify_case(int Case, const int &Expected, const int &Received) { cerr << "Test Case #" << Case << "..."; if (Expected == Received) cerr << "PASSED" << endl; else { cerr << "FAILED" << endl; cerr << "\tExpected: \"" << Expected << '\"' << endl; cerr << "\tReceived: \"" << Received << '\"' << endl; } }
    void test_case_0() { int Arg0 = 2; int Arg1 = 2; int Arg2 = 1; int Arg3 = 1; int Arg4 = 2; int Arr5[] = {}; vector <int> Arg5(Arr5, Arr5 + (sizeof(Arr5) / sizeof(Arr5[0]))); int Arg6 = 1; verify_case(0, Arg6, getCount(Arg0, Arg1, Arg2, Arg3, Arg4, Arg5)); }
    void test_case_1() { int Arg0 = 2; int Arg1 = 2; int Arg2 = 1; int Arg3 = 1; int Arg4 = 3; int Arr5[] = {}; vector <int> Arg5(Arr5, Arr5 + (sizeof(Arr5) / sizeof(Arr5[0]))); int Arg6 = 6; verify_case(1, Arg6, getCount(Arg0, Arg1, Arg2, Arg3, Arg4, Arg5)); }
    void test_case_2() { int Arg0 = 10; int Arg1 = 10; int Arg2 = 10; int Arg3 = 10; int Arg4 = 1; int Arr5[] = {}; vector <int> Arg5(Arr5, Arr5 + (sizeof(Arr5) / sizeof(Arr5[0]))); int Arg6 = 1; verify_case(2, Arg6, getCount(Arg0, Arg1, Arg2, Arg3, Arg4, Arg5)); }
    void test_case_3() { int Arg0 = 10; int Arg1 = 10; int Arg2 = 10; int Arg3 = 10; int Arg4 = 1; int Arr5[] = {10}; vector <int> Arg5(Arr5, Arr5 + (sizeof(Arr5) / sizeof(Arr5[0]))); int Arg6 = 0; verify_case(3, Arg6, getCount(Arg0, Arg1, Arg2, Arg3, Arg4, Arg5)); }
    void test_case_4() { int Arg0 = 11; int Arg1 = 11; int Arg2 = 11; int Arg3 = 11; int Arg4 = 2; int Arr5[] = {10}; vector <int> Arg5(Arr5, Arr5 + (sizeof(Arr5) / sizeof(Arr5[0]))); int Arg6 = 140; verify_case(4, Arg6, getCount(Arg0, Arg1, Arg2, Arg3, Arg4, Arg5)); }
    void test_case_5() { int Arg0 = 123; int Arg1 = 456; int Arg2 = 70; int Arg3 = 80; int Arg4 = 90; int Arr5[] = {30, 40, 20, 10, 50}; vector <int> Arg5(Arr5, Arr5 + (sizeof(Arr5) / sizeof(Arr5[0]))); int Arg6 = 6723; verify_case(5, Arg6, getCount(Arg0, Arg1, Arg2, Arg3, Arg4, Arg5)); }

// END CUT HERE

};

// BEGIN CUT HERE
int main()
{
    FoxJumping ___test;
    ___test.run_test(-1);
    return 0;
}
// END CUT HERE

SRM 503 DIV1 500pt

考虑第i个点放在选择序列中第j个位置的贡献,此时概率是1/m
,对i和其它点的距离排个序,还有和城市的最近距离,然后按距离从小到大考虑每个点,如果这个点的位置在j之前,离i距离为dis,且离i距离小于dis的点位置全在j之后,那么此时的贡献就是由这个点到i的距离。这么扫一遍就行了。
复杂度O(n^3)

// BEGIN CUT HERE

// END CUT HERE
#line 5 "KingdomXCitiesandVillages.cpp"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
int n,m;
long double dis[55][105];
long double get_dis(ll x,ll y,ll xx,ll yy)
{
    return sqrt((x-xx)*(x-xx)+(y-yy)*(y-yy));
}
long double e[55],se[55];
long double calc(int id,int pos)
{
    if(pos==1||dis[id][m]<=dis[id][1]) return dis[id][m];
    long double tmp=1,ret=0;
    for(int i=1;i<=m-pos+1;i++)
    {
        if(dis[id][i]>dis[id][m]) 
        {
            ret+=tmp*dis[id][m];
            return ret;
        }
        ret+=(long double)(pos-1)/(m-i)*tmp*dis[id][i];
        tmp=tmp*(m-pos+1-i)/(m-i);
    }
    return ret;
}
class KingdomXCitiesandVillages
{
public:
    double determineLength(vector <int> cX, vector <int> cY, vector <int> vX, vector <int> vY)
    {
        n=cX.size();
        m=vX.size();
        for(int i=0;i<m;i++)
        {
            for(int j=0;j<m;j++) dis[i][j]=get_dis(vX[i],vY[i],vX[j],vY[j]);
            dis[i][m]=23333333333333333.0;
            for(int j=0;j<n;j++) dis[i][m]=min(dis[i][m],get_dis(vX[i],vY[i],cX[j],cY[j]));
        }
        for(int i=1;i<m;i++) se[i]=se[i-1]+1.0/(m-1);
        long double ans=0;
        for(int i=0;i<m;i++)
        {
            sort(dis[i],dis[i]+m);
            for(int j=1;j<=m;j++) 
                ans+=calc(i,j)/m;
        }   
        return (double)ans;
    }

// BEGIN CUT HERE
public:
    void run_test(int Case) { if ((Case == -1) || (Case == 0)) test_case_0(); if ((Case == -1) || (Case == 1)) test_case_1(); if ((Case == -1) || (Case == 2)) test_case_2(); }
private:
    template <typename T> string print_array(const vector<T> &V) { ostringstream os; os << "{ "; for (typename vector<T>::const_iterator iter = V.begin(); iter != V.end(); ++iter) os << '\"' << *iter << "\","; os << " }"; return os.str(); }
    void verify_case(int Case, const double &Expected, const double &Received) { cerr << "Test Case #" << Case << "..."; if (Expected == Received) cerr << "PASSED" << endl; else { cerr << "FAILED" << endl; cerr << "\tExpected: \"" << Expected << '\"' << endl; cerr << "\tReceived: \"" << Received << '\"' << endl; } }
    void test_case_0() 
    { 
    int Arr0[] = {0}; 
    vector <int> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); 
    int Arr1[] = {6}; 
    vector <int> Arg1(Arr1, Arr1 + (sizeof(Arr1) / sizeof(Arr1[0]))); 
    int Arr2[] = {2, 2, 7, 6, 5, 10, 4, 7, 6, 8, 5, 9, 3, 5, 6, 5, 0, 2, 9, 6, 0, 2, 7, 6, 0, 9, 0, 1, 4, 8, 1, 6, 3, 7, 9, 1, 4, 3, 3, 5, 1, 5, 5, 8, 8, 10, 3, 4, 7, 10}; 
    vector <int> Arg2(Arr2, Arr2 + (sizeof(Arr2) / sizeof(Arr2[0]))); 
    int Arr3[] = {10, 2, 7, 4, 1, 10, 2, 6, 7, 5, 10, 1, 9, 3, 3, 5, 4, 6, 5, 5, 1, 8, 5, 2, 10, 6, 5, 4, 3, 2, 3, 1, 6, 10, 7, 10, 0, 2, 4, 9, 9, 7, 0, 1, 7, 7, 0, 5, 0, 1}; 
    vector <int> Arg3(Arr3, Arr3 + (sizeof(Arr3) / sizeof(Arr3[0]))); 
    double Arg4 = 2.5; 
    verify_case(0, Arg4, determineLength(Arg0, Arg1, Arg2, Arg3)); 
    }
    void test_case_1() { int Arr0[] = {1, 4, 7, 10}; vector <int> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); int Arr1[] = {5, 5, 5, 5}; vector <int> Arg1(Arr1, Arr1 + (sizeof(Arr1) / sizeof(Arr1[0]))); int Arr2[] = {1, 4, 7, 10}; vector <int> Arg2(Arr2, Arr2 + (sizeof(Arr2) / sizeof(Arr2[0]))); int Arr3[] = {4, 4, 4, 4}; vector <int> Arg3(Arr3, Arr3 + (sizeof(Arr3) / sizeof(Arr3[0]))); double Arg4 = 4.0; verify_case(1, Arg4, determineLength(Arg0, Arg1, Arg2, Arg3)); }
    void test_case_2() { int Arr0[] = {1, 2, 3}; vector <int> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); int Arr1[] = {4, 4, 4}; vector <int> Arg1(Arr1, Arr1 + (sizeof(Arr1) / sizeof(Arr1[0]))); int Arr2[] = {4, 5, 6}; vector <int> Arg2(Arr2, Arr2 + (sizeof(Arr2) / sizeof(Arr2[0]))); int Arr3[] = {4, 4, 4}; vector <int> Arg3(Arr3, Arr3 + (sizeof(Arr3) / sizeof(Arr3[0]))); double Arg4 = 4.166666666666667; verify_case(2, Arg4, determineLength(Arg0, Arg1, Arg2, Arg3)); }

// END CUT HERE

};

// BEGIN CUT HERE
int main()
{
    KingdomXCitiesandVillages ___test;
    ___test.run_test(0);
    return 0;
}
// END CUT HERE

SRM 507 DIV1 900pt

朴素的dp:f[i][j][k][t]表示前i行,用了j,k,t个R,G,B的方案数,状态n^4,转移n^3,tle
我们对每个颜色分别做一遍,在处理R时,我们只需考虑G+B的值,最后只需要把方案乘一个c[G+B][G]
然后,我们令num[i][j]表示单独的一行,用i个G或者B,用j个R的方案数,这个可以预处理出来。
那么状态变成了n^3,转移变成了n^2。
预处理:f[i][j][k][t]表示一行有i层,最上层有j个点,用了k个另外两种颜色,用了t个当前颜色的方案数。
转移也是,枚举这一层用了什么,组合数搞一搞就行了。
预处理看似是n^6,实际上……O(跑得过),手测极限数据不超过1s

// BEGIN CUT HERE

// END CUT HERE
#line 5 "CubeBuilding.cpp"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define mod 1000000007
ll dp[26][51][26];
ll num[51][26],c[51][51];
ll f[26][26][51][26];
void pre(int x,int y,int n)
{
    c[0][0]=1;
    for(int i=1;i<=max(x,n);i++)
    {
        c[i][0]=1;
        for(int j=1;j<=i;j++)
        c[i][j]=(c[i-1][j]+c[i-1][j-1])%mod;
    }
    num[0][0]=1;
    f[0][n][0][0]=1;
    ll tmp;
    for(int i=0;i<y;i++)
    {
        for(int j=0;j<=n;j++)
        {
            for(int t=0;t<=x;t++)
            for(int k=0;k<=y;k++)
            if(tmp=f[i][j][t][k])
            {
                for(int t1=0;t1<=j&&t1+t<=x;t1++)
                for(int k1=1;k1+t1<=j&&k1+k<=y;k1++)
                    (f[i+1][t1+k1][t1+t][k1+k]+=tmp*c[t1+k1-1][t1]%mod*c[j][k1+t1])%=mod;
            }
        }
        for(int j=1;j<=n;j++)
        {
            for(int t=0;t<=x;t++)
            for(int k=0;k<=y;k++)
            if(tmp=f[i+1][j][t][k])
                (num[t][k]+=tmp)%=mod;
        }
    }
}
ll work(int x,int y,int n)
{
    memset(dp,0,sizeof(dp));
    dp[0][0][0]=1;ll tmp;
    for(int i=0;i<n;i++)
    for(int j=0;j<=x;j++)
    for(int k=0;k<=y;k++)
    if(tmp=dp[i][j][k])
    {
        for(int j1=0;j1+j<=x;j1++)
        for(int k1=0;k1+k<=y;k1++)
            (dp[i+1][j+j1][k+k1]+=tmp*num[j1][k1])%=mod;
    }
    return dp[n][x][y];
}
class CubeBuilding
{
public:
    int getCount(int R, int G, int B, int N)
    {
        pre(max(R+G,max(G+B,B+R)),max(R,max(G,B)),N);
        return (int)((work(R+G,B,N)*c[R+G][G]+work(R+B,G,N)*c[R+B][B]+work(B+G,R,N)*c[B+G][G])%mod);
    }

// BEGIN CUT HERE
public:
    void run_test(int Case) { if ((Case == -1) || (Case == 0)) test_case_0(); if ((Case == -1) || (Case == 1)) test_case_1(); if ((Case == -1) || (Case == 2)) test_case_2(); if ((Case == -1) || (Case == 3)) test_case_3(); }
private:
    template <typename T> string print_array(const vector<T> &V) { ostringstream os; os << "{ "; for (typename vector<T>::const_iterator iter = V.begin(); iter != V.end(); ++iter) os << '\"' << *iter << "\","; os << " }"; return os.str(); }
    void verify_case(int Case, const int &Expected, const int &Received) { cerr << "Test Case #" << Case << "..."; if (Expected == Received) cerr << "PASSED" << endl; else { cerr << "FAILED" << endl; cerr << "\tExpected: \"" << Expected << '\"' << endl; cerr << "\tReceived: \"" << Received << '\"' << endl; } }
    void test_case_0() { int Arg0 = 2; int Arg1 = 3; int Arg2 = 9; int Arg3 = 16; int Arg4 = 4; verify_case(0, Arg4, getCount(Arg0, Arg1, Arg2, Arg3)); }
    void test_case_1() { int Arg0 = 1; int Arg1 = 1; int Arg2 = 2; int Arg3 = 1; int Arg4 = 0; verify_case(1, Arg4, getCount(Arg0, Arg1, Arg2, Arg3)); }
    void test_case_2() { int Arg0 = 2; int Arg1 = 2; int Arg2 = 1; int Arg3 = 3; int Arg4 = 162; verify_case(2, Arg4, getCount(Arg0, Arg1, Arg2, Arg3)); }
    void test_case_3() { int Arg0 = 0; int Arg1 = 0; int Arg2 = 10; int Arg3 = 12; int Arg4 = 372185933; verify_case(3, Arg4, getCount(Arg0, Arg1, Arg2, Arg3)); }

// END CUT HERE

};

// BEGIN CUT HERE
int main()
{
    CubeBuilding ___test;
    ___test.run_test(0);
    return 0;
}
// END CUT HERE

SRM 510 DIV1 500pt

令f[x]表示x-x+blen-1中的lucky number,我们发现,如果x不是lucky number,那么f[x+1]>=f[x],所以我们不需要考虑f[x+1]。
令b[x]表示min(f[x],f[x+1],...f[x+jlen-blen]),观察也可发现,当x+jlen-blen+1不是lucky number时,b[x]>=b[x+1]。
综上,我们选择的jlen的起始位置只能是某个lucky number-blen+1,然后blen的选择方案只能是jlen的起始位置或某个lucky number+1.
复杂度n^2

int find(long long a, long long b, long long jlen, long long blen)
    {
        q[1]=4;q[t=2]=7;
        for(int i=1;i<=t;i++)
        {
            if(q[i]*10+4<=b) q[++t]=q[i]*10+4;
            if(q[i]*10+7<=b) q[++t]=q[i]*10+7;
            if(q[i]<=b&&q[i]>=a) st[++cnt]=q[i];
        }
        sort(st+1,st+cnt+1);
        for(int i=1;i<=cnt;i++)
        {
            A[i]=max(a,st[i]-blen+1);B[i]=st[i]+1;
            for(int j=i+1;j<=cnt;j++) 
            if(st[j]-st[i]<=blen) len[i]++;
        }
        int ans=0;
        for(int t=1,j=0,i=1;i<=cnt&&A[i]+jlen-1<=b;i++)
        {
            while(j<cnt&&B[j+1]<=A[i]+jlen-blen) j++;
            while(t<=cnt&&B[t]<A[i]) t++;
            int tmp=1e9,t1=0;
            for(int k=t;k<=j;k++) tmp=min(tmp,len[k]);
            for(int k=1;k<=cnt;k++)
            if(st[k]>=A[i]&&st[k]<=A[i]+blen-1) t1++;
            ans=max(ans,min(tmp,t1));
        }
        return ans;
    }
}

SRM 510 DIV1 1000pt

把N表示成a0+a1x+a2x^2...的形式,x就是进制数,a0,a1,a2...都小于x,那么,如果项数超过3,那么可选的x很少,不超过,300000,这部分直接暴力。
然后,考虑两项和一项的时候,考虑枚举每个系数,n以内的lucky number有2^17个左右,看起来枚举的复杂度是爆炸的,但是,因为有x>ai的限制条件,所以a2不会很大,a1也不会很大,枚举的总量也不会很大。
两项的时候是个一次函数,3项的时候是二次函数,直接解个方程就行了。

#include <bits/stdc++.h>
using namespace std;
#define ll long long
map<ll,bool> mp;
ll q[1<<20];
bool check(ll x,ll B)
{
    while(x) 
    {
        if(!mp[x%B]) return 0;
        x/=B;
    }
    return 1;
}
#define eps 1e-9
int have(long double a,long double b,long double c)
{
    ll tmp=sqrt(b*b-4*a*c);
    if(fabs((b*b-4*a*c)-(long double)tmp*tmp)>eps) return 0; 
    long double t1=(-b+sqrt(b*b-4*a*c))/(2*a);
    long double t2=(-b-sqrt(b*b-4*a*c))/(2*a);
    long double t3=max(max(a,b),c);
    return (t1>t3)+(t2>t3);
}
class TheLuckyBasesDivOne
{
public:
    long long find(long long n)
    {
        int t;
        q[1]=4;q[t=2]=7;
        for(int i=1;i<=t;i++)
        {
            mp[q[i]]=1;
            if(q[i]*10+4<=n) q[++t]=q[i]*10+4;
            if(q[i]*10+7<=n) q[++t]=q[i]*10+7;
        }
        if(mp[n]) return -1;
        ll ret=0;
        for(ll i=2;i*i*i<=n;i++)
        if(check(n,i)) ret++;
        sort(q+1,q+t+1);
        for(int i=1;q[i]*(q[i]+1)<=n&&i<=t;i++)
        {
            for(int j=1;j<=t&&q[j]+q[i]*(max(q[i],q[j])+1);j++)
            if((n-q[j])%q[i]==0)
            {
                ll tmp=(n-q[j])/q[i];
                if(tmp>max(q[i],q[j])) ret++;
            }
        }
        for(int i=1;i<=t;i++)
        {
            if(q[i]*(q[i]+1)*(q[i]+1)>n) break;
            for(int j=1;j<=t;j++)
            {
                if(q[i]*(q[j]+1)*(q[j]+1)+q[j]*(q[j]+1)>n) break;
                for(int k=1;k<=t;k++)
                {
                    if(q[i]*(q[k]+1)*(q[k]+1)+q[j]*(q[k]+1)>n) break;
                    ret+=have(q[i],q[j],q[k]-n);
                }
            }
        }
        return ret;
    }
}

SRM 515 DIV1 550pt

每个时刻只能来一个人,那么最多只有24人次来,考虑状压,dp[i][j][k]表示时刻i之后,剩余j把剑,已经来过的人的状态为k的最大期望花费。
乍一看是2^24乘24^2的,然而状压的那里,只出现一次的人是不用状压的,于是最多只需要压12位,这样复杂度就对了。
注意一个细节,第i个人第j次来的概率不是输入的e,而是e/(1-之前的概率之和)。
果然概率dp需要加强,虽然想出了状态然而转移的时候有个地方懵逼了,最后还是看了下题解……

#line 5 "NewItemShop.cpp"
#include <bits/stdc++.h>
using namespace std;
#define eps 1e-10
double dp[25][25][1<<12];
bool vis[25][25][1<<12];
int tot,cnt;
int id[25],v[25],pos[25],c[25];
double e[25];
struct node
{
    int t,v,id;double e;
    bool operator <(const node &a)const{
        return t<a.t;
    }
}b[1005];
double get_ans(int m,int t,int st)
{
    if(m==0||t==tot+1) return 0;
    if(vis[m][t][st]) return dp[m][t][st];
    vis[m][t][st]=1;
    if(id[pos[t]]!=-1)
    {
        if(st>>id[pos[t]]&1) return dp[m][t][st]=get_ans(m,t+1,st);
        dp[m][t][st]=(1.0-e[t])*get_ans(m,t+1,st);
        dp[m][t][st]+=e[t]*max(get_ans(m,t+1,st+(1<<id[pos[t]])),v[t]+get_ans(m-1,t+1,st+(1<<id[pos[t]])));
    }
    else
    {
        dp[m][t][st]=(1.0-e[t])*get_ans(m,t+1,st);
        dp[m][t][st]+=e[t]*max(get_ans(m,t+1,st),v[t]+get_ans(m-1,t+1,st));
    }
    return dp[m][t][st];
}
class NewItemShop
{
public:
    double getMaximum(int m, vector <string> str)
    {
        for(int i=0;i<str.size();i++)
        {
            int s=0,a,x;
            double tmp=1,c;
            for(;;)
            {
                sscanf(str[i].data()+s,"%d,%d,%lf",&a,&x,&c);c/=100;
                b[++tot].id=i;
                b[tot].t=a;
                b[tot].v=x;
                b[tot].e=c/tmp;
                tmp-=c;
                while(s<str[i].size()&&!isspace(*(str[i].data()+s))) s++;
                if(s==str[i].size()) break;s++;
            }
        }
        memset(id,-1,sizeof(id));
        sort(b+1,b+tot+1);
        for(int i=1;i<=tot;i++) 
        {
            c[pos[i]=b[i].id]++;
            if(c[pos[i]]>=2&&id[pos[i]]==-1) id[pos[i]]=cnt++;
            v[i]=b[i].v;e[i]=b[i].e;
        }
        return get_ans(m,1,0);
    }
}

SRM 517 DIV1 600pt

SRM 517 DIV1 900pt

SRM 519 DIV1 600pt

SRM 519 DIV1 900pt

SRM 520 DIV1 1000pt

SRM 521 DIV1 1000pt

SRM 522 DIV1 1050pt

SRM 648 DIV1 850pt

SRM 658 DIV1 650pt

TCO'10 Semifinal 1 950pt

TCO'10 Wildcard Round 500pt