Scalar Question

help
1

2 players r playing a game. They have A bundles of Pencils each of size B. The player who can’t make move loses. For each move, a person choses a bundle and divides into some number(more than 1) of equal bundles. The size of each bundle is integer and is no less than C.
1<=A<=10^5
1<=B,C<=10^9
Example:

A,B,C=4,8,6
Output: 0

A,B,C=1,9,2
Output: 1

Can anyone pls tell me the correct solution?

2

@chef_ka_baap, is contest ongoing or finished???

3

This is finished. I want help too in this.

4

Just a observation , If B has no factor between [C,B) ==>ans=0(can’t divide equally by 1st player).
if it has a factor ->. if (A is odd){return 1;} else {return 0;}
Can be proved easily . Ask me if you didn’t understand last line

5

Anybody understood Q->3 permutation wala Question??

6

@aloo08051999 but i think it will not work for A,B,C=5,92,10
I think B can’t be divided so ans is 0

7

Once a bundle has been split into separate bundles, can each of these split-out bundles be chosen by a player in a subsequent turn?

If so, sounds like a simple Sprague Grundy (with a hint of DP) problem to me.

Edit:

This Problem sounds really, really familiar - I think it’s one of these ones in disguise:

but I can’t see which one, just yet.

2 Likes
8

@ssjgz s bro. once one of the bundless of size B out of A are divided, they can also be divided by other person. There r many problems in hackrank. can u pls give the precise sol.?

9

B=92 can we divided into 4 equal parts of 23 each. And since A is odd ans will be 1. Basically in every case 1st person can play optimally to win in this test case.Sorry By mistake I wrote [C,sqrt(B)]. It is basically [C,B) . I did this question in contest and it worked fine…

10

@aloo08051999 ok but what if after dividing , the value is again divisible someother number ? Should we take prime factor ? Eg: A,B,C=1,16,2