fork download
copy 
  1. #include <bits/stdc++.h>
  2. #pragma GCC optimize("O3,unroll-loops")
  3. #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
  4. #define ll long long
  5.  
  6.  
  7. using namespace std;
  8.  
  9. const int N = 5e5;
  10.  
  11. int n , m , k , PX;
  12.  
  13.  
  14. void init()
  15. {
  16.     ios_base::sync_with_stdio(0);
  17.     cin.tie(0);
  18.     cout.tie(0);
  19.     #define TASK "Sheep"
  20.     if(fopen(TASK".INP" , "r"))
  21.     {
  22.         freopen(TASK".INP" , "r" , stdin);
  23.         freopen(TASK".OUT" , "w" , stdout);
  24.     }
  25. }
  26.  
  27. void process()
  28. {
  29.     int res = 1;
  30.     if(n > m) swap(n , m);
  31.     while(m - m/2 > k)
  32.     {
  33.         k += n;
  34.         n += n;
  35.         res ++;
  36.     }
  37.     cout << res << '\n';
  38. }
  39.  
  40. void read()
  41. {
  42.     string a , b;
  43.     cin >> a >> b;
  44.     vector < vector < int > > dp(a.size() + 1 , vector < int > (b.size() + 1));
  45.     for(int i = 1 ; i <= a.size() ; i ++)
  46.         for(int j = 1 ; j <= b.size() ; j ++)
  47.             if(a[i - 1] == b[j - 1]) dp[i][j] = dp[i - 1][j - 1] + 1;
  48.             else dp[i][j] = max(dp[i][j - 1] , dp[i - 1][j]);
  49.     k = dp[a.size()][b.size()];
  50.     n = a.size(); m = b.size();
  51. }
  52.  
  53. int main()
  54. {
  55.     init();
  56.     int test_case = 1;
  57.     //cin >> test_case;
  58.     while(test_case --)
  59.     {
  60.         read();
  61.         process();
  62.     }
  63.     return 0;
  64. }
  65.  
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1
https://ideone.com/MPVeD1
language:
C++14 (gcc 8.3)
created:
4 days 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!