Show all threads Hide all threads Show all messages Hide all messages 
[n/m]==[n/(m+1)]  Wang Jia  1705. Gangster Hares  29 Dec 2014 20:39  5 
maybe the problem can be abstracted as the following one: n,m are integers, n given, find the smallest m such that [n/m]==[n/(m+1)] holds, where [] denotes the floor() function. well, anyone has any ideas? Yes, it's redefinition of problem. but how can i find such an m? a binary search does seems not to work... The binary search works. But it isn't a binary search by the answer. ;) I use binary search of answer in range Sqrt(n) and Sqrt(n) + Sqrt(Sqrt(n)) 
Any hints  VNXtreMe  1705. Gangster Hares  4 Jan 2012 14:46  1 
I got TLE on testcase 3 and I know test3 is testing near 10^18. Im using the square root method to solve the problem and the loop starts with the value from the square root function. However for numbers that are close to 10^18, the loop will run approximately 30,000 times and I know this is the problem with my solution. Can anyone tell me some ways that I could use to make the solution faster? btw I'm doing this in C++. Thanks :) 
Solution  Michail Yudin  1705. Gangster Hares  11 Sep 2011 17:01  10 
If you want to do it "as is" you got TLE. If you are in intellectual minority you got wa2. =) But how to solve it at 1 second? 10^18 input. approx. o(n) algo needed. please tell me an idea! Thx a lot. не понятен тест №2. Почему он не проходит. В процессе отладки понятно что прдлагаемые k не больше 20. Т.е. он должен проходить на ура. правильно ли я понял что: при k = 1 ответ 0 при k = 2 ответ 0 при k = 3 ответ 2 k=1 ответ 2 k=2 ответ 3 k=3 ответ 2 k=4 ответ 3 ... Edited by author 14.04.2009 23:48 Edited by author 14.04.2009 23:48 остроумно:))) всмысле имеется ввиду что зайцы могут получить и по 0 кочанов:)) спасибо, Вы правы. What test 3# Edited by author 17.08.2009 13:08 Edited by author 17.08.2009 13:08 О(1)??? It's very interesting, because my solution is in O(log n) operations. Could you explain this algorithm? Edited by author 25.10.2011 17:31 Edited by author 25.10.2011 17:31 
why time limit on test#3?  lolpwnZzzz  1705. Gangster Hares  22 Nov 2010 00:06  1 
my code: // 1705.cpp : Defines the entry point for the console application. // #include <iostream> using namespace std; double sqroot(double); int main() { int t; cin>>t; long long int input[50001]; long long int output[50001]; for(int i=0;i<t;i++) { scanf("%lli",&input[i]); long long int k=2; k=sqroot((double)input[i]); if(k<1) k = 1; while(true ) { if(input[i]/k==(input[i]/(k+1))) break; else k++; } output[i]=k; } for(int i=0;i<t;i++) printf("%lli\n",output[i]); return 0; } inline double sqroot(double n) { double begin=0; double end=n; double res=0; double precision=0.1; while(endbegin>precision) { res=(begin+end)/2; if(res*res>n) end=res; else begin=res; } return res; } for n=10^18 loop execute about 30000 times May this be the couse of time limit?? 
WA#3 what is test 3.  xurshid_n  1705. Gangster Hares  19 Aug 2009 09:19  4 
Help Me Please. WA#2 what is test 2. My Code: import java.util.Scanner; public class Rubbits { public static void main(String[] args) { Scanner rb = new Scanner(System.in); int n = rb.nextInt(); long [] a = new long [n]; int i,j,k,m; for ( i = 0; i < n; i++) { a[i] = rb.nextInt(); } for ( i = 0; i <n; i++) { if (a[i]==1){ System.out.println("0");
} else if(a[i]==2) System.out.println("1"); else{ for ( j =2; j < a[i]; j++) { k =(int)a[i]/j; m = k*j; if (a[i]m>=k) { System.out.println(j); break; } }
} } } } test #2 n=1 output 2 n=2 output 3 n=3 output 2 
WA #4 HELP ME  Quyon  1705. Gangster Hares  19 Aug 2009 09:16  1 

how about n=1?  TNT_wjx  1705. Gangster Hares  19 Aug 2009 09:14  9 
I think when n=1 k must be 0 no it is not 2 it is 0 you were not understand the problem Edited by author 04.04.2009 20:34 Then why does my AC program output 2??? k cannot be 0 because we cannot divide on it. There will be no answer on question "How much heads of cabbage receive each hare?" because even 1=0*1000000+1 is true. The answer is 2 because for 1 we have 1/1=1 but 1/2=0. And for 2 we have 1/2=1/3=0. I'm sorry maby I was not understood the problem K is the minimum integer that [n/k]=[n/(k+1)] if n=1 then output 2 1/2=0 and 1/3=0 
Why I got wrong answer on test 6?  Bright  1705. Gangster Hares  16 Aug 2009 04:00  3 
Probably you should use your own sqrt function for 64bit integers. You shouldn't if you've got correct formula. 
TLE test 3!!!!  vk  1705. Gangster Hares  2 May 2009 16:38  5 
and i have the same mistake #include <iostream> using namespace std; int main() { int i,a,t,j,o[30004]; cin>>t; for(i=1;i<=t;i++) { cin>>a; for(j=1;j<=20;j++) { if(((a(a%j))/j)<=(a%j)) { o[i]=j; break; } } } for(i=1;i<=t;i++) { cout<<o[i]<<endl; } return 0; } I tried to solve the minimum K where (double)(n/k)(double)(n/(k+1)) < 1.0 and then I iterate on this min_k till find the answer which [n/k]==[n/(k+1)], but I got TLE on test 3. Is there any special test case which cause me to get TLE? Is there any special test case which cause me to get TLE? There is no special test case in this problem, just maximal test. t=30000. n are random near 10^18 for example in the range [10^1810^17, 10^18] 
I don't understand the problem statement.  Anonymous  1705. Gangster Hares  26 Apr 2009 21:57  3 
Just as title. Would somebody explain it to me without spoiling the problem? You have to find the minimum number k, which satisfy the condition (n div k) = (n div (k + 1)). Number n is given by the input. 
Admins, what are you doing?  Victor Barinov (TNU)  1705. Gangster Hares  5 Apr 2009 15:32  2 
Rejudging of the contest after the contest is a VERY BAD THING! I am SURE that a lot of people who found solution for problem F can find error and write own sqrt function for int64. BUT if you have not tests that fails this on the contest you CAN NOT do rejudge after IT. YOU CAN CHANGE THE DESCRIPTION OF THE PROBLEM TO SATISFY THE DATA SET BUT YOU CAN NOT CHANGE DATA SET! In this case results of the contest is not objective at all. Edited by author 05.04.2009 01:58 We apologize to all participants of the online contest whose submit during the contest lost AC verdict. Adding new tests to the problems of Timus Online Judge is a usual rule of this site, but we agree that the rejudge of the contest is not fair thing. I'll try to explain why we he had to rejudge this problem. Because of technical error only 3 first tests from this problem's test set were installed to the Timus Online Judge. Unfortunately we have found this error only after the contest was finished. Now this problem has all tests that were prepared for the contest by its author. No new tests were added as a result of investigation of AC solutions of the contest. 
How to solve it?  birrd  1705. Gangster Hares  5 Apr 2009 08:38  2 

I can't understand?  yaho0o0  1705. Gangster Hares  4 Apr 2009 13:43  1 
Why on the 1 test the corect answer is not 2 2 3 