Показать все ветки Спрятать все ветки Показать все сообщения Спрятать все сообщения |
WA#3 | sleepntsheep | 1705. Зайцы-бандиты | 1 мар 2024 14:01 | 1 |
WA#3 sleepntsheep 1 мар 2024 14:01 What is test 3? I tried 1 (output 2) 2 (output 3) 3 (output 2) All of those are correct... |
[n/m]==[n/(m+1)] | Wang Jia | 1705. Зайцы-бандиты | 29 дек 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. Зайцы-бандиты | 4 янв 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. Зайцы-бандиты | 11 сен 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. Зайцы-бандиты | 22 ноя 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(end-begin>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. Зайцы-бандиты | 19 авг 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. Зайцы-бандиты | 19 авг 2009 09:16 | 1 |
|
how about n=1? | TNT_wjx | 1705. Зайцы-бандиты | 19 авг 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. Зайцы-бандиты | 16 авг 2009 04:00 | 3 |
Probably you should use your own sqrt function for 64-bit integers. You shouldn't if you've got correct formula. |
TLE test 3!!!! | vk | 1705. Зайцы-бандиты | 2 май 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^18-10^17, 10^18] |
I don't understand the problem statement. | Anonymous | 1705. Зайцы-бандиты | 26 апр 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. Зайцы-бандиты | 5 апр 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. Зайцы-бандиты | 5 апр 2009 08:38 | 2 |
|
I can't understand? | yaho0o0 | 1705. Зайцы-бандиты | 4 апр 2009 13:43 | 1 |
Why on the 1 test the corect answer is not 2 2 3 |