fork(1) download
copy 
  1. #include <iostream>
  2. #include <vector>
  3.  
  4. using namespace std;
  5.  
  6. template <typename T> void PrintVector(vector<T> vec){
  7.     cout << "[";
  8.     for (typename vector<T>::iterator it = vec.begin(); it != vec.end(); it++) {
  9.         if (it != vec.begin())
  10.             cout << ", ";
  11.         cout << *it;
  12.     }
  13.     cout << "]" << endl;
  14. }
  15.  
  16. // class : make combination
  17. // set numArray that you want to make combination
  18. // call Reset() at first
  19. // call Next() to make combination of numArray. result is set to comArray
  20. // return value of Next() is 0 ==> no more combination
  21. // Print() : print comArray (current combination)
  22. template <typename T> class Combination {
  23.   private:
  24.     vector<int> comParam;
  25.   public:
  26.     vector<T> numArray;
  27.     vector<T> comArray;
  28.  
  29.     Combination() {}
  30.     Combination(vector<T> a) { numArray = a; }
  31.  
  32.     int Reset() {
  33.         int size = numArray.size();
  34.         comParam.clear();
  35.         for (int i = 0; i < size; i++) {
  36.             comParam.push_back((i == 0) * size);
  37.         }
  38.         comArray = numArray;
  39.         return 0;
  40.     }
  41.  
  42.     int Next() {
  43.         int size = comParam.size();
  44.         int pos, carry;
  45.  
  46.         pos = size - 1;
  47.         carry = 1;
  48.         while (carry && (pos >= 0)) {
  49.             comParam[pos] = comParam[pos] - carry;
  50. 	        if (comParam[pos] < 0) {
  51. 	            comParam[pos] = size - pos - 1;
  52. 	            carry = 1;
  53. 	            pos --;
  54. 	        } else {
  55. 	            carry = 0;
  56. 	        }
  57.         }
  58.         if (pos < 0) return 0;
  59.  
  60.         comArray = numArray;
  61.         for (int i = 0; i < size; i++) {
  62.             T tmp = comArray[i];
  63.             comArray[i] = comArray[i + comParam[i]];
  64.             comArray[i + comParam[i]] = tmp;
  65.         }
  66.         return 1;
  67.     }
  68.  
  69.     void Print() {
  70.         PrintVector<T>(comArray);
  71.     }
  72. };
  73.  
  74. class BilliardProblem : private Combination<int> {
  75.   public:
  76.     vector<int> ballArray;   // ball number list
  77.     int ballNum;    // number of ball
  78.     int ballSum;    // sum of all ball ( sum = n * (n - 1) + 1 )
  79.  
  80.     BilliardProblem(int n) {
  81.         ballNum = n;
  82.         ballSum = n * (n - 1) + 1;
  83.         ballArray.clear();
  84.  
  85.         // make initial ball list
  86.         int sum = 0;
  87.         for (int i = 1; i <= n - 1; i++) {
  88.             ballArray.push_back(i);
  89.             sum += i;
  90.         }
  91.         ballArray.push_back(ballSum - sum);
  92.     }
  93.  
  94.     // find next ball list
  95.     int Next() {
  96.         int pos;
  97.  
  98.         pos = ballNum - 1;
  99.         if (pos <= 2) return 0;
  100.         ballArray[pos-1] = ballArray[pos-1] + 1;
  101.         ballArray[pos] = ballArray[pos] - 1;
  102.         if (ballArray[pos-1] >= ballArray[pos]) {
  103.             pos--;
  104.             while (pos > 2) {
  105.                 ballArray[pos-1] = ballArray[pos-1] + 1;
  106.                 for (int i = pos; i < ballNum - 1; i++) {
  107.                     ballArray[i] = ballArray[i-1] + 1;
  108.                 }
  109.                 int sum = 0;
  110.                 for (int i = 0; i < ballNum - 1; i++) {
  111.                     sum += ballArray[i];
  112.                 }
  113.                 ballArray[ballNum - 1] = ballSum - sum;
  114.                 if (ballArray[ballNum - 1] > ballArray[ballNum - 2]) {
  115.                     return 1;
  116.                 } else {
  117.                     pos--;
  118.                 }
  119.             }
  120.             return 0;
  121.         }
  122.         return 1;
  123.     }
  124.  
  125.     // check all combination of ball list
  126.     int Check() {
  127.         int nExist = 0;
  128.         int count  = 0;
  129.  
  130.         numArray = ballArray;
  131.         Combination::Reset();
  132.         while (Combination::Next()) {
  133.             // sum check
  134. 	        for (int n = 1; n <= ballSum / 2 + 1; n++) {
  135. 	            nExist = 0;
  136. 		        for (int i = 1; i <= ballNum; i++) {
  137. 		            for (int j = 0; j < ballNum; j++) {
  138. 		                int sum = 0;
  139. 		                for (int k = 0; k < i; k++) {
  140. 		                    sum += comArray[(j + k) % ballNum];
  141. 		                }
  142. 		                if (n == sum) {
  143. 		                    nExist = 1;
  144. 		                    break;
  145. 		                }
  146. 		            }
  147. 		            if (nExist == 1) break;
  148. 		        }
  149. 		        if (nExist == 0) break;
  150. 		    }
  151. 		    // combination found then print combination
  152. 		    if (nExist) {
  153. 		        Combination::Print();
  154. 		        count++;
  155. 		    }
  156. 		}
  157. 		return count;
  158.     }
  159.  
  160.     // print ball list
  161.     void Print() {
  162.         PrintVector<int>(ballArray);
  163.     }
  164. };
  165.  
  166. int main(void) {
  167.  
  168.     BilliardProblem *ballSet;
  169.     int     count;
  170.  
  171.     for (int ball = 1; ball <= 7; ball++) {
  172.  
  173.         ballSet = new BilliardProblem(ball);
  174.  
  175. 	    cout << "===============================================" << endl;
  176. 	    cout << "Check " << ball << " balls.";
  177. 	    cout << "  ( 1 - " << ballSet->ballSum << " )" << endl;
  178.  
  179. 	    count = 0;
  180. 	    do {
  181. 	        count += ballSet->Check();
  182. 	    } while (ballSet->Next());
  183.  
  184. 	    cout << count <<  " ways found, ";
  185. 	    cout << "include combination of mirror and rotation." << endl;
  186. 	    cout << "(" << count / ball / ((ball <= 2 ) ? 1 : 2);
  187. 	    cout << " ways without mirror and rotation)" << endl;
  188.  
  189. 	    delete ballSet;
  190. 	}
  191.  
  192.     return 0;
  193. }
  194.  
  195.  
Success #stdin #stdout 1.51s 3232KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
===============================================
Check 1 balls.  ( 1 - 1 )
[1]
1 ways found, include combination of mirror and rotation.
(1 ways without mirror and rotation)
===============================================
Check 2 balls.  ( 1 - 3 )
[2, 1]
[1, 2]
2 ways found, include combination of mirror and rotation.
(1 ways without mirror and rotation)
===============================================
Check 3 balls.  ( 1 - 7 )
[4, 1, 2]
[4, 2, 1]
[2, 4, 1]
[2, 1, 4]
[1, 4, 2]
[1, 2, 4]
6 ways found, include combination of mirror and rotation.
(1 ways without mirror and rotation)
===============================================
Check 4 balls.  ( 1 - 13 )
[7, 1, 3, 2]
[7, 2, 3, 1]
[3, 1, 7, 2]
[3, 2, 7, 1]
[2, 7, 1, 3]
[2, 3, 1, 7]
[1, 7, 2, 3]
[1, 3, 2, 7]
[6, 4, 1, 2]
[6, 2, 1, 4]
[4, 6, 2, 1]
[4, 1, 2, 6]
[2, 6, 4, 1]
[2, 1, 4, 6]
[1, 4, 6, 2]
[1, 2, 6, 4]
16 ways found, include combination of mirror and rotation.
(2 ways without mirror and rotation)
===============================================
Check 5 balls.  ( 1 - 21 )
[10, 3, 1, 5, 2]
[10, 2, 5, 1, 3]
[5, 1, 3, 10, 2]
[5, 2, 10, 3, 1]
[3, 10, 2, 5, 1]
[3, 1, 5, 2, 10]
[2, 10, 3, 1, 5]
[2, 5, 1, 3, 10]
[1, 5, 2, 10, 3]
[1, 3, 10, 2, 5]
10 ways found, include combination of mirror and rotation.
(1 ways without mirror and rotation)
===============================================
Check 6 balls.  ( 1 - 31 )
[14, 1, 7, 3, 2, 4]
[14, 4, 2, 3, 7, 1]
[7, 1, 14, 4, 2, 3]
[7, 3, 2, 4, 14, 1]
[4, 14, 1, 7, 3, 2]
[4, 2, 3, 7, 1, 14]
[3, 7, 1, 14, 4, 2]
[3, 2, 4, 14, 1, 7]
[2, 4, 14, 1, 7, 3]
[2, 3, 7, 1, 14, 4]
[1, 14, 4, 2, 3, 7]
[1, 7, 3, 2, 4, 14]
[14, 1, 3, 6, 2, 5]
[14, 5, 2, 6, 3, 1]
[6, 3, 1, 14, 5, 2]
[6, 2, 5, 14, 1, 3]
[5, 14, 1, 3, 6, 2]
[5, 2, 6, 3, 1, 14]
[3, 6, 2, 5, 14, 1]
[3, 1, 14, 5, 2, 6]
[2, 6, 3, 1, 14, 5]
[2, 5, 14, 1, 3, 6]
[1, 14, 5, 2, 6, 3]
[1, 3, 6, 2, 5, 14]
[10, 1, 3, 2, 7, 8]
[10, 8, 7, 2, 3, 1]
[8, 10, 1, 3, 2, 7]
[8, 7, 2, 3, 1, 10]
[7, 8, 10, 1, 3, 2]
[7, 2, 3, 1, 10, 8]
[3, 1, 10, 8, 7, 2]
[3, 2, 7, 8, 10, 1]
[2, 7, 8, 10, 1, 3]
[2, 3, 1, 10, 8, 7]
[1, 10, 8, 7, 2, 3]
[1, 3, 2, 7, 8, 10]
[13, 1, 2, 5, 4, 6]
[13, 6, 4, 5, 2, 1]
[6, 13, 1, 2, 5, 4]
[6, 4, 5, 2, 1, 13]
[5, 4, 6, 13, 1, 2]
[5, 2, 1, 13, 6, 4]
[4, 6, 13, 1, 2, 5]
[4, 5, 2, 1, 13, 6]
[2, 5, 4, 6, 13, 1]
[2, 1, 13, 6, 4, 5]
[1, 13, 6, 4, 5, 2]
[1, 2, 5, 4, 6, 13]
[12, 5, 1, 2, 7, 4]
[12, 4, 7, 2, 1, 5]
[7, 4, 12, 5, 1, 2]
[7, 2, 1, 5, 12, 4]
[5, 12, 4, 7, 2, 1]
[5, 1, 2, 7, 4, 12]
[4, 12, 5, 1, 2, 7]
[4, 7, 2, 1, 5, 12]
[2, 7, 4, 12, 5, 1]
[2, 1, 5, 12, 4, 7]
[1, 5, 12, 4, 7, 2]
[1, 2, 7, 4, 12, 5]
60 ways found, include combination of mirror and rotation.
(5 ways without mirror and rotation)
===============================================
Check 7 balls.  ( 1 - 43 )
0 ways found, include combination of mirror and rotation.
(0 ways without mirror and rotation)
https://ideone.com/hA1mFM
language:
C++ (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!