Guest User

Untitled

a guest
Apr 1st, 2018
106
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.01 KB | None | 0 0
  1. //https://www.reddit.com/r/dailyprogrammer/comments/87rz8c/20180328_challenge_355_intermediate_possible/
  2. #include <iostream>
  3. #include <map>
  4. using namespace std;
  5.  
  6. struct Ingredients{
  7.     int pumpkin;
  8.     int apple;
  9.     int egg;
  10.     int milk;
  11.     int sugar;
  12. };
  13.  
  14. void maxPies(map<int, int> &pieMap, Ingredients ingredients, int p=0, int a=0){
  15.  
  16.     if((ingredients.pumpkin - 1 < 0  || ingredients.egg - 3 < 0 || ingredients.milk - 4 < 0 || ingredients.sugar - 3 < 0)
  17.         && (ingredients.apple - 1 < 0  || ingredients.egg - 4 < 0 || ingredients.milk - 3 < 0 || ingredients.sugar - 2 < 0))
  18.     {
  19.         //Found max pies combination
  20.         //Add it to array
  21.         pieMap.insert(pair<int,int>(p,a));
  22.         return;
  23.     }
  24.     //Make Apple Pie
  25.     if(ingredients.apple - 1 >= 0  && ingredients.egg - 4 >= 0 && ingredients.milk - 3 >= 0 && ingredients.sugar - 2 >= 0){
  26.         //Subtract Ingredients
  27.         Ingredients i = ingredients;
  28.         i.apple--;
  29.         i.egg-=4;
  30.         i.milk-=3;
  31.         i.sugar-=2;
  32.         //Find More Pies
  33.         maxPies(pieMap, i, p, a+1);
  34.     }
  35.         //Make Pumpkin Pie
  36.     if(ingredients.pumpkin - 1 >= 0  && ingredients.egg - 3 >= 0 && ingredients.milk - 4 >= 0 && ingredients.sugar - 3 >= 0){
  37.         //Subtract Ingredients
  38.         Ingredients i = ingredients;
  39.         i.pumpkin--;
  40.         i.egg-=3;
  41.         i.milk-=4;
  42.         i.sugar-=3;
  43.         //Find More Pies
  44.         maxPies(pieMap, i, p+1, a);
  45.     }
  46. }
  47.  
  48. int main(){
  49.     Ingredients ingredients;
  50.     char c;
  51.     map<int, int> pieMap;
  52.     int max;
  53.  
  54.     //Read Input
  55.     cin >> ingredients.pumpkin >> c >> ingredients.apple >> c >> ingredients.egg >> c >> ingredients.milk >> c >> ingredients.sugar;
  56.  
  57.     //Calculate Totals
  58.     //Inefficient Recursion :(
  59.     maxPies(pieMap, ingredients);
  60.  
  61.     //Find Max Pie Count
  62.     map<int, int>::iterator it = pieMap.begin();
  63.     while(it != pieMap.end()){
  64.         if((it->first + it->second) > max) max = (it->first + it->second);
  65.         it++;
  66.     }  
  67.  
  68.     it = pieMap.begin();
  69.     //Print Max Pies Combos
  70.     while(it != pieMap.end()){
  71.         if((it->first + it->second) == max){
  72.             cout << it->first << " Pumpkin Pies and " << it->second << " Apple Pies" << endl;
  73.            
  74.         }
  75.         it++;
  76.     }
  77. }
Add Comment
Please, Sign In to add comment