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Если я правильно понимаю, надо посчитать количество яиц, необходимых для поиска E бинаркой, а если оно окажется больше количества яиц в гнезде, то вывести количество этажей? 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)] 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 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 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.
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 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 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 .. 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? 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) 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; } 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, ... 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. 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? 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 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 Can anybody explain, why return fabs(Temp-floor(Temp))<1e-3; causes WA on test 3 and return Temp == floor(Temp); got AC ???? .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 |
|