If you pick n-1 as l then the second player will always win, so answer can never be 0
0 means  picked up the first player and 1 means picked up the second;
Case 1: 3 buttons
for i = 1 //doesn't make sense to solve for 1 since its asked to choose >=2
1 2 3
0 1 0 //first player won
for i = 2
1 2 3
0 0 1
0 1 1 // first play wins in each case
Case 2: 4 buttons
for i = 2
1 2 3 4
0 1 1 0
0 1 0 0 //first player wins in both these cases
for i = 3:
1 2 3 4
0 0 0 1
0 1 1 1
0 0 1 1 //second player wins in each case
case 3: 6 buttons (5 and 6 are similar)
1 2 3 4 5 6
for i = 2
0 1 1 0 0 1
0 0 1 0 0 1
0 1 1 0 1 1 //second player is  winning

It's clearly seen that the minimal choice to win is k such that n %(k+1) == 0
since n%((n-1)+1) is always 0, n-1 is always an answer in case no smaller answer exists.

I have seen many people solve this problem using divisor of given number(k).But i cannot understand how it works.Can anyone explain me how this logic works??

sorry for bad english

Check your program for very big K. It helped me.

Edited by author 31.03.2017 14:38

var
  i,n,l,j:longword; found:boolean;
begin
  readln(n);
  repeat
  found:=False;
  for j:=3 to n div 2 do
  begin
    if n mod j=0 then
    begin
      found:=True;
      break;
    end;
  end;
  if found then n:=j;
  until not found;
  writeln(n-1);
  readln;
end.

Please help me to optimize my code. It's 0.405 sec

what if k=7?
Is l=2?

How it is posible to get AC in 0.001 s? What time do such ACs take to get L for K= 99999989?
Could anyone give a hint to make it faster than O(sqrt(K))?

It's not a hard problem, if you use Sprague–Grundy theorem. But this solution is about 0.5 in best case. I saw some people getting AC in 0.015. What's the idea of their solution?

what is the test #7

Edited by author 18.08.2012 04:46

public class Buttons {
    public static void main(String[] args) {
        //convert parameter into int
        int N = 0;
        try {
            N = Integer.parseInt(args[0]);
        } catch(NumberFormatException ignore) {}
        //find L
        for(int i = 3; i < Math.sqrt(N); i++) {
          if(N%i == 0) {
            System.out.println(i-1);
        System.exit(1);
          }
    }
    System.out.println(N-1);
    }
}
P.S. On my computer it works perfectly

I got a WA because I think L can be 1

What is wrong answer 3?

Bash Game

Edited by author 20.07.2011 09:30

Edited by author 20.07.2011 09:31

var i,j:integer;
l,k,p,m:int64;

begin

  read(k);
  p:=0;
  l:=2;
    while l<100000000 do begin
      if k mod (l+1)=0 then begin
        write(L);
        halt;
      end else inc(l);
    end;
 write(0);

end.

Edited by author 05.05.2011 20:04

Edited by author 05.05.2011 20:04

var i,j:integer;
l,k,p,m:int64;

begin

  read(k);
  p:=0;
  l:=2;
    while p<>1 do begin
      m:=l+1;
      i:=0;
      while i<k do begin
        i:=i+m;
        p:=i;
      end;
      if p=k then begin
        write(L);
        halt;
      end else begin
        p:=0;
        inc(l);
      end;

    end;


end.

I really don't understand why is the answer is least divisor - 1.
Can anybody help?

In my pgm there's no '0'...
At least we can print(n-1) :)

with TL < 0.25 it's more interesting, and that's enough even for Java && C#

A - first divider of K, which is more or equal than 3 (A>=3)
We need write A-1.
AC - 0.578 and 134 KB

Edited by author 27.03.2010 14:34

Help somebody!!
Why my code has WA6..or GIVE SOME TESTS, please))

#include<iostream>
#include<vector>
#include<cmath>
using namespace std;

vector<int>easy_numbers(0);

int next_number(int numb_of_numb)
{
        int step=easy_numbers.size()-1;
        int curr_number=easy_numbers[step];
        while(step+1<numb_of_numb)
        {
                while(1)
                {
                        curr_number++;
                        int sq_root=sqrt(static_cast<double>(curr_number))+1;
                        int buf_step;
                        buf_step=0;
                        while(easy_numbers[buf_step]<sq_root)
                                if (curr_number%easy_numbers[buf_step++]!=0) continue;
                                else goto g1;
                        break;
                        g1:
                }
                easy_numbers.push_back(curr_number);
                step++;
        }
        return curr_number;
}

int main()
{
        int K;
        int L=-1;
        cin >> K;
        if (K==4) {cout << 3; exit(0);}
        easy_numbers.push_back(3);
        int buf=0;
        while((easy_numbers[buf]*easy_numbers[buf])<=K)
        next_number(++buf);
        for (int i=0;i<easy_numbers.size();i++)
        {
                if (K%easy_numbers[i]==0) {L=easy_numbers[i]-1; break;}

        }
        if (L==-1 && K%2==0) {L=K/2-1; cout << L;
        exit(0);}
        if (L==-1) {L=K-1; cout << L;
        exit(0);}
        cout << L;
        return 0;
}

When i write my program like:
#include<cstdio>
long long int i,k;
int main(){

scanf("%lld",&k);
i=k / 3;
while(k % i!=0){
i=k /(k / i +1);
}

i got AC,but when i change it to:

#include<cstdio>

int main(){
long long int i,k;
scanf("%lld",&k);
i=k / 3;
while(k % i!=0){
i=k /(k / i +1);
}
printf("%lld",(k / i-1));
}

printf("%lld",(k / i-1));
}
i got WA5...does anyoe know how is that possible?