ამოხსნების სტატუსი

ამ გვერდზე თქვენ იხილავთ გაგზავნილი ამოხსნების სტატუსს.


გაგზავნის თარიღი: 12.05.2019 11:30:36

ამოცანა: გამოსახულებები

მომხმარებელი: Niko2019

ვერდიქტი: სრული ამოხსნა

შეფასება: 100.0 ქულა







#include <iostream>
#include <string>
#include <vector>
#include <utility>
#include <map>
#include <stdio.h>

using namespace std;

typedef pair < unsigned, unsigned > p2u;
typedef p2u xtotal;
typedef vector < pair<char, xtotal> > xseq;
typedef map<p2u,p2u> xsmap;

inline unsigned ops(xtotal x) {return x.first;}
inline unsigned ways(xtotal x) {return x.second;}
inline p2u mkp2u(unsigned x, unsigned y) {return make_pair(x,y);}

unsigned nchok(unsigned n, unsigned k)  {
  unsigned m,r,s;
  r = n-k;
  if (r<k)  k = r;
  if (k==0)  return 1;
  for (m=r=n-k+1,s=1; ++r,s++<k;)  m = m*r/s;
  return m;
}

inline xtotal joyndp(xtotal a, xtotal b)  {
  unsigned m = ops(a), n = ops(b);
  return mkp2u(1+m+n,nchok(m+n,n)*ways(a)*ways(b));
}

xtotal rngeval(xseq & q, p2u ir, xsmap & xsm)  {
  unsigned m = ir.first, n = ir.second;
  if (n-m==1)  return xsm[ir] = q[m].second;
  unsigned s = 0;
  for (unsigned i=n-1; i>m; --i)
    if (q[i].first=='+' || i==n-1)  {
      p2u ir1 = mkp2u(m,i), ir2 = mkp2u(i,n);
      if (xsm.find(ir2)==xsm.end())  rngeval(q,ir2,xsm);
      if (xsm.find(ir1)==xsm.end())  rngeval(q,ir1,xsm);
      s += ways(joyndp(xsm[ir1],xsm[ir2]));
    }
  return xsm[ir] = mkp2u(1+ops(xsm[mkp2u(m,n-1)])+ops(xsm[mkp2u(n-1,n)]),s);
}

xtotal rdxpr(string ops, const char* & p)  {
  xtotal u,v;
  xseq q;
  char op = ops[0];
  switch (op)  {
    case 'a': case '+': case '-':
    case 'm': case '*': case '/':
      for (;; ++p)  {
        v =  rdxpr(string("a+-").find(op)!=string::npos ? "m*/p" : "p---", p);
        if (op=='*')  op = '+';  else if (op=='/')  op = '-';
        if (op!='-')  op = '+';
        q.push_back(make_pair(op,v));
        if (op=*p, op!=ops[1] && op!=ops[2])  {
          xsmap xsm;
          return rngeval(q,mkp2u(0,q.size()),xsm);
        }
      }
    case 'p': case '^':
      for (;; ++p)  {
        v = *p=='(' ? rdxpr("a+-m",++p) : mkp2u(0,1);
        ++p;
        u = op=='^' ? joyndp(u,v) : v;
        if (op=*p, op!='^')  return u;
      }
  }
}

int main()  {
  string s;
  getline(cin,s);
  const char * p = s.c_str();
  cout << ways(rdxpr("a+-m",p)) << endl;
  return 0;
}

ტესტები

შემავალი მონაცემები
a-b-c
გამომავალი მონაცემები
1
თქვენი პასუხი
1
ჩეკერის პასუხი
YES
შემავალი მონაცემები
a+a+a+a+a*a
გამომავალი მონაცემები
60
თქვენი პასუხი
60
ჩეკერის პასუხი
YES
შემავალი მონაცემები
(((a-a)))+a+a+a+a+a
გამომავალი მონაცემები
360
თქვენი პასუხი
360
ჩეკერის პასუხი
YES
შემავალი მონაცემები
a-a+(a-a)*(a-a)
გამომავალი მონაცემები
8
თქვენი პასუხი
8
ჩეკერის პასუხი
YES
შემავალი მონაცემები
a+a+a+a+a+a+a+a+a+a+a+a+a
გამომავალი მონაცემები
479001600
თქვენი პასუხი
479001600
ჩეკერის პასუხი
YES
შემავალი მონაცემები
a-a-a-a-a-a-a-a+a+a+a+a+a
გამომავალი მონაცემები
11880
თქვენი პასუხი
11880
ჩეკერის პასუხი
YES
შემავალი მონაცემები
a+(a-a*a+a)-a-a*a^a
გამომავალი მონაცემები
57
თქვენი პასუხი
57
ჩეკერის პასუხი
YES
შემავალი მონაცემები
(a^a^(a+a/a)-a*a+a)
გამომავალი მონაცემები
15
თქვენი პასუხი
15
ჩეკერის პასუხი
YES
შემავალი მონაცემები
a-a-((a-a))/(a+a-a)^a
გამომავალი მონაცემები
48
თქვენი პასუხი
48
ჩეკერის პასუხი
YES
შემავალი მონაცემები
(a-a)*(a-a)*(a-a)*(a-a)
გამომავალი მონაცემები
272
თქვენი პასუხი
272
ჩეკერის პასუხი
YES