Advertisement
Guest User

Untitled

a guest
Nov 24th, 2014
144
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.19 KB | None | 0 0
  1. #include <iostream>
  2. #include <fstream>
  3. #include <iomanip>
  4.  
  5. #define MAGIC 2147483647
  6. #define MINUSINF -2147483647
  7. #define INF 2147483647
  8. using namespace std;
  9.  
  10. long liczba[501];
  11. char znak[500];
  12. long maks[500][500];
  13. long mini[500][500];
  14.  
  15. long tmp[500];
  16.  
  17. long getMaxSum(int from, int i, int to); //forward declaration
  18. long getMaxDiff(int from, int i, int to);
  19. long getMaxMult(int from, int i, int to);
  20. long getMinSum(int from, int i, int to);
  21. long getMinDiff(int from, int i, int to);
  22. long getMinMult(int from, int i, int to);
  23. long getMax(int from, int to);
  24. long getMin(int from, int to);
  25.  
  26.  
  27.  
  28.  
  29. int readFile(){
  30.     ifstream in;
  31.     in.open("in");
  32.     int i=0;
  33.     while(!in.eof()){
  34.         in >> liczba[i];
  35.         in >> znak[i];
  36.         i++;
  37.     }
  38.     return i;
  39. }
  40.  
  41. void initArrays(int n){
  42.     for(int i=0; i<n; i++){
  43.         for(int j=0; j<n; j++){
  44.             maks[i][j] = MAGIC;
  45.             mini[i][j] = MAGIC;
  46.         }
  47.         maks[i][i] = liczba[i];
  48.         mini[i][i] = liczba[i];
  49.     }
  50. }
  51.  
  52. int evaluate(int i){
  53.  
  54.  
  55.     int result;
  56.     if(znak[i]=='*')
  57.         result = liczba[i]*liczba[i+1];
  58.     if(znak[i]=='+')
  59.         result = liczba[i]+liczba[i+1];
  60.     if(znak[i]=='-')
  61.         result = liczba[i]-liczba[i+1];
  62.  
  63.  
  64.     return result;
  65. }
  66.  
  67. long getMaxSum(int from, int i, int to){
  68.     return getMax(from, i) + getMax(i+1, to);
  69. };
  70. long getMaxDiff(int from, int i, int to){
  71.     return getMax(from, i) - getMin(i+1, to);
  72. };
  73.  
  74. long getMaxMult(int from, int i, int to){
  75.     long tmp[4];
  76.     tmp[0] = getMax(from, i) * getMax(i+1, to);
  77.     tmp[1] = getMax(from, i) * getMin(i+1, to);
  78.     tmp[2] = getMin(from, i) * getMax(i+1, to);
  79.     tmp[3] = getMin(from, i) * getMin(i+1, to);
  80.  
  81.     for(int i=1; i<4; i++){
  82.         if(tmp[i]>tmp[0])
  83.             tmp[0] = tmp[i];
  84.     }
  85.     return tmp[0];
  86. };
  87.  
  88. long getMinSum(int from, int i, int to){
  89.     return getMin(from, i) + getMin(i+1, to);
  90. };
  91. long getMinDiff(int from, int i, int to){
  92.     return getMin(from, i)-getMax(i+1, to);
  93. };
  94. long getMinMult(int from, int i, int to){
  95.     long tmp[4];
  96.     tmp[0] = getMax(from, i) * getMax(i+1, to);
  97.     tmp[1] = getMax(from, i) * getMin(i+1, to);
  98.     tmp[2] = getMin(from, i) * getMax(i+1, to);
  99.     tmp[3] = getMin(from, i) * getMin(i+1, to);
  100.  
  101.     for(int i=1; i<4; i++){
  102.         if(tmp[i]<tmp[0])
  103.             tmp[0] = tmp[i];
  104.     }
  105.     return tmp[0];
  106. };
  107.  
  108. long getMax(int from, int to){
  109.  
  110.  
  111.     if((from-to) == 1){
  112.         return evaluate(from);
  113.     }
  114.  
  115.     if(from==to)
  116.         return liczba[from];
  117.     long tmp;
  118.     long max = MINUSINF;
  119.     for(int i=0; i<(to-from); i++){
  120.         if(znak[i+from]=='+')
  121.             tmp = getMaxSum(from, from+i, to);
  122.         if(znak[i+from]=='-')
  123.             tmp = getMaxDiff(from, from+i, to);
  124.         if(znak[i+from]=='*')
  125.             tmp = getMaxMult(from, from+i, to);
  126.         if(tmp > max)
  127.             max = tmp;
  128.     }
  129.  
  130.     return max;
  131.  
  132. }
  133.  
  134. long getMin(int from, int to){
  135.  
  136.  
  137.     if((from-to) == 1){
  138.         return evaluate(from);
  139.     }
  140.     if(from==to)
  141.         return liczba[from];
  142.     long tmp;
  143.     long min = INF;
  144.     for(int i=0; i<(to-from); i++){
  145.         if(znak[i+from]=='+')
  146.             tmp = getMinSum(from, from+i, to);
  147.         if(znak[i+from]=='-')
  148.             tmp = getMinDiff(from, from+i, to);
  149.         if(znak[i+from]=='*')
  150.             tmp = getMinMult(from, from+i, to);
  151.         if(tmp < min)
  152.             min = tmp;
  153.     }
  154.     return min;
  155. }
  156.  
  157. int main(){
  158.     int n = readFile();
  159.     initArrays(n);
  160.     n--;
  161.     cout << n<<endl;
  162.     cout << getMax(0,n)<<endl;
  163.     cout << getMin(0,n)<<endl;
  164.  
  165.     return 0;
  166. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement