fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <sstream>
  4. #include <algorithm>
  5. #include <cmath>
  6. using namespace std;
  7.  
  8. /*****************************************************************************************
  9.  //  DevDraft 2014 Brian Ackermann Submission 2.0
  10.  //  TreeNode class represents a single node in the decision tree
  11.  //  Contains the current hand of the player's turn
  12.  //  left child, right child and possible middle child if this is the root of our tree
  13.  //  two static methods used to construct the decision tree
  14.  //  and to decide if player one can force a win (if not player 2 automatically wins)
  15.  ******************************************************************************************/
  16. class TreeNode{
  17.  
  18. public:
  19.     //public fields used to represent decision tree node
  20.     std::vector<double> hand;
  21.     TreeNode* left;
  22.     TreeNode* middle;
  23.     TreeNode* right;
  24.  
  25.     //Basic constructor to fill the player's hand
  26.     TreeNode(std::vector<double> arr)
  27.     {
  28.         this->hand = arr;
  29.     }
  30.  
  31.     /********************************************
  32.      //  constructTree static method
  33.      //  Input: TreeNode pointer, boolean
  34.      //  Output: nothing
  35.      //  Side-effects: Constructs decision tree
  36.      *********************************************/
  37.     static void constructTree(TreeNode* root, bool isRoot)
  38.     {
  39.         std::vector<double> leftHand, middleHand, rightHand;
  40.         std::vector<double> currHand = root->hand;
  41.  
  42.         //we've encountered a leaf node simply return
  43.         if(currHand[0] == currHand[1] && currHand[0] == currHand[2])
  44.         {
  45.             return;
  46.         }
  47.         //we've encountered a parent of a leaf node
  48.         else if(currHand[0] == currHand[1])
  49.         {
  50.             rightHand.push_back(currHand[0]);
  51.             rightHand.push_back(currHand[0]);
  52.             rightHand.push_back(currHand[0]);
  53.  
  54.             root->right = new TreeNode(rightHand);
  55.             constructTree(root->right, false);
  56.         }
  57.  
  58.         else if(currHand[1] == currHand[2])
  59.         {
  60.             leftHand.push_back(currHand[1]);
  61.             leftHand.push_back(currHand[1]);
  62.             leftHand.push_back(currHand[1]);
  63.  
  64.             root->left = new TreeNode(leftHand);
  65.             constructTree(root->left, false);
  66.         }
  67.         //We're at the root of our tree, three branches must be made
  68.         else
  69.         {
  70.             if(isRoot)
  71.             {
  72.                 if(currHand[0] != std::floor((currHand[1]+currHand[2])/2))
  73.                 {
  74.                     leftHand.push_back(currHand[1]);
  75.                     leftHand.push_back(std::floor((currHand[1]+currHand[2])/2));
  76.                     leftHand.push_back(currHand[2]);
  77.                     root->left = new TreeNode(leftHand);
  78.                     constructTree(root->left, false);
  79.                 }
  80.                 else
  81.                     return;
  82.  
  83.                 if(currHand[1] != std::floor((currHand[0]+currHand[2])/2))
  84.                 {
  85.                     middleHand.push_back(currHand[0]);
  86.                     middleHand.push_back(std::floor((currHand[0]+currHand[2])/2));
  87.                     middleHand.push_back(currHand[2]);
  88.                     root->middle = new TreeNode(middleHand);
  89.                     constructTree(root->middle, false);
  90.                 }
  91.                 else
  92.                     return;
  93.  
  94.                 if(currHand[2] != std::floor((currHand[0]+currHand[1])/2))
  95.                 {
  96.                     rightHand.push_back(currHand[0]);
  97.                     rightHand.push_back(std::floor((currHand[0]+currHand[1])/2));
  98.                     rightHand.push_back(currHand[1]);
  99.                     root->right = new TreeNode(rightHand);
  100.                     constructTree(root->right, false);
  101.                 }
  102.                 else
  103.                     return;
  104.  
  105.             }
  106.         //we're at an interior node create two branches and recurse
  107.             else
  108.             {
  109.                 if(currHand[0] != std::floor((currHand[1]+currHand[2])/2))
  110.                 {
  111.                     leftHand.push_back(currHand[1]);
  112.                     leftHand.push_back(std::floor((currHand[1]+currHand[2])/2));
  113.                     leftHand.push_back(currHand[2]);
  114.                     root->left = new TreeNode(leftHand);
  115.                     constructTree(root->left, false);
  116.                 }
  117.                 else
  118.                     return;
  119.  
  120.                 if(currHand[2] != std::floor((currHand[0]+currHand[1])/2))
  121.                 {
  122.                     rightHand.push_back(currHand[0]);
  123.                     rightHand.push_back(std::floor((currHand[0]+currHand[1])/2));
  124.                     rightHand.push_back(currHand[1]);
  125.                     root->right = new TreeNode(rightHand);
  126.                     constructTree(root->right, false);
  127.                 }
  128.                 else
  129.                     return;
  130.             }
  131.         }
  132.     }
  133.  
  134.     /***************************************************************
  135.      // playerOneCanForceWin static method determines if player one
  136.      // can force a win if not player two must be able to
  137.      //
  138.      // Input: TreNode pointer, integer depth, bool
  139.      // Output: Boolean
  140.      // Side-effects: none
  141.      ***************************************************************/
  142.     static bool playerOneCanForceWin(TreeNode* root, int depth, bool isRoot)
  143.     {
  144.         //reached leaf node, if player one's turn return false
  145.         if(!root->left && !root->right)
  146.         {
  147.             if(depth%2 == 0)
  148.                 return false;
  149.             return true;
  150.         }
  151.         if(isRoot)
  152.         {
  153.             bool leftTurn = false;
  154.             bool rightTurn = false;
  155.             bool middleTurn = false;
  156.  
  157.             if(root->left)
  158.             {
  159.                 leftTurn = playerOneCanForceWin(root->left, depth+1, false);
  160.             }
  161.             else
  162.             {
  163.                 leftTurn = true;
  164.             }
  165.             if(root->right)
  166.             {
  167.                 rightTurn = playerOneCanForceWin(root->right, depth+1, false);
  168.             }
  169.             else
  170.             {
  171.                 rightTurn = true;
  172.             }
  173.             if(root->middle)
  174.             {
  175.                 middleTurn = playerOneCanForceWin(root->middle, depth+1, false);
  176.             }
  177.             else
  178.             {
  179.                 middleTurn = true;
  180.             }
  181.  
  182.             if(leftTurn || rightTurn || middleTurn)
  183.                 return true;
  184.             else
  185.                 return false;
  186.         }
  187.         //we're at an interior player 1 node, check if either route returns true
  188.         else if(depth%2 == 0)
  189.         {
  190.             bool leftTurn = false;
  191.             bool rightTurn = false;
  192.  
  193.             if(root->left)
  194.             {
  195.                 leftTurn = playerOneCanForceWin(root->left, depth+1, false);
  196.             }
  197.             else
  198.             {
  199.                 leftTurn = true;
  200.             }
  201.             if(root->right)
  202.             {
  203.                 rightTurn = playerOneCanForceWin(root->right, depth+1, false);
  204.             }
  205.             else
  206.             {
  207.                 rightTurn = true;
  208.             }
  209.  
  210.             if(leftTurn || rightTurn)
  211.                 return true;
  212.             else
  213.                 return false;
  214.         }
  215.         //we're at an interior player 2 node, check if both routes return true (both must or else player two can force a win)
  216.         else
  217.         {
  218.             bool leftTurn = false;
  219.             bool rightTurn = false;
  220.  
  221.             if(root->left)
  222.             {
  223.                 leftTurn = playerOneCanForceWin(root->left, depth+1, false);
  224.             }
  225.             else
  226.             {
  227.                 leftTurn = true;
  228.             }
  229.             if(root->right)
  230.             {
  231.                 rightTurn = playerOneCanForceWin(root->right, depth+1, false);
  232.             }
  233.             else
  234.             {
  235.                 rightTurn = true;
  236.             }
  237.  
  238.             if(leftTurn && rightTurn)
  239.                 return true;
  240.             else
  241.                 return false;
  242.         }
  243.     }
  244.  
  245.     ~TreeNode()
  246.     {
  247.         delete left;
  248.         delete middle;
  249.         delete right;
  250.     }
  251. };
  252.  
  253. int main() {
  254.     //read in standard input parse into hand and call premade functions
  255.     std::string tmp;
  256.     while(std::getline(std::cin, tmp)){
  257.         std::vector<double> nums;
  258.         std::stringstream ss(tmp);
  259.         int ti;
  260.         while(ss >> ti)
  261.             nums.push_back(ti);
  262.  
  263.         if(nums.size() != 1)
  264.         {
  265.             TreeNode* root = new TreeNode(nums);
  266.             TreeNode::constructTree(root, true);
  267.             if(TreeNode::playerOneCanForceWin(root, 0, true))
  268.                 cout << "First\n";
  269.             else
  270.                 cout << "Second\n";
  271.         }
  272.     }
  273.     return 0;
  274. }
Runtime error #stdin #stdout 0s 3492KB
comments (?)
stdin
copy 
42 58 79
92 89 96
49 21 55
64 67 97
43 25 31
33 46 69
34 45 14
90 88 29
40 13 62
98 14 33
65 38 33
35 73 19
12 80 15
31 77 43
84 78 68
28 25 19
16 97 14
57 39 56
63 80 19
28 25 72
86 14 11
34 39 97
44 20 60
62 80 53
11 70 82
78 61 63
87 30 55
94 81 55
46 94 20
91 81 92
12 35 99
65 59 15
23 32 59
20 55 44
40 70 15
64 35 28
30 60 53
62 33 97
stdout
copy 
Standard output is empty
https://ideone.com/A5gwP8
language:
C++14 (gcc 8.3)
created:
9 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!