fork(5) download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. typedef long long LL;
  4. #define int LL
  5. LL power(int base , int expo)
  6. {
  7.     LL ret = 1, to = base;
  8.     while(expo)
  9.     {
  10.         if(expo&1)
  11.             ret = ret * to;
  12.         to = to * to;
  13.         expo/=2;
  14.     }
  15.     return ret;
  16. }
  17.  
  18.  
  19.  
  20. LL dp[66][2];
  21. pair  < int , int > pi[66][2];
  22. LL x[66][2];
  23. LL y[66][2];
  24.  
  25. LL ret( string A , string B)
  26. {
  27.     LL i , j ,k,l;
  28.     const LL INF = 20000000000000LL;
  29.     for(i=0;i<64;++i)
  30.         for(j=0;j<2;++j)
  31.             x[i][j]= y[i][j]=dp[i][j] =  INF;
  32.     dp[A.length()][1] = 0 ;
  33.     dp[A.length()][0] = 0 ;
  34.     for(i=A.length()-1;i>=0;--i)
  35.         for(j=0;j<2;++j)
  36.         {
  37.             for(k=0;k<10;++k)
  38.                 for(l=0;l<=(j?9:k);++l)
  39.                 {
  40.                     if(A[i]!='?' && A[i]-'0'!=k)continue;
  41.                     if(B[i]!='?' && B[i]-'0'!=l)continue;
  42.  
  43.                     if(dp[i][j] > dp[i+1][j ||(k>l)] + (k-l)*power(10,int(A.length())-1-i  ))
  44.                     {
  45.                             dp[i][j] = dp[i+1][j ||(k>l)] + (k-l)*power(10,int(A.length())-1-i  );
  46.                             pi[i][j] = {i+1,j ||(k>l)};
  47.                             x[i][j] = k;
  48.                             y[i][j] = l ;
  49.                     }
  50.                     else if(dp[i][j] == dp[i+1][j ||(k>l)] + (k-l)*power(10,int(A.length())-1-i  ))
  51.                     {
  52.                         string one = "";
  53.                         one+=char(x[i][j]+'0');
  54.                         one += char(y[i][j]+'0');
  55.                         string two ="";
  56.                         two+= char(k+'0');
  57.                         two += char(l+'0');
  58.                         if(two<one)
  59.                         {
  60.                             x[i][j] = k;
  61.                             y[i][j] = l;
  62.                         }
  63.                     }
  64.                 }
  65.         }
  66.     return dp[0][0];
  67. }
  68. LL ret2( string A , string B)
  69. {
  70.     LL i , j ,k , l  ;
  71.     const LL INF = 20000000000000LL;
  72.     for(i=0;i<64;++i)
  73.         for(j=0;j<2;++j)
  74.             x[i][j]= y[i][j]=dp[i][j] =  INF;
  75.     dp[A.length()][1] = 0 ;
  76.     dp[A.length()][0] = 0 ;
  77.     for(i=A.length()-1;i>=0;--i)
  78.         for(j=0;j<2;++j)
  79.         {
  80.             for(k=0;k<10;++k)
  81.                 for(l=0;l<=(j?9:k);++l)
  82.                     {
  83.                         if(A[i]!='?' && A[i]-'0'!=k)continue;
  84.                         if(B[i]!='?' && B[i]-'0'!=l)continue;
  85.                         if(dp[i][j] > dp[i+1][j ||(k>l)] + (k-l)*power(10,int(A.length())-1-i  ))
  86.                         {
  87.                             dp[i][j] = dp[i+1][j ||(k>l)] + (k-l)*power(10,int(A.length())-1-i  );
  88.                             pi[i][j] = {i+1,j ||(k>l)};
  89.                             x[i][j] = k;
  90.                             y[i][j] = l ;
  91.                         }
  92.                         else if(dp[i][j] == dp[i+1][j ||(k>l)] + (k-l)*power(10,int(A.length())-1-i  ))
  93.                         {
  94.                             string one = "";
  95.                             one+=char(x[i][j]+'0');
  96.                             one += char(y[i][j]+'0');
  97.                             string two ="";
  98.                             two+= char(k+'0');
  99.                             two += char(l+'0');
  100.                             reverse(one.begin(),one.end());
  101.                             reverse(two.begin(),two.end());
  102.                             if(two<one)
  103.                             {
  104.                                 x[i][j] = k;
  105.                                 y[i][j] = l;
  106.                             }
  107.                         }
  108.                     }
  109.         }
  110.     return dp[0][0];
  111. }
  112.  
  113.  
  114.  main()
  115. {
  116. //    freopen("B-small-attempt5.in","r+",stdin);
  117. //    freopen("out3.txt","w+",stdout);
  118.     int T   , i , e , j  ;
  119.     cin>>T;
  120.     for(e=0;e<T;++e)
  121.     {
  122.         int i ;
  123.         cout<<"Case #"<<e+1<<": ";
  124.         string A , B;
  125.         cin>>A>>B;
  126.  
  127.         LL foo = ret(A,B);
  128.         LL bar= ret2(B,A);
  129.  
  130.         assert(foo!=20000000000000LL || bar!=20000000000000LL);
  131.         if(foo<=bar)
  132.         {
  133.             ret(A,B);
  134.  
  135.             i = 0 , j = 0;
  136.             string o1="" , o2 = "";
  137.             for(;i!=A.length();++i)
  138.             {
  139.                 o1 = o1  + char(x[i][j]+'0');
  140.                 o2 = o2  + char(y[i][j]+'0');
  141.                 j = pi[i][j].second;
  142.             }
  143.             reverse(o1.begin(),o1.end());
  144.             reverse(o2.begin(),o2.end());
  145.             while(o1.size()<A.size())o1+='0';
  146.             while(o2.size()<A.size())o1+='0';
  147.             reverse(o1.begin(),o1.end());
  148.             reverse(o2.begin(),o2.end());
  149.             cout<<o1<<" "<<o2<<"\n";
  150.         }
  151.         else
  152.         {
  153.  
  154.             ret2(B,A);
  155.             i = 0 , j = 0;
  156.             string o1="" , o2 = "";
  157.             for(;i!=A.length();++i)
  158.             {
  159.                 o1 = o1  + char(x[i][j]+'0');
  160.                 o2 = o2  + char(y[i][j]+'0');
  161.                 j = pi[i][j].second;
  162.             }
  163.             reverse(o1.begin(),o1.end());
  164.             reverse(o2.begin(),o2.end());
  165.             while(o1.size()<A.size())o1+='0';
  166.             while(o2.size()<A.size())o1+='0';
  167.             reverse(o1.begin(),o1.end());
  168.             reverse(o2.begin(),o2.end());
  169.             cout<<o2<<" "<<o1<<"\n";
  170.         }
  171.     }
  172.     return 0;
  173. }
  174.  
Success #stdin #stdout 0s 3432KB
comments (?)
stdin
copy 
1
? ?
stdout
copy 
Case #1: 0 0
https://ideone.com/YOkGQB
language:
C++14 (gcc 8.3)
created:
8 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!