fork(9) download
copy 
  1. #include<iostream>
  2. #include<cstdio>
  3. #include<algorithm>
  4. #include<memory.h>
  5. #include<vector>
  6. #include<stack>
  7. #include<queue>
  8. #include<cassert>
  9. #include<cstdlib>
  10. #include<cmath>
  11. #include<map>
  12. #include<cstring>
  13.  
  14. #define debug(x) cout<<#x<<"= "<<x<<endl
  15. #define mod(x) ((x)>0)?(x):(-(x))
  16. #define MAX(a,b) ((a)>(b))? (a):(b)
  17. #define MIN(a,b) ((a)<(b))? (a):(b)
  18. #define bit(n,i) (n&(1<<(i-1)))
  19. #define setbit(n,i) n |= (1<<(i-1))
  20. #define inf (1<<30)
  21. #define SETZERO(x) memset( x, 0, sizeof(x))
  22. #define SETMIN1(x) memset( x, -1, sizeof(x))
  23. #define CLEAR(x) while(!x.empty()) x.pop();
  24.  
  25. using namespace std;
  26. char a[1001],b[1001];
  27. int sa,sb;
  28. long long mf[1001][1001];
  29. long long MAXRET = (1ll<<31);
  30. long long f( int i, int j)
  31. {
  32.     if( i == sa || j == sb)
  33.         return 1;
  34.     long long &ret = mf[i][j];
  35.     if( ret >= 0)
  36.         return ret;
  37.     if( a[i] == b[j])
  38.     {
  39.         ret=f( i+1, j+1);
  40.     }
  41.     else
  42.     {
  43.         ret=f( i, j+1)+f( i+1, j);
  44.     }
  45.     if(ret>MAXRET) ret = MAXRET*2;
  46.     return ret;
  47. }
  48. void output( long long n, int i, int j)
  49. {
  50.     if( i == sa && j == sb)
  51.         return;
  52.     if( i == sa)
  53.         printf("%s", &b[j]);
  54.     else
  55.     if( j == sb)
  56.         printf("%s", &a[i]);
  57.     else
  58.     if( a[i] == b[j])
  59.         printf( "%c", a[i]),output( n, i+1, j+1);
  60.     else
  61.     if(a[i]<b[j]){
  62.         if( f( i+1, j) >= n)
  63.             printf( "%c", a[i]),output( n, i+1, j);
  64.         else
  65.             printf( "%c", b[j]),output( n-f(i+1,j), i, j+1);
  66.     }
  67.     else{
  68.         if( f( i, j+1) >= n)
  69.             printf( "%c", b[j]),output( n, i, j+1);
  70.         else
  71.             printf( "%c", a[i]),output( n-f(i,j+1), i+1, j);
  72.     }
  73. }
  74. int main()
  75. {
  76.     #ifndef ONLINE_JUDGE
  77.         freopen( "a.in", "r", stdin);
  78.         freopen( "a.out", "w", stdout);
  79.     #endif
  80.     int t;
  81.     scanf("%d",&t);
  82.     while(t--)
  83.     {
  84.         SETMIN1( mf);
  85.         long long n;
  86.         scanf( "%s\n%s", a, b);
  87.         sa = strlen(a);
  88.         sb = strlen(b);
  89.         cin >> n;
  90.         if( f(0,0) < n)
  91.         {
  92.             cout<<"NO ANSWER";
  93.         }
  94.         else
  95.         {
  96.             output( n, 0, 0);
  97.         }
  98.         cout<<"\n";
  99.     }
  100. }
  101.  
  102.  
  103.  
Success #stdin #stdout 0s 11168KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/z4p7OW
language:
C++ (gcc 8.3)
created:
11 years ago
visibility:
secret

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!