fork download
copy 
  1. #define _CRT_SECURE_NO_WARNINGS
  2. #include <iostream>
  3. using namespace std;
  4.  
  5. const double inf=12345678901234567890;
  6. const int nmax=555;
  7.  
  8. double dp[nmax][nmax][2], b[nmax], t[nmax], mint[nmax][nmax];
  9. double a, w, d, v;
  10. int n, ind[nmax], list[nmax], r, s[nmax][nmax][2][3];
  11. bool used[nmax][nmax][2];
  12.  
  13.  
  14. double min(double x, double y){return x<y?x:y;}
  15. void Solve(int i, int j, int k);
  16. double Time(double x, double y);
  17. void Update(double &oldv, double newv, int i, int j, int k, int i1, int j1, int k1);
  18.  
  19. int main()
  20. {
  21.    cin>>a>>w>>n;
  22.  
  23.    for(int i=1;i<=n;i++)
  24.    {
  25.       cin>>b[i]>>d>>v;
  26.       ind[i]=i;
  27.       b[i]-=a;
  28.       if(b[i]<0) b[i]+=360.0;
  29.       t[i]=(d-1.0)*60.0*(360.0*w);
  30.    }
  31.  
  32.    for(int i=1;i<=n;i++)
  33.       for(int j=i+1;j<=n;j++)
  34.          if(b[j]<b[i])
  35.          {
  36.             double c;
  37.             c=b[i], b[i]=b[j], b[j]=c;
  38.             c=t[i], t[i]=t[j], t[j]=c;
  39.             int q;
  40.             q=ind[i], ind[i]=ind[j], ind[j]=q;
  41.          }
  42.  
  43.    for(int i=1;i<=n;i++)
  44.       for(int j=i;j<=n;j++)
  45.       {
  46.          used[i][j][0]=used[i][j][1]=false;
  47.          mint[i][j]=t[i];
  48.          for(int k=i+1;k<=j;k++) mint[i][j]=min(mint[i][j], t[k]);
  49.       }
  50.  
  51.    for(int i=1;i<=n;i++)
  52.    {
  53.       Solve(i,i,0);
  54.       Solve(i,i,1);
  55.    }
  56.  
  57.    int i=1, j=1, k=0;
  58.    double ans=dp[1][1][0];
  59.    for(j=2;j<=n;j++)
  60.       if(ans>dp[j][j][0]) ans=dp[j][j][0], i=j;
  61.  
  62.  
  63.    if(ans==inf) cout<<"Impossible";
  64.    else
  65.    {
  66.       printf("%.5lf",ans/(v*(360.0*w)));
  67.       r=1, list[r]=ind[i], j=i;
  68.       while(i>1 || j<n)
  69.       {
  70.          int i1=s[i][j][k][0];
  71.          int j1=s[i][j][k][1];
  72.          int k1=s[i][j][k][2];
  73.          if(i1!=i) list[++r]=ind[i1];
  74.          else list[++r]=ind[j1];
  75.          i=i1, j=j1, k=k1;
  76.       }
  77.       for(int i=n;i>=1;i--) cout<<endl<<list[i];
  78.    }
  79.  
  80.    return 0;
  81. }
  82.  
  83.  
  84. void Solve(int i, int j, int k)
  85. {
  86.    if(i==1 && j==n)
  87.    {
  88.       dp[i][j][k]=inf, used[i][j][k]=true;
  89.       if(k==0)
  90.       {
  91.          if(Time(0,b[1])<=mint[1][n]) dp[i][j][k]=Time(0,b[1]);
  92.       }
  93.       else
  94.       {
  95.           if(Time(0,b[n])<=mint[1][n]) dp[i][j][k]=Time(0,b[n]);
  96.       }
  97.       return;
  98.    }
  99.    //1<i || j<n
  100.    if(k==0)
  101.    {
  102.       dp[i][j][k]=inf, used[i][j][k]=true;
  103.       if(i>1)
  104.       {
  105.          if(!used[i-1][j][0]) Solve(i-1,j,0);
  106.          if(dp[i-1][j][0]<inf && dp[i-1][j][0]+Time(b[i-1],b[i])<=mint[i][j])
  107.             Update(dp[i][j][k], dp[i-1][j][0]+Time(b[i-1],b[i]), i,j,k,i-1,j,0);
  108.       }
  109.       if(j<n)
  110.       {
  111.          if(!used[i][j+1][1]) Solve(i,j+1,1);
  112.          if(dp[i][j+1][1]<inf && dp[i][j+1][1]+Time(b[j+1],b[i])<=mint[i][j])
  113.             Update(dp[i][j][k], dp[i][j+1][1]+Time(b[j+1],b[i]), i,j,k,i,j+1,1);
  114.       }
  115.    }
  116.    else
  117.    {
  118.       dp[i][j][k]=inf, used[i][j][k]=true;
  119.       if(i>1)
  120.       {
  121.          if(!used[i-1][j][0]) Solve(i-1,j,0);
  122.          if(dp[i-1][j][0]<inf && dp[i-1][j][0]+Time(b[i-1],b[j])<=mint[i][j])
  123.             Update(dp[i][j][k], dp[i-1][j][0]+Time(b[i-1],b[j]), i,j,k,i-1,j,0);
  124.       }
  125.       if(j<n)
  126.       {
  127.          if(!used[i][j+1][1]) Solve(i,j+1,1);
  128.          if(dp[i][j+1][1]<inf && dp[i][j+1][1]+Time(b[j+1],b[j])<=mint[i][j])
  129.             Update(dp[i][j][k], dp[i][j+1][1]+Time(b[j+1],b[j]), i,j,k,i,j+1,1);
  130.       }
  131.    }
  132. }
  133.  
  134. double Time(double x, double y)
  135. {
  136.    if(x>y) return Time(y,x);
  137.    else return min(x+360.0-y,y-x)*v;
  138. }
  139.  
  140.  
  141. void Update(double &oldv, double newv, int i, int j, int k, int i1, int j1, int k1)
  142. {
  143.    if(oldv>newv) oldv=newv, s[i][j][k][0]=i1, s[i][j][k][1]=j1, s[i][j][k][2]=k1;
  144. }
Success #stdin #stdout 0s 4552KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
-nan
https://ideone.com/GPQRO8
language:
C++14 (gcc 8.3)
created:
6 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!