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 you need to be in control. you are in control when you keep the first player in "loop". if you take number of buttons is 6, say, then the "loop" length is 3, i.e. if you take max number of buttons as 3 - 1 = 2, then whatever amount the first player takes you can keep them in loop. if they take first time 1, you take 2 - in sum 3, 3 - remaining, you are a winner. if they take 2 - you take 1, 3 remaining again - you are a winner. so, idea is to find the smallest divisor of a number > 2 & answer will be that - 1. hope that makes sense. Edited by author 18.01.2019 19:50 WLOG, let's break `k` elements of heap into block of length `d`. The numbers below are listed from 1, ..., k in their congruent modulo of `d`. [1, 2, ...., (d - 1), d], [1, 2, ...., (d - 1), d], ......(k / d) blocks. Here [..] is a block notation. B = #blocks of length `d` = (k / d) Basis: If B = 1, it's always true, as `first player` can pick whatever from 1, ..., (d - 1), `second player` always left with atleast 1 element by less then d to be picked. So `second player` player will greedily pick all remaining element in the block as an optimal move for his/her winning. Hypothesis: Let say it's true upto (B - 1) blocks that `second player` has taken the last element. Proof: If we have B block then since it is true for (B - 1) blocks we left with 1 block of element to pick and since `first player` is the who pick first in the last 1 block by using the `basis` we know that `second player` is always the winner. Hence, if we take the divisor of number of elements in the heap (k) we always end of with `second player` being the winner. Edited by author 07.06.2022 10:23 Edited by author 07.06.2022 10:23 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. 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 for j := 3 to sqrt(n) do will help you :) > for j := 3 to sqrt(n) do will help you :) will it? for sqrt(8) = 2.8, but answer should be 4 - 1 = 3 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? wtf i=k / 3; ?? If k%(l+1)==0 then 2nd have a chance to win. And 1st wins if k%(l+1)!=0 try it: for (l=3;k%l!=0;l++);; Edited by author 31.03.2017 14:34 Check your program for very big K. It helped me. Edited by author 31.03.2017 14:38 I got a WA because I think L can be 1 thnx man .. that should help 5 years later, same trap grabbing me :( what if k=7? Is l=2? No. Because we know that if k=3 then answer 2. So we can remove 3 buttons from bunch. And find answer for k=4, but answer for this input will be 3. So 2!=3 and such answer is wrong. So answer will be 6 (cause we can't divide it on groups answer for those we know). Can someone tell me what's wrong with this program? #include <stdio.h> int main(void) { int n; scanf("%d", &n); printf("%d\n", n-1); return 0; } 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))? I think one can get AC in 0.001 by giving solutions that have precalculated values for K = 3...10^8. 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 Numbers are read from stdin var n,i,j:longint; begin readln(n); if (n<=2)then begin writeln('0') ; halt; end; j:=trunc(sqrt(n)); for i:=3 to j do begin if (n mod i=0) then break; end; writeln(i-1); end. Can anybody tell me why? It seems rigth^Why ? It drives me crazy^ Edited by author 15.06.2008 14:10 Edited by author 15.06.2008 14:10 I think your j should be n div 2,and I promise it's not TLE.And you can define 'ans' to store the answer and let it equal n.That's all. zj_zcy, what if n = 3 ? Your program wrote 0, but right answer 2 The trouble is if n is big prime. Try this: 99999989 The answer is: 99999988. Think how to modify algorithm to catch big primes in factorization. Here it isn't necessary, but it will be useful. Your code will possibly fail for integers like 2*n,also for test cases where n is a prime number 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 I made the same, but WA on test 11. What's the matter? I see a solution in another topic, there used I64. Oh, don't tell me to use I64. 10^8 is involved to int. Why does not it work? <code> #include <stdio.h> int K; int L; int main() { scanf("%d", &K); L = 2; while (K%(L+1) != 0) { if ((L+1)*(L+1) > K) { printf("%d\n", K-1); return 0; } L++; } printf("%d\n", L); return 0; } </code> Edited by author 18.08.2011 03:22 At last. I undestood. Expression "if ((L+1)*(L+1) > K)" not correct, because we skip 2. Since for K=8, we return 7, when the correct answer is 3. Edited by author 18.08.2011 03:56 > I made the same No I see u didn't :) The actual solution is 5 lines, 4 of which are declarations and i/o Edited by author 27.11.2011 17:43 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 "l<100000000" Indeed, why? No, because for example k=2, answer l=1 doesn't satisfy condition 2<=l<k To Vovka: Look at problem constraints: K >= 3. I think so. Because N-1 could always be the right answer,but I don't know why I got wa #11 n-1 is the right answer, but the task want you to choose the minimal from all the answers 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 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. var i,k:longint; begin read(k); i:=k div 3; while(k mod i<>0) do i:=k div(k div i +1); write(k div i-1); end. Edited by author 19.05.2007 23:58 So fabulous. Excellent... After you found maximal divider of K you can found minimal devider of K.... Excellent solution... Explain this solution, please. I'm a beginning programmer, so I can't understand. |
|