HabKaffee

Heaven_Mana_1

Nov 4th, 2020
130
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <vector>
  2. #include <fstream>
  3. #include <iostream>
  4. #include <cstdlib>
  5. #include <typeinfo>
  6. #include <climits>
  7.  
  8. std::ifstream FileIn("/home/habkaffee/Cpp/Heaven_mana/data.txt");
  9.  
  10. void funcSort(std::vector<std::vector<int>>& vector){
  11.     int tmp = 0;
  12.     for (size_t i = 0; i < vector.size() - 1; ++i) {
  13.         for (size_t j = 0; j < vector.size() - i - 1; ++j)
  14.             if (vector[j][0] > vector[j + 1][0]) {
  15.             for (size_t k = 0; k < 2; ++k) {
  16.                 tmp = vector[j][k];
  17.                 vector[j][k] = vector[j + 1][k];
  18.                 vector[j + 1][k] = tmp;
  19.                 }
  20.             }
  21.     }
  22. }
  23.  
  24. int distance(int first, int second){
  25.     return std::abs(first-second);
  26. }
  27.  
  28. int searchForLeftMinInArr(std::vector<std::vector<int>>& coordinatesAndTime, int curentPosition){
  29.     int minTime = INT_MAX;
  30.     int minCoord = INT_MAX;
  31.     if (curentPosition == -1){
  32.         return -1;
  33.     }
  34.     for (size_t i = 0; i<curentPosition ; ++i){
  35.         if (minTime>coordinatesAndTime[i][1] && coordinatesAndTime[i][1]>=0){
  36.             minTime = coordinatesAndTime[i][1];
  37.             minCoord = i;
  38.         }
  39.     }
  40.     return minCoord == INT_MAX ? -1 : minCoord;
  41. }
  42.  
  43. int searchForRightMinInArr(std::vector<std::vector<int>>& coordinatesAndTime, int curentPosition){
  44.     int minTime = INT_MAX;
  45.     int minCoord = INT_MAX;
  46.     for (size_t i = curentPosition+1; i<coordinatesAndTime.size() ; ++i){
  47.         if(minTime>=coordinatesAndTime[i][1] && coordinatesAndTime[i][1]>=0){
  48.             minTime = coordinatesAndTime[i][1];
  49.             minCoord = i;
  50.         }
  51.     }
  52.     return minCoord == INT_MAX ? -1 : minCoord;
  53. }
  54.  
  55. int searchForGlobalMin(std::vector<std::vector<int>>& coordinatesAndTime){
  56.     int minTime = INT_MAX;
  57.     int minCoord = INT_MAX;
  58.     for (size_t i = 0; i<coordinatesAndTime.size() ; ++i){
  59.         if(minTime>=coordinatesAndTime[i][1] && coordinatesAndTime[i][1]>=0){
  60.             minTime = coordinatesAndTime[i][1];
  61.             minCoord = i;
  62.         }
  63.     }
  64.     return minCoord;
  65. }
  66.  
  67. bool checkForEndOfMana(std::vector<std::vector<int>>& coordinatesAndTime){
  68.     for (size_t i = 0; i<coordinatesAndTime.size();++i){
  69.         if (coordinatesAndTime[i][1] != -1){
  70.             return true;
  71.         }
  72.     }
  73.     return false;
  74. }
  75.  
  76. void decreaseTime(std::vector<std::vector<int>>& coordinatesAndTime, int step){
  77.     for (size_t i = 0; i<coordinatesAndTime.size();++i){
  78.         if (coordinatesAndTime[i][1]>=0){
  79.             coordinatesAndTime[i][1] -= step;
  80.         }
  81.         if (coordinatesAndTime[i][1]<0){
  82.             coordinatesAndTime[i][1] = -1;
  83.         }
  84.     }
  85. }
  86.  
  87. int heavenManaSearch(std::vector<std::vector<int>>& coordinatesAndTime, unsigned totalManaAmount, unsigned curentManaAmount,int curentPosition,int totalSecond){
  88.     int leftMin = searchForLeftMinInArr(coordinatesAndTime,curentPosition);
  89.     int rightMin = searchForRightMinInArr(coordinatesAndTime,curentPosition);
  90.  
  91.     //conditions for immediate exit
  92.     if (leftMin != -1){
  93.         if (distance(coordinatesAndTime[curentPosition][0],coordinatesAndTime[leftMin][0])>coordinatesAndTime[leftMin][1]){
  94.             //std::cout<<-1;
  95.             return -1;
  96.         }
  97.     }
  98.     if (rightMin != -1){
  99.         if (distance(coordinatesAndTime[curentPosition][0],coordinatesAndTime[rightMin][0])>coordinatesAndTime[rightMin][1]){
  100.             //std::cout<<-1;
  101.             return -1;
  102.         }
  103.     }
  104.     //end of conditions
  105.  
  106.     if (coordinatesAndTime[curentPosition][1]>=0){
  107.         coordinatesAndTime[curentPosition][1] = -1;
  108.         curentManaAmount++;
  109.     }
  110.  
  111.     if (leftMin == -1){
  112.         if (distance(coordinatesAndTime[curentPosition][0],coordinatesAndTime[rightMin][0])>coordinatesAndTime[rightMin][1]){
  113.             return -1;
  114.         }
  115.         else {
  116.             for (size_t i = curentPosition+1;i<rightMin;++i){
  117.                 if (coordinatesAndTime[i][1]>=0){
  118.                     coordinatesAndTime[i][1] = -1;
  119.                     curentManaAmount++;
  120.                 }
  121.                 coordinatesAndTime[rightMin][1] = -1;
  122.                 curentManaAmount++;
  123.                 totalSecond += distance(coordinatesAndTime[curentPosition][0],coordinatesAndTime[rightMin][0]);
  124.                 curentPosition = rightMin;
  125.                 heavenManaSearch(coordinatesAndTime, totalManaAmount,curentManaAmount,curentPosition, totalSecond);
  126.             }
  127.         }
  128.     }
  129.     else if (rightMin == -1){
  130.         if (distance(coordinatesAndTime[curentPosition][0],coordinatesAndTime[leftMin][0])>coordinatesAndTime[leftMin][1]){
  131.             return -1;
  132.         }
  133.         else {
  134.             for (size_t i = curentPosition-1;i>leftMin;--i){
  135.                 if (coordinatesAndTime[i][1]>=0){
  136.                     coordinatesAndTime[i][1] = -1;
  137.                     curentManaAmount++;
  138.                 }
  139.                 coordinatesAndTime[leftMin][1] = -1;
  140.                 curentManaAmount++;
  141.                 totalSecond += distance(coordinatesAndTime[curentPosition][0],coordinatesAndTime[leftMin][0]);
  142.                 curentPosition = rightMin;
  143.                 heavenManaSearch(coordinatesAndTime, totalManaAmount,curentManaAmount,curentPosition, totalSecond);
  144.             }
  145.         }
  146.     }
  147.  
  148.  
  149.     //calculating the closer point
  150.    
  151.     //if distances are equal
  152.     if (distance(coordinatesAndTime[curentPosition][0],coordinatesAndTime[leftMin][0])==distance(coordinatesAndTime[curentPosition][0],coordinatesAndTime[rightMin][0])){
  153.        if (coordinatesAndTime[leftMin][1]>coordinatesAndTime[rightMin][1]){
  154.            coordinatesAndTime[rightMin][1] = -1;
  155.            for (size_t i = curentPosition+1; i<rightMin;++i){
  156.                if (coordinatesAndTime[i][1] >= 0){
  157.                    coordinatesAndTime[i][1] = -1;
  158.                    curentManaAmount++;
  159.                }
  160.            }
  161.            curentManaAmount++;
  162.            totalSecond+=distance(coordinatesAndTime[curentPosition][0],coordinatesAndTime[rightMin][0]);
  163.            decreaseTime(coordinatesAndTime, distance(coordinatesAndTime[curentPosition][0],coordinatesAndTime[rightMin][0]));
  164.            curentPosition = rightMin;
  165.            heavenManaSearch (coordinatesAndTime, totalManaAmount,curentManaAmount,curentPosition,totalSecond);
  166.        }
  167.        else if (coordinatesAndTime[leftMin][1]<coordinatesAndTime[rightMin][1]){
  168.            coordinatesAndTime[leftMin][1] = -1;
  169.            for (size_t i = curentPosition+1; i>leftMin;--i){
  170.                if (coordinatesAndTime[i][1] >= 0){
  171.                    coordinatesAndTime[i][1] = -1;
  172.                    curentManaAmount++;
  173.                }
  174.            }
  175.            curentManaAmount++;
  176.            totalSecond+=distance(coordinatesAndTime[curentPosition][0],coordinatesAndTime[leftMin][0]);
  177.            decreaseTime(coordinatesAndTime, distance(coordinatesAndTime[curentPosition][0],coordinatesAndTime[leftMin][0]));
  178.            curentPosition = leftMin;
  179.            heavenManaSearch (coordinatesAndTime, totalManaAmount,curentManaAmount,curentPosition,totalSecond);
  180.        }
  181.    }
  182.    //if distances aren't equal
  183.     else if (distance(coordinatesAndTime[curentPosition][0],coordinatesAndTime[leftMin][0])>distance(coordinatesAndTime[curentPosition][0],coordinatesAndTime[rightMin][0])){
  184.         //if we have time to take left mana and go to right mana than
  185.         if (coordinatesAndTime[rightMin][1]>=(coordinatesAndTime[curentPosition][0]+coordinatesAndTime[leftMin][0])*2+coordinatesAndTime[rightMin][0]){
  186.             for (size_t i = curentPosition-1; i>leftMin; --i){
  187.                 if (coordinatesAndTime[i][1] >= 0){
  188.                     coordinatesAndTime[i][1] = -1;
  189.                     curentManaAmount++;
  190.                 }
  191.             }
  192.  
  193.             coordinatesAndTime[leftMin][1] = -1;
  194.             curentManaAmount++;
  195.             totalSecond+=2*distance(coordinatesAndTime[curentPosition][0],coordinatesAndTime[leftMin][0]);
  196.             decreaseTime(coordinatesAndTime, distance(curentPosition, leftMin));
  197.            
  198.             for (size_t i = curentPosition+1;i<rightMin;++i){
  199.                 if (coordinatesAndTime[i][1] >= 0){
  200.                     coordinatesAndTime[i][1] = -1;
  201.                     curentManaAmount++;
  202.                 }
  203.             }
  204.             coordinatesAndTime[rightMin][1] = -1;
  205.             curentManaAmount++;
  206.             totalSecond += distance(coordinatesAndTime[curentPosition][0],coordinatesAndTime[rightMin][0]);
  207.             decreaseTime(coordinatesAndTime, distance(coordinatesAndTime[curentPosition][0],coordinatesAndTime[rightMin][0]));
  208.             curentPosition = rightMin;
  209.             heavenManaSearch (coordinatesAndTime, totalManaAmount,curentManaAmount,curentPosition,totalSecond);
  210.         }
  211.         //if we haven't than
  212.         else{
  213.             for (size_t i = curentPosition+1;i<rightMin;++i){
  214.                 if (coordinatesAndTime[i][1] >= 0){
  215.                     coordinatesAndTime[i][1] = -1;
  216.                     curentManaAmount++;
  217.                 }
  218.             }
  219.             coordinatesAndTime[rightMin][1] = -1;
  220.             curentManaAmount++;
  221.             totalSecond += distance(coordinatesAndTime[curentPosition][0],coordinatesAndTime[rightMin][0]);
  222.             decreaseTime(coordinatesAndTime, distance(coordinatesAndTime[curentPosition][0],coordinatesAndTime[rightMin][0]));
  223.             curentPosition = rightMin;
  224.             heavenManaSearch (coordinatesAndTime, totalManaAmount,curentManaAmount,curentPosition,totalSecond);
  225.         }
  226.     }
  227.     else if (distance(coordinatesAndTime[curentPosition][0],coordinatesAndTime[leftMin][0])<distance(coordinatesAndTime[curentPosition][0],coordinatesAndTime[rightMin][0])){
  228.         //if we have time to take left mana and go to right mana than
  229.         if (coordinatesAndTime[leftMin][1]>=(coordinatesAndTime[curentPosition][0]+coordinatesAndTime[rightMin][0])*2+coordinatesAndTime[leftMin][0]){
  230.             for (size_t i = curentPosition+1; i<rightMin; ++i){
  231.                 if (coordinatesAndTime[i][1] >= 0){
  232.                     coordinatesAndTime[i][1] = -1;
  233.                     curentManaAmount++;
  234.                 }
  235.             }
  236.  
  237.             coordinatesAndTime[rightMin][1] = -1;
  238.             curentManaAmount++;
  239.             totalSecond+=2*distance(coordinatesAndTime[curentPosition][0],coordinatesAndTime[rightMin][0]);
  240.             decreaseTime(coordinatesAndTime, distance(curentPosition, rightMin));
  241.            
  242.             for (size_t i = curentPosition-1;i>leftMin;--i){
  243.                 if (coordinatesAndTime[i][1] >= 0){
  244.                     coordinatesAndTime[i][1] = -1;
  245.                     curentManaAmount++;
  246.                 }
  247.             }
  248.             coordinatesAndTime[leftMin][1] = -1;
  249.             curentManaAmount++;
  250.             totalSecond += distance(coordinatesAndTime[curentPosition][0],coordinatesAndTime[leftMin][0]);
  251.             decreaseTime(coordinatesAndTime, distance(coordinatesAndTime[curentPosition][0],coordinatesAndTime[leftMin][0]));
  252.             curentPosition = leftMin;
  253.             heavenManaSearch (coordinatesAndTime, totalManaAmount,curentManaAmount,curentPosition,totalSecond);
  254.         }
  255.         //if we haven't than
  256.         else{
  257.             for (size_t i = curentPosition-1;i>leftMin;--i){
  258.                 if (coordinatesAndTime[i][1] >= 0){
  259.                     coordinatesAndTime[i][1] = -1;
  260.                     curentManaAmount++;
  261.                 }
  262.             }
  263.             coordinatesAndTime[leftMin][1] = -1;
  264.             curentManaAmount++;
  265.             totalSecond += distance(coordinatesAndTime[curentPosition][0],coordinatesAndTime[leftMin][0]);
  266.             decreaseTime(coordinatesAndTime, distance(coordinatesAndTime[curentPosition][0],coordinatesAndTime[leftMin][0]));
  267.             curentPosition = leftMin;
  268.             heavenManaSearch (coordinatesAndTime, totalManaAmount,curentManaAmount,curentPosition,totalSecond);
  269.         }  
  270.     }
  271.  
  272.     if (totalManaAmount == curentManaAmount){
  273.         return totalSecond;
  274.     }
  275.     else {
  276.         return -1;
  277.     }
  278.     }
  279.  
  280.  
  281.  
  282. int main(){
  283.     int totalManaAmount = -1;
  284.     if(FileIn.is_open()){
  285.         FileIn >> totalManaAmount;
  286.     }
  287.     else {
  288.         std::cout<<"File can't open";
  289.         return -1;
  290.     }
  291.  
  292.     //std::cout<<totalManaAmount<<std::endl;
  293.  
  294.     std::vector<std::vector<int>> coordinatesAndTime(totalManaAmount, std::vector<int>(2,0));
  295.  
  296.     for (size_t i = 0; i<totalManaAmount;++i){
  297.         for (size_t j =0; j<2;++j){
  298.             FileIn>> coordinatesAndTime[i][j];
  299.         }
  300.     }
  301.  
  302.     funcSort(coordinatesAndTime);
  303.    
  304.     //std::cout<<"I'm working, at least now"<<std::endl;
  305.    
  306.     int startPosition = searchForGlobalMin(coordinatesAndTime);
  307.     std::cout<<startPosition<<std::endl;
  308.  
  309.     //std::cout<<"I'm working, at least now"<<std::endl;
  310.  
  311.     int totalSecond = heavenManaSearch(coordinatesAndTime,totalManaAmount,0,startPosition,0);
  312.  
  313.     std::cout<<totalSecond<<std::endl;
  314.     return 0;
  315. }
RAW Paste Data Copied