Show all threads Hide all threads Show all messages Hide all messages |
Give me more tests | SK1 | 1223. Chernobyl’ Eagle on a Roof | 6 Oct 2022 21:42 | 10 |
I've got AC. If you have WA check 100 512. (Answer is 10) my programm gives a right answer 10 on 100 512 and though it doesn't pass 1 test Try this: 1 100 = 100 2 100 = 14 3 100 = 9 4 100 = 8 5 100 = 7 6 100 = 7 2 3 = 2 7 999 = 11 Ononism is the best way to pass your free time!!! Isn't it? Pops must die!!! ROCK FOREVER!!! Punks NOT dead!!! HM... IT's so interesting... Edited by author 30.11.2005 18:20 When I buy my wife, she was fifteen - she was nice, her vagin work well, and she was good at the plow. But one year later her voice go deep, she become hair on her chest, and her vagin hang like a sleeve of a wizard... Sad, isn't it? When I buy my wife, she was fifteen - she was nice, her vagin work well, and she was good at the plow. But one year later her voice go deep, she become hair on her chest, and her vagin hang like a sleeve of a wizard... Sad, isn't it? Баран! Edited by author 11.04.2014 14:21 |
Бинаркой считать количество яиц? | Артём | 1223. Chernobyl’ Eagle on a Roof | 6 Oct 2022 21:21 | 2 |
Если я правильно понимаю, надо посчитать количество яиц, необходимых для поиска E бинаркой, а если оно окажется больше количества яиц в гнезде, то вывести количество этажей? |
Huuh! I've AC! | PSV | 1223. Chernobyl’ Eagle on a Roof | 19 Feb 2022 11:50 | 4 |
First DP formula like 1 + min max (a[i - 1, k-1], a[n - i,k ]) is NOT GOOD! In pascal it gets TLE! Take more clever formula!!! You can simply optimize this formula, assuming that min and max are convex functions. or binary search the intersection of (e eggs, f-th floor) #define T1(i) c[e][(i)-1] #define T2(i) c[e-1][f-(i)] |
Why WA1? | ivan.filippov201608@gmail.com | 1223. Chernobyl’ Eagle on a Roof | 3 Nov 2021 00:00 | 1 |
Why WA1? ivan.filippov201608@gmail.com 3 Nov 2021 00:00 pls give me some tests,i don't know,what's wrong with my code #include<iostream> #define endl '\n' #define ll long long # define ld long double using namespace std; ll d[1100][1100]; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); #ifdef LOCAL freopen("input.txt","r",stdin); freopen("output.txt","w",stdout); #endif // LOCALfr int n,m; for (int i=1;i<=1000;i++) { for (int j=1;j<=1000;j++) { d[i][j] = d[i][j-1] + d[i - 1][j - 1] + 1; } } n=1;m=1; while (n && m) { cin>>n>>m; if (n &&m) { int l=1,r=m+1000,mi; while (l<r) { mi=(l+r)/2; if (d[n][mi]>=m) { r=mi; } else l=mi+1; } cout<<l<<endl; } } return 0; } Edited by author 03.11.2021 00:01 Edited by author 03.11.2021 00:01 Edited by author 03.11.2021 00:01 |
AC 0.926 | kirdmiv | 1223. Chernobyl’ Eagle on a Roof | 4 Mar 2021 21:17 | 2 |
O(n^3) to calculate dp values. o(1) to answer query. dp[floors][eggs] -- answer. it enough to calculate in O(10*n^2) AC in 0.015sec |
Some thoughts about problem(can be considered as hint). | LaVuna [NULP] | 1223. Chernobyl’ Eagle on a Roof | 28 Nov 2020 14:06 | 1 |
I would suggest you to think about sumulating all possible situations like dropping eggs from first floor, from second, from third ,..., from n-th and we must choose then worst case scenario, but try to minimize that result.
|
Is the 1-st test like explanation test? (+) | bstu_student | 1223. Chernobyl’ Eagle on a Roof | 21 Aug 2018 03:51 | 1 |
Try to check some different algos and take WA1, but answeres for 1-10 and 2-5 is correct. P.S. have AC Edited by author 22.08.2018 03:10 |
An efficient solution | 2ch | 1223. Chernobyl’ Eagle on a Roof | 19 Mar 2018 20:39 | 1 |
Define d[i][j] to be the maximum number of floors that can be checked with i eggs after j steps. To answer the query one should do the binary search to find number of steps X such that d[input_eggs][X] >= input_floors with X being smallest possible. d[i][i] = i, d[2][5] = 15 ,d[2][6] = 21 ( 1 -> 6 -> 11 -> 15 -> 18 -> 20 -> 21 ) d[i][j] = d[i - 1][j] + d[i - 1][j - 1] + 1; Explanation of the formula: Suppose we know d[i][j - 1] and d[i - 1][j - 1] Throw an egg from (d[i - 1][j - 1] + 1) floor. Did it break? If yes, we can definitely check all floors from the first to d[i - 1][j - 1]th with remaining i - 1 eggs within remaining j - 1 steps. If it didn't then you just check how many floors you can check at most with i eggs within j - 1 steps starting from ((d[i - 1][j - 1] + 1) + 1) th floor d[i][j] can be calculated in N^2 Query is answered in log(N) time My Java 1.8 solution runs in 0.062s. Edited by author 19.03.2018 20:45 |
what is the so-called initial step for 2 eggs / 20 floors? | esbybb | 1223. Chernobyl’ Eagle on a Roof | 18 Mar 2016 03:06 | 10 |
spot check shows me that it should be 7 am i right? then the answer is 8 moves?? EGGS=2, FLOORS=20 (20 eggs, initial step = 7) e=20(20) 7 14 17 18 19 e=19(20) 7 14 17 18 19 (+7, +3) ...(e=18..14 ) e=13(20) 7 14 8 9 10 11 12 13 [7 moves] (20 eggs, initial step = 7) (20 eggs, initial step = 6) e=5(20) 6 1 2 3 4 5 e=17(20) 6 12 18 13 14 15 16 17 [8 moves] (20 eggs, initial step = 5) e=20(20) 5 10 15 18 19 20 e=17(20) 5 10 15 18 16 17 e=14(20) 5 10 15 11 12 13 14
(20 eggs, initial step = 4) 4 8 12 16 20 17 18 .. thanks! also what is the algorithm for this particular test case? thanks or maybe step is not fixed at all? like step0=7, step1=6, step2=5? +6 +5 +4 +3 6 11 15 18 5 6 1 2 3 4 5 10(or 11) 6 11 7 8 9 10 14(or 15) 6 11 15 12 13 14 17(or 18) 6 11 15 18 16 17 20 6 11 15 18 19 20 hmm for 2 eggs / 20 floors the answer is 6, this is weird Edited by author 16.03.2016 05:21 2eggs 100floors (14) +14 +13 +12 +11 +10 +9 +8 +7 14 27 39 41 52 62 71 80 88 95 39 14 27 39 28 29 30 31 32 33 34 35 36 37 38 100 14 27 39 41 52 62 71 80 88 95 96 97 98 99 IIRC for this task we need to save the last egg at all costs, until the moment we figure out the exact answer. For 2 eggs / 20 floors, that would be: 1st try: 6, and if breaks — 1, 2, 3, 4, 5 in worst case for last egg (so it breaks when we figure out the answer for sure). 2nd: 11, if breaks — 7, 8, 9, 10. 3rd: 14, if breaks — 11, 12, 13. 4th: 17, if breaks — 15, 16 5th: 19, if breaks — 18. 6th: 20 So in worst case, 6 tries. Then again, i didn't solve it yet, so i can't guarantee anything, but that's how i understood it from previous discussions. And yeah, you already described it above, i didn't read. Sorry. Edited by author 16.03.2016 06:26 the direction is right, step0 is the answer, for 2 eggs dunno for 3 eggs also coz i не решил еще тоже Well, intuitively, with 3 eggs we should put the first one in the middle, to minimize a floor quantity in worst case for remaining two eggs? intuitively this is DP problem with precomputing table of 1001x1001 cells row 1 contain values -1 1 2 3 4 5 .. row 2 contain values -1 1 2 2 3 3 .. row 3 ?? with 3 eggs we do move0 somewhere in the middle, doing loop from Eggs to 1, computing min(row1[step1]+row2[step22]) (or minimize step1+step2, maybe) for 3 eggs: for (step2=e; step2>1; step2--) for (step1=i2; step1>1; step1--) row 2 : -1 1 2 2 3 3 3 4 4 4 4 5 5 5 5 5 6 6 6 6 6 6 7 7 7 7 7 7 7 8 .. |
Hint | Vlad-Doru Ion | 1223. Chernobyl’ Eagle on a Roof | 25 Aug 2014 04:25 | 3 |
Hint Vlad-Doru Ion 13 Dec 2012 22:32 If your complexity is O(N^3) and your solution only gets AC in C/C++ then maybe you should print the matrix of where is best to drop the first egg. If your complexity is O(N^3) you can use the fact that when number of eggs >= log(N) , answer is log(N) . O(N^2*log(N)) . If your complexity is O(N^3) you can use the fact that when number of eggs >= log(N) , answer is log(N) . O(N^2*log(N)) . Keivan, that's such a good observation! Is that the intended solution though? |
Is my algorithm correct? If not give me a hint! | Vlad Ionescu | 1223. Chernobyl’ Eagle on a Roof | 29 Aug 2013 02:53 | 2 |
I thought that tha fastest way we could determine the floor was a binary search. For each i=1,n as long as we have enough eggs we do the binary search and stop when we visited both i and i-1. If we are left with only one egg we can't risk breaking without knowing the floor it so we start from the value just below the smallest value we know the egg hasn't broken and check all of them until we break the egg. For each binary search we count how many tests we did and just select the largest one (worst case). The complexity is O(N*log2 N). Is this correct or am I mistaken somewhere? And can anyone give me some test cases please? Yes, binary search is good when you have enough eggs. But what if you don't have enough eggs? Then when you have 1 egg left you need to check all floors, from 1st to the topmost floor. For example: Case eggs=100 and floors=100 Then you will do 7 experiments I will do 7 experiments too But case eggs=2 and floors=100 Then you will do about ~1+50 experiments But I will do 14 (i'm too lazy to write how, sorry) |
WA 1 | Invincible [MSU Tashkent] | 1223. Chernobyl’ Eagle on a Roof | 9 Aug 2011 14:34 | 1 |
WA 1 Invincible [MSU Tashkent] 9 Aug 2011 14:34 help me please, here's my code, I don't know why it always gets WA 1 #include <stdio.h> #include <stdlib.h> int findmax(int a, int b) {return (a>b ? a : b);} int mas[1001][1001]; int main(void) { int i,j,a,b,k,max,min; for (i=1;i<1001;i++) { mas[1][i]=1; mas[2][i]=2; mas[i][1]=i; } for (i=3;i<1001;i++) { for (j=2;j<1001;j++) { mas[i][j]=2000;
if (j>5) { if (mas[i][j-1]==mas[i][j-2]) {mas[i][j]=mas[i][j-1]; continue;} }
for (k=2; k<=i; k++) { max=findmax(mas[k-1][j-1],mas[i-k][j])+1; if (mas[i][j]!=2000 && max>mas[i][j]) break; if (max<mas[i][j]) {mas[i][j]=max; min=k;} } } } scanf("%d",&a); scanf("%d",&b);
while (a!=0 && b!=0) { printf("%d\n",mas[b][a]); scanf("%d",&a); scanf("%d",&b); } return 0; } |
I use dp and got ac!!!! | xiaoc | 1223. Chernobyl’ Eagle on a Roof | 26 Jun 2010 14:17 | 1 |
|
why answer for '2 100' is 14 ??? | MSU Teminator | 1223. Chernobyl’ Eagle on a Roof | 25 Jun 2010 09:05 | 3 |
my answer for '2 100' is 51 The first drop is from 14-th floor. If the egg is broken => F(1,13)+1=13+1=14 Than from 27-th floor If the egg is broken => F(1,27-14-1)+2=12+2=14 Than from 39-th floor If the egg is broken => F(1,39-27-1)+3=11+3=14 Than from 50-th floor, 60-th, 69-th, 77-th, 84-th, ... |
To admins: too weak tests | Alexey Shmelev [NNSU Top Lamers] | 1223. Chernobyl’ Eagle on a Roof | 24 Aug 2009 13:11 | 2 |
Hello! I believe, accepted solution 1851664 will get WA on several tests (e.g. "2 1000"). This test ("2 1000") is the most difficult test for some kind of solutions. Probably, it is necessary to retest this problem with harder tests. Thanks! Some new tests were added. Read site news. |
what algorithm behind this? | Hong Jin | 1223. Chernobyl’ Eagle on a Roof | 23 Nov 2008 15:21 | 1 |
Can anyone explain to me what is the algorithm behind this and how to use dp to solve this? why does binary search not work? |
No subject | Alias aka Alexander Prudaev | 1223. Chernobyl’ Eagle on a Roof | 12 May 2008 18:41 | 2 |
No subject Alias aka Alexander Prudaev 10 May 2008 19:49 i dont understand the problem. what mean first number in input? why we cant professor can't use binary search in first example? F(1, 10) = 10 why ? i think we 7 is more than we need. Because 1 egg may be broken before bin search finishing With 1 egg we cannot admit any risk therfore must go from 1 floor to 10 Edited by author 12.05.2008 18:53 |
Don't ever submit with freopen! | LSBG | 1223. Chernobyl’ Eagle on a Roof | 25 Mar 2008 23:45 | 2 |
I just spent about 40 minutes trying to find an unexisting bug in my code(I got WA 1), while the only bug I actually had was that I submitted with freopen! just use something like this #ifedf _DEBUG freopen() #endif or #ifndef ONLINE_JUDGE freopen() #endif |
return fabs(Temp-floor(Temp))<1e-3; | .Net, Java - any pcode sucks | 1223. Chernobyl’ Eagle on a Roof | 1 May 2007 22:03 | 1 |
Can anybody explain, why return fabs(Temp-floor(Temp))<1e-3; causes WA on test 3 and return Temp == floor(Temp); got AC ???? |
WHY TLE | PSV | 1223. Chernobyl’ Eagle on a Roof | 26 Oct 2006 03:41 | 1 |
.const . max = 1010; . oo = 3000; .var . n, k, i, j, maxn, maxk, top : word; . a : array [0..max, 0..max] of word; . sk, sn : array [1..max] of word; .procedure f(n, k : word); .var . i : word; .begin . if a[n, k] <> 0 then exit; . a[n, k] := oo; . for i := 1 to n do begin . if a[i - 1, k - 1] = 0 then f(i - 1, k - 1); . if a[n - i, k] = 0 then f(n - i, k); . if a[i - 1, k - 1] > a[n - i, k] then begin . if a[n, k] > a[i - 1, k - 1] then a[n, k] := a[i - 1, k - 1]; . end else begin . if a[n, k] > a[n - i, k] then a[n, k] := a[n - i, k]; . end; . end; . inc(a[n, k]); .end; .begin . read(k); . if k <> 0 then readln(n); . top := 0; . while k <> 0 do begin . inc(top); . sk[top] := k; . sn[top] := n; . if k > maxk then maxk := k; . if n > maxn then maxn := n; . read(k); . if k <> 0 then readln(n); . end; . for i := 1 to maxn do a[i, 1] := i; . for i := 1 to maxk do a[1, i] := 1; . for i := 1 to top do begin . f(sn[i], sk[i]); . writeln(a[sn[i], sk[i]]); . end; .end. I use recursive DP. And I think it's right. Why fuckin TLE? I also tried not recursive... Both have TLE Edited by author 26.10.2006 03:43 |