SHARE
TWEET

Untitled

a guest Dec 8th, 2019 86 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1.     #include <iostream>
  2.     #include <string>
  3.     #include <stdio.h>
  4.     #include <stack>
  5.     #include <algorithm>
  6.     #include <list>
  7.     #include <queue>
  8.     #include <vector>
  9.     #include <cassert>
  10.  
  11. using namespace std;
  12.  
  13. using std::string;
  14. using std::cin;
  15. using std::cout;
  16. using std::list;
  17. using std::endl;
  18. using std::stack;
  19. using std::queue;
  20. using std::min;
  21. using std::max;
  22. using std::vector;
  23.  
  24. const int INF = 1000000000;
  25. vector<char> symb = {'a', 'b', 'c', '.', '*', '+', '1'};
  26. vector<char> ch = {'a', 'b', 'c'};
  27.  
  28. class Task8 {
  29. public:
  30.     using status = int;
  31.  
  32.     string s;
  33.     char symbol;
  34.     int k;
  35.  
  36.     Task8() :
  37.         s(""),
  38.         symbol('#'),
  39.         k(0)
  40.     {}
  41.  
  42.     Task8(string _s, char _c, int _k) :
  43.         s(_s),
  44.         symbol(_c),
  45.         k(_k)
  46.     {}
  47.  
  48.     string int2str(int x) { // x >= 0
  49.         if (x == 0)
  50.             return "0";
  51.         string res = "";
  52.         while (x > 0) {
  53.             res += (char)(x % 10 + '0');
  54.             x /= 10;
  55.         }
  56.         reverse(res.begin(), res.end());
  57.         return res;
  58.     }
  59.  
  60.     struct State {
  61.         vector<int> canMake;
  62.         vector<int> minLen;
  63.  
  64.         State(int _k) :
  65.             canMake(_k + 1, false),
  66.             minLen(_k + 1, INF)
  67.         {}
  68.  
  69.         State():
  70.             canMake(0),
  71.             minLen(0)
  72.         {}
  73.     };
  74.  
  75.     void read() {
  76.         cin >> s;
  77.         cin >> symbol;
  78.         cin >> k;
  79.     }
  80.  
  81.     status getArguments(vector<State>& stack, pair<State, State>& args) {
  82.         if (stack.empty()) {
  83.             return -1;
  84.         }
  85.         args.second = stack.back();
  86.         stack.pop_back();
  87.  
  88.         if (stack.empty()) {
  89.             return -1;
  90.         }
  91.         args.first = stack.back();
  92.         stack.pop_back();
  93.  
  94.         return 1;
  95.     }
  96.  
  97.     int solve() {
  98.         vector<State> stack;
  99.  
  100.         for (char c : s) {
  101.             if (c >= 'a' && c <= 'z') {
  102.                 stack.push_back(State(k));
  103.                 stack.back().minLen[0] = 1;
  104.                 if (c == symbol) {
  105.                     stack.back().canMake[1] = 1;
  106.                     stack.back().minLen[1] = 1;
  107.                 }
  108.             } else if (c == '1') {
  109.                 stack.push_back(State(k));
  110.                 stack.back().canMake[0] = 1;
  111.                 stack.back().minLen[0] = 0;
  112.             } else if (c == '+') {
  113.                 pair<State, State> args;
  114.                 if (getArguments(stack, args) == -1) {
  115.                     return -1;
  116.                 }
  117.  
  118.                 stack.push_back(State(k));
  119.                 for (int prefix = 0; prefix <= k; ++prefix) {
  120.                     stack.back().canMake[prefix] = args.first.canMake[prefix] | args.second.canMake[prefix];
  121.                     stack.back().minLen[prefix] = min(args.first.minLen[prefix], args.second.minLen[prefix]);
  122.                 }
  123.             } else if (c == '.') {
  124.                 pair<State, State> args;
  125.                 if (getArguments(stack, args) == -1) {
  126.                     return -1;
  127.                 }
  128.  
  129.                 stack.push_back(State(k));
  130.                 for (int prefix = 0; prefix <= k; ++prefix) {
  131.                     for (int takeFromFirst = 0; takeFromFirst <= prefix; ++takeFromFirst) {
  132.                         int takeFromSecond = prefix - takeFromFirst;
  133.                         stack.back().canMake[prefix] |= args.first.canMake[takeFromFirst] & args.second.canMake[takeFromSecond];
  134.  
  135.                         if (args.first.canMake[takeFromFirst]) {
  136.                             stack.back().minLen[prefix] = min(
  137.                                 stack.back().minLen[prefix],
  138.                                 takeFromFirst + args.second.minLen[takeFromSecond]
  139.                             );
  140.                         }
  141.                     }
  142.                     stack.back().minLen[prefix] = min(
  143.                         stack.back().minLen[prefix],
  144.                         args.first.minLen[prefix] + args.second.minLen[0]
  145.                     );
  146.                 }
  147.             } else if (c == '*') {
  148.                 if (stack.empty()) {
  149.                     return -1;
  150.                 }
  151.                 State arg = stack.back();
  152.                 stack.pop_back();
  153.  
  154.                 stack.push_back(State(k));
  155.                 stack.back().canMake[0] = 1;
  156.                 for (int prefix = 1; prefix <= k; ++prefix) {
  157.                     for (int i = 1; i <= prefix; ++i) {
  158.                         if (arg.canMake[i] && stack.back().canMake[prefix - i]) {
  159.                             stack.back().canMake[prefix] = 1;
  160.                         }
  161.                     }
  162.                 }
  163.  
  164.                 stack.back().minLen[0] = 0;
  165.                 for (int prefix = 0; prefix <= k; ++prefix) {
  166.                     for (int i = 0; i < prefix; ++i) {
  167.                         if (stack.back().canMake[i]) {
  168.                             stack.back().minLen[prefix] = min(
  169.                                 stack.back().minLen[prefix],
  170.                                 i + arg.minLen[prefix - i]
  171.                             );
  172.                         }
  173.                     }
  174.                 }
  175.             }
  176.         }
  177.  
  178.         if ((int)stack.size() != 1) {
  179.             return -1;
  180.         }
  181.  
  182.         if (stack.back().minLen[k] == INF) {
  183.             return INF;
  184.         } else {
  185.             return stack.back().minLen[k];
  186.         }
  187.     }
  188. };
  189.  
  190.  
  191. int ans (string str, char x, int k){
  192.     if (x != 'a' && x != 'b' && x != 'c'){
  193.         return -1;
  194.     }
  195.     stack<vector<int>> st;
  196.     for (int i = 0; i < str.length(); ++i){
  197.         if (str[i] != 'a' && str[i] == 'b' && str[i] == 'c' && str[i] != '1' && str[i] != '.' && str[i] != '*' && str[i] != '+'){
  198.             return -1;
  199.         }
  200.         vector <int> min_length;
  201.         if (str[i] == 'a' || str[i] == 'b' || str[i] == 'c' || str[i] == '1'){
  202.             if (str[i] == x){
  203.                 min_length.push_back(1);
  204.                 min_length.push_back(1);
  205.             }
  206.             else{
  207.                 if (str[i] == '1'){
  208.                     min_length.push_back(0);
  209.                     min_length.push_back(INF);
  210.                 }
  211.                 else{
  212.                     min_length.push_back(1);
  213.                     min_length.push_back(INF);
  214.                 }
  215.             }
  216.             st.push(min_length);
  217.         }
  218.         if (str[i] == '+'){
  219.             if (st.size() < 2){
  220.                 return -1;
  221.             }
  222.             vector<int> s2 = st.top();
  223.             st.pop();
  224.             vector<int> s1 = st.top();
  225.             st.pop();
  226.             int new_sz = max(s1.size(), s2.size());
  227.             vector<int> new_vector;
  228.             for (int j = 0; j < new_sz; ++j){
  229.                 new_vector.push_back(INF);
  230.                 if (s1.size() > j) new_vector[j] = min(s1[j], new_vector[j]);
  231.                 if (s2.size() > j) new_vector[j] = min(s2[j], new_vector[j]);
  232.             }
  233.             st.push(new_vector);
  234.         }
  235.         if (str[i] == '.'){
  236.             if (st.size() < 2){
  237.                 return -1;
  238.             }
  239.             vector<int> s2 = st.top();
  240.             st.pop();
  241.             vector<int> s1 = st.top();
  242.             st.pop();
  243.             vector<int> new_vector(s1.size() + s2.size() - 1, INF);
  244.             if (s2[0] < INF){
  245.                 for (int j = 0; j < s1.size(); ++j) {
  246.                     if (s1[j] < INF) {
  247.                         new_vector[j] = s1[j] + s2[0];
  248.                     }
  249.                 }
  250.             }
  251.             for (int j = 0; j < s1.size(); ++j){
  252.                 if (s1[j] == j){
  253.                     for (int l = 0; l < s2.size(); ++l){
  254.                         if (s2[l] < INF){
  255.                             new_vector[j + l] = min(new_vector[j + l], s1[j] + s2[l]);
  256.                         }
  257.                     }
  258.                 }
  259.                 if (j == 0 && s1[j] < INF && s2[0] < INF){
  260.                     new_vector[0] = min(new_vector[0], s1[0] + s2[0]);
  261.                 }
  262.             }
  263.             st.push(new_vector);
  264.         }
  265.         if (str[i] == '*'){
  266.             if (st.size() < 1){
  267.                 return -1;
  268.             }
  269.             vector<int> s1 = st.top();
  270.             st.pop();
  271.             vector<int> new_vector;
  272.             new_vector.push_back(0);
  273.             for (int j = 0; j < 2 * k; ++j){
  274.                 if (j + 1 < s1.size()) {
  275.                     new_vector.push_back(s1[j + 1]);
  276.                 } else {
  277.                     new_vector.push_back(INF);
  278.                 }
  279.             }
  280.             for (int j = 1; j <= 2 * k; ++j) {
  281.                 for (int l = 1; l < s1.size(); ++l) {
  282.                     if (s1[l] < INF && new_vector[j - l] == (j - l)) {
  283.                         new_vector[j] = min(new_vector[j], new_vector[j - l] + s1[l]);
  284.                     }
  285.                 }
  286.             }
  287.  
  288.             for (int j = new_vector.size() - 2; j >= 0; --j)
  289.             {
  290.                 new_vector[j] = min(new_vector[j], new_vector[j + 1]);
  291.             }
  292.             st.push(new_vector);
  293.         }
  294.     }
  295.     if (st.size() > 1){
  296.         return -1;
  297.     }
  298.     vector<int> vec = st.top();
  299.     if (k >= vec.size()){
  300.         return INF;
  301.     }
  302.     return vec[k];
  303. }
  304.  
  305.     void test()
  306.     {
  307.         assert(ans("acb..bab.c.*.ab.ba.+.+*a.", 'b', 2) == 4);    // it's check answer for regex (acb + b(abc)*(ab + ba))*a
  308.         assert(ans("acb..bab.c.*.ab.ba.+.+*a.", 'b', 1) == 4);
  309.         assert(ans("acb..bab.c.*.ab.ba.+.+*a.", 'b', 3) == INF);
  310.         assert(ans("acb..bab.c.*.ab.ba.+.+*a.", 'a', 1) == 1);
  311.         assert(ans("acb..bab.c.*.ab.ba.+.+*a.", 'a', 2) == INF);
  312.         assert(ans("acb..bab.c.*.ab.ba.+.+*a.", 'c', 1) == INF);
  313.         assert(ans("acb..bab.c.*.ab.ba.+.+*a.", 'b', 2) == 4);    // it's check answer for regex (acb + b(abc)*(ab + ba))*a
  314.         assert(ans("ab+c.aba.*.bac.+.+*", 'c', 4) == INF);        // it's check answer for regex ((a + b)c + a(ba)*(b + ac))*
  315.         assert(ans("ab+c.aba.*.bac.+.+*", 'c', 1) == INF);
  316.         assert(ans("ab+c.aba.*.bac.+.+*", 'b', 1) == 2);
  317.         assert(ans("ab+c.aba.*.bac.+.+*", 'b', 2) == INF);
  318.         assert(ans("ab+c.aba.*.bac.+.+*", 'b', 3) == INF);
  319.         assert(ans("ab+c.aba.*.bac.+.+*", 'a', 1) == 2);
  320.         assert(ans("aa.a.ab.1+*.1aaac...+.aa.*.", 'a', 5) == 5);  // it's check answer for regex aaa(ab + 1)*(1 + aaac)(aa)*
  321.         assert(ans("aa.a.ab.1+*.1aaac...+.aa.*.", 'a', 6) == 7);
  322.         assert(ans("aa.a.ab.1+*.1aaac...+.aa.*.", 'a', 7) == 7);
  323.         assert(ans("aa.a.ab.1+*.1aaac...+.a*.", 'a', 6) == 6);    // it's check answer for regex aaa(ab + 1)*(1 + aaac)(a)*
  324.         assert(ans("aa.a.ab.1+*.1aaac...+.a*.", 'a', 1) == 3);
  325.         assert(ans("aa.a.ab.1+*.1aaac...+.a*.", 'a', 3) == 3);
  326.         assert(ans("aa.a.ab.1+*.1aaac...+.a*.", 'b', 1) == INF);
  327.         assert(ans("aa.*bbb..*.cc.c.c.*.", 'a', 1) == 2);         // // it's check answer for regex aa*bbb*cccc*
  328.         assert(ans("aa.*bbb..*.cc.c.c.*.", 'a', 2) == 2);
  329.         assert(ans("aa.*bbb..*.cc.c.c.*.", 'a', 15) == 16);
  330.         assert(ans("aa.*bbb..*.cc.c.c.*.", 'b', 1) == 3);
  331.         assert(ans("aa.*bbb..*.cc.c.c.*.", 'b', 28) == 30);
  332.         assert(ans("aa.*bbb..*.cc.c.c.*.", 'b', 29) == 30);
  333.         assert(ans("aa.*bbb..*.cc.c.c.*.", 'b', 30) == 30);
  334.         assert(ans("aa.*bbb..*.cc.c.c.*.", 'c', 1) == 4);
  335.         assert(ans("aa.*bbb..*.cc.c.c.*.", 'c', 97) == 100);
  336.         assert(ans("aa.*bbb..*.cc.c.c.*.", 'c', 98) == 100);
  337.         assert(ans("aa.*bbb..*.cc.c.c.*.", 'c', 99) == 100);
  338.         assert(ans("aa.*bbb..*.cc.c.c.*.", 'c', 100) == 100);
  339.  
  340.  
  341.         assert(ans("ab+c.aba.*.bac.+.+*", 'a', 2) == 3);          // it's check answer for regex ((a + b)c + a(ba)*(b + ac))*
  342.         assert(ans("ab+c.aba.*.bac.+.+*", 'a', 3) == INF);
  343.         assert(ans("ab+c.aba.*.bac.+.+*", 'c', 4) == INF);
  344.         assert(ans("aab..*aaaa...+", 'a', 2) == 3);               // it's check answer for regex (aab)* + aaaa
  345.         assert(ans("aab..*aaaa...+", 'a', 4) == 4);
  346.         assert(ans("ab+c.aba.*.bac.+.+*", 'y', 1) == -1);         // it's check answer for regex with not correct symbol x
  347.         assert(ans("a**aa..aa.", 'a', 5) == -1);                  // it's check answer for regex a**aa aa (not correct regex
  348.         // there are more than 1 elem in stack at the end)
  349.         assert(ans("a**ad..aa.", 'a', 5) == -1);                  // it's check answer for not correct regex (there are not correct symbols)
  350.         assert(ans("a1**aa..a0.", 'a', 5) == -1);                 // it's check answer for not correct regex (there are not correct symbols)
  351.         assert(ans("*", 'a', 4) == -1);                           // it's check answer for not correct regex (where expected 1 elems for '*' but there are less)
  352.         assert(ans("a**aa+++aa1...", 'b', 1) == -1);              // it's check answer for not correct regex (where expected 2 elems for '+' but there are less)
  353.         assert(ans("a**1c+.bc*...", 'c', 1) == -1);               // it's check answer for not correct regex (where expected 2 elems for '.' but there are less)
  354.  
  355.     }
  356.  
  357. int testStrLen = 6;
  358.  
  359. void stress (vector<char> str) {
  360.     if (str.size() == 9) {
  361.         str.push_back('-');
  362.         for (int i = 0; i < 2; ++i) {
  363.             str[9] = ch[i];
  364.             stress(str);
  365.         }
  366.     }
  367.     else {
  368.         if (str.size() == 10) {
  369.             for (int i = 0; i < 50; ++i) {
  370.                 string s = "";
  371.                 for (int j = 0; j < 9; ++j) {
  372.                     s += str[j];
  373.                 }
  374.                 int ansMy = ans(s, str[9], i);
  375.                 Task8 solver(s, str[9], i);
  376.                 int ansTrue =  solver.solve();
  377.                 if (ansMy != ansTrue) {
  378.                     cout << "Wrong Answer! on test :  " << s << " " << str[9] << " " << i << endl;
  379.                     cout << "My answer = " << ansMy << " True answer = " << ansTrue << endl;
  380.                 }
  381.             }
  382.         }
  383.         else {
  384.             str.push_back('-');
  385.             for (int i = 0; i < 8; ++i) {
  386.                 str[str.size() - 1] = symb[i];
  387.                 stress(str);
  388.             }
  389.         }
  390.     }
  391. }
  392.  
  393.     int main() {
  394.         string s;
  395.         char x;
  396.         int k;
  397.  
  398.         vector<char> str;
  399.         stress(str);
  400.         /*cin >> s >> x >> k;
  401.         int answer = ans(s, x, k);
  402.         if (answer == -1){
  403.             cout << "Error : string of regular expression is not correct" << endl;
  404.         }
  405.         else {
  406.             cout << "ans = " << answer << endl;
  407.         } */
  408.         test();
  409.         /*for (int i = 0; i < 23; ++i) {
  410.             cin >> s >> x >> k;
  411.             int answer = ans(s, x, k);
  412.             int waitAnswer;
  413.             cin >> waitAnswer;
  414.             if (answer != waitAnswer) {
  415.                 cout << "Wrong! On test " << i << endl;
  416.             }
  417.         }*/
  418.         return 0;
  419.     }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top