Если я правильно понимаю, надо посчитать количество яиц, необходимых для поиска 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!!!

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.

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??

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.

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?

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;
}

time复杂度是O(n log^2 n )

my answer for '2 100' is 51

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!

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.

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!

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