xiaoyiming12's blog

By xiaoyiming12, history, 3 weeks ago, In English

The problem: Problem (Reserve link)

#include <bits/stdc++.h>
using namespace std;

int main() {
	int c, m, n;
	bool stan;
	cin >> c;
	while (c --) {
		stan = true;
		cin >> m >> n;
		if (m < n) swap(m, n);
		while (n && m / n == 1) {
			stan = !stan;
			m -= n;
			swap(m, n);
		}
		puts(stan ? "Stan wins" : "Ollie wins");
	}
	return 0;
}

It passes the example, but not accepted.

Please give a counterexample and fix the program.

  • Vote: I like it
  • -9
  • Vote: I do not like it

»
3 weeks ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by xiaoyiming12 (previous revision, new revision, compare).

»
3 weeks ago, hide # |
 
Vote: I like it +3 Vote: I do not like it

Your code fails when m % n == 0 the current player wins immediately by subtracting to 0, but your loop flips the turn anyway. Add m % n != 0 to the while condition btw

  • »
    »
    3 days ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    No.

»
3 days ago, hide # |
 
Vote: I like it +4 Vote: I do not like it

The algorithm is wrong.