fork download
copy 
  1. #include <vector>
  2. #include<queue>
  3. #include<limits.h>
  4. #include <list>
  5. #include <set>
  6. #include<map>
  7. #include <deque>
  8. #include <stack>
  9. #include <bitset>
  10. #include <functional>
  11. #include <numeric>
  12. #include <utility>
  13. #include <sstream>
  14. #include <iostream>
  15. #include <iomanip>
  16. #include <cstdio>
  17. #include <cstdlib>
  18. #include <ctime>
  19. #include<cmath>
  20. #include<memory.h>
  21. #include<assert.h>
  22. #include<fstream>
  23. #include<algorithm>
  24.  
  25. using namespace std;
  26.  
  27. #define ff first
  28. #define ss second
  29. #define all(data) data.begin(),data.end()
  30.  
  31. #define sig cout << "reached" << endl;
  32. #define parr(data) {for(auto da: data) cout << da << " "; cout << endl;}
  33. #define pmap(data) {for(auto da: data) cout << da.ff << " " << da.ss << endl; }
  34. #define pmat(data) {for(auto dat: data) {for(auto da: dat) cout << da << " "	; cout << endl;} }
  35. #define input freopen("i.in", "r", stdin);
  36. #define output freopen("o.out", "w", stdout);
  37.  
  38. #define forr(i,s,e) for(int i=s; i<e; i++)
  39. #define forre(i,s,e) for(int i = s; i>=e; i--)
  40.  
  41. #define sd(x) scanf("%d",&x);
  42. #define slld(x) scanf("%lld",&x);
  43. #define sf(x) scanf("%Lf",&x);
  44. #define sc(x) scanf(" %c",&x);
  45.  
  46. #define pd(x) printf("%d\n",x);
  47. #define pd_(x) printf("%d ",x);
  48. #define plld(x) printf("%lld\n",x);
  49. #define plld_(x) printf("%lld ",x);
  50. #define nl printf("\n");
  51.  
  52. typedef unsigned long long int llu; typedef long long int ll;
  53. typedef pair<int, int> pii; typedef pair<ll, ll> pll;
  54. typedef vector<int> vi;  typedef vector<vi> vvi;  typedef vector<ll> vl;    typedef vector<vl> vvl;
  55. typedef vector<pii> vpi; typedef vector<pll> vpl; typedef vector<vpi> vvpi; typedef vector<vpl> vvpl;
  56. typedef vector<bool> vb; typedef vector<vb> vvb;  typedef vector<char> vc;  typedef vector<vector<char> > vvc;
  57.  
  58. int inf = 1000000005; ll llinf = 2000000000000000005LL;
  59. ll mod = 1000000007; ll mod9 = 1000000009;
  60. double pi = 3.1415926535897; double eps = 1e-15;
  61. int dx[] = { 1, -1, 0, 0, 1, -1, 1, -1 }, dy[] = { 0, 0, 1, -1, 1, 1, -1, -1 };
  62.  
  63. vb isprime; vi primes;
  64. void seive(int n, bool wantlist = true){ isprime.resize(n + 1, true); isprime[0] = isprime[1] = false; int sq = sqrt(n + 1); forr(i, 2, sq + 1){ if (isprime[i]){ for (int j = i*i; j <= n; j += i) isprime[j] = false; } } for (int i = 2; wantlist && i <= n; i++){ if (isprime[i]) primes.push_back(i); } }
  65. template<class T>
  66. inline T gcd(T a, T b){ while (b > 0){ a %= b; swap(a, b); } return a; }
  67. template<class T>
  68. inline T lcm(T a, T b){ return a*b / gcd(a, b); }
  69. template<class T>
  70. inline vector<T> operator+(vector<T>& a, vector<T>& b) { assert(a.size() == b.size()); int n = a.size(); vector<T> c(n); for (int i = 0; i < n; i++) c[i] = a[i] + b[i]; return c; }
  71. int fastMax(int x, int y) { return (((y - x) >> (32 - 1))&(x^y)) ^ y; }
  72. inline ll bexp(ll x, ll n, ll m = mod){ ll res = 1; x %= m; while (n){ if (n & 1) res = res * x % m; x = x * x % m; n >>= 1; } return res; }
  73. inline bool ispalin(string& str){ int n = str.length(); for (int i = 0; i < n / 2; i++) if (str[i] != str[n - i - 1]) return false; return true; }
  74.  
  75. //******************************************************************************************
  76.  
  77. string a, b;
  78. int na, nb;
  79.  
  80. string expand(string x){
  81. 	string tmp;
  82. 	for(char c : x){
  83. 		if(isalpha(c)) tmp.push_back(c);
  84. 		else{
  85. 			forr(i, 0, 4) tmp.push_back('*');
  86. 		}
  87. 	}
  88. 	return tmp;
  89. }
  90.  
  91. int mem[2005][2005];
  92.  
  93. int rec(int i, int j){
  94. 	if(i == na && j == nb) return true;
  95. 	if(i == na){
  96. 		forr(k, j, nb) if(b[k] != '*') return false;
  97. 		return true;
  98. 	}
  99. 	if(j == nb){
  100. 		forr(k, i, na) if(a[k] != '*') return false;
  101. 		return true;
  102. 	}
  103. 	int &res = mem[i][j];
  104. 	if(res == -1){
  105. 		res = 0;
  106. 		if(a[i] != '*' && b[j] != '*'){
  107. 			if(a[i] == b[j]) res = rec(i + 1, j + 1);
  108. 			else res = false;
  109. 		}
  110. 		else{
  111. 			if(a[i] != '*' && b[j] == '*') res = rec(i, j + 1) || rec(i + 1, j + 1);
  112. 			else if(a[i] == '*' && b[j] != '*') res = rec(i + 1, j) || rec(i + 1, j + 1);
  113. 			else res = res || rec(i + 1, j + 1) || rec(i + 1, j) || rec(i, j + 1);
  114. 		}
  115. 	}
  116. 	return res;
  117. }
  118.  
  119. int main(){
  120. 	input
  121. 	output
  122. 	int t; sd(t);
  123. 	forr(i, 1, t + 1){
  124. 		memset(mem, -1, sizeof(mem));
  125. 		cin >> a >> b;
  126. 		a = expand(a); b = expand(b);
  127. 		na = a.length(); nb = b.length();
  128. 		cout << "Case #" << i << ": ";
  129. 		if(rec(0, 0) == 1) printf("TRUE\n");
  130. 		else printf("FALSE\n");
  131. 	}
  132.  
  133. }
Time limit exceeded #stdin #stdout 5s 30952KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/i5zApD
language:
C++14 (gcc 8.3)
created:
7 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!