Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /*
- Two players, S and T, are playing a game where they make alternate moves. S plays first.
- In this game, they start with an integer N. In each move, a player removes one digit from the
- integer and passes the resulting number to the other player. The game continues in this fashion until
- a player finds he/she has no digit to remove when that player is declared as the loser.
- With this restriction, its obvious that if the number of digits in N is odd then S wins otherwise T
- wins. To make the game more interesting, we apply one additional constraint. A player can remove a
- particular digit if the sum of digits of the resulting number is a multiple of 3 or there are no digits left.
- Suppose N = 1234. S has 4 possible moves. That is, he can remove 1, 2, 3, or 4. Of these, two of
- them are valid moves.
- • Removal of 4 results in 123 and the sum of digits = 1 + 2 + 3 = 6; 6 is a multiple of 3.
- • Removal of 1 results in 234 and the sum of digits = 2 + 3 + 4 = 9; 9 is a multiple of 3.
- The other two moves are invalid.
- If both players play perfectly, who wins?
- */
- #include<iostream>
- #include<algorithm>
- #include<string>
- #include<vector>
- using namespace std;
- bool prob(string &str1)
- {
- string str2 = str1;
- string str3 = str2;
- if (str1 == "") return false;
- for(int i=0; i<str2.size(); i++)
- {
- int counter = 0;
- str2.erase(i, 1);
- for (int j = 0; j < str2.size(); j++)
- counter = counter + str2[j] - '0';
- if (counter % 3 == 0) {
- str1 = str2; return true;
- }
- else str2 = str1;
- }
- return false;
- }
- int main()
- {
- int testcases; cin >> testcases;
- for (int i = 0; i < testcases; i++)
- {
- cout << "Case " << i+1 << ":";
- int arr[2] = { 0,1 };
- string str; cin >> str;
- while (prob(str))
- {
- arr[0] = 1 - arr[0]; arr[1] = 1 - arr[1];
- }
- if (arr[0] == 1)
- cout << "S\n";
- else cout << "T\n";
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement