CCO '98 P6 - Derek's Dilemma

View as PDF

Submit solution

Points: 12
Time limit: 1.0s
Memory limit: 64M

Problem types
Canadian Computing Competition: 1998 Stage 2, Day 2, Problem 3

There once were two sad people who were named, oddly enough, A and B. They were sad because they were always being talked about, often quite slanderously, in math problems by the callous, faceless mathematical institution. Whenever they would talk to other people, the mean people would say "Hey, I read about you! You're always collecting and losing apples, aren't you?" They could not get jobs, because the mean interviewers would say "Didn't I read that at one point you two were prisoners? Hmmm, this is a dilemma…"

While the author feels deeply for them, unfortunately, he lacks any semblance of an imagination and none of the other letters could make it, so he will be using them yet again. However, to prevent the standard misconceptions, please read the disclaimer.

A and B are playing a game. They have n tokens, inscribed with the numbers 1 to n. A takes token 1 and places it in one of two piles. B then takes token 2 and places it in one of the two piles. A does this with token 3, and so on, until the last player places token n in one of the two piles.

The numbers on the tokens in each of the piles are summed up, and A wins if the two totals are relatively prime. (Two numbers are relatively prime if there is no integer greater than 1 which evenly divides both of them) Otherwise, B wins. (Note: an empty pile has total 0, and every integer evenly divides 0)

Your goal is to figure out, if both A and B play perfectly, which one of them will win for a given n.

Note: This question is for the sole purpose of cruelty to participants of the CCC. Any resemblance to real or imagined persons, living or dead, is purely coincidental.

Input Specification

Several lines containing the number of tokens for different games to be analyzed. Each line consists of a single number n, 1 \le n \le 30, except for the last line, which contains the number 0.

Output Specification

For each non-zero n, you are to print out who will win the game (A or B) with n tokens, assuming both play as well as possible.

Sample Input

2
5
10
0

Sample Output

When n=2, B will win.
When n=5, A will win.
When n=10, A will win.

Comments

There are no comments at the moment.