Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <blockquote> <p>If we throw from floor 14 again, and it breaks, then we recurse. n(n+1)/2=k where k is now 13... but that gives us 4.815, if we ceil and that and add our previous drop we get 6, which is lower than the actual solution, so something here is wrong...</p> </blockquote> <p>What if it doesn't break? Then you have a three-egg problem with 86 floors, which takes maybe one drop less to solve than the 100-floor problem.</p> <p>Say you drop the first egg from the 50<sup>th</sup> floor. If it breaks, you have a two-egg problem with 49 floors, which takes up to 10 additional drops. So that would give you a worst-case of 11 drops (since if it doesn't break, the 50-floor three-egg problem takes at most 7 additional drops).</p> <p>If you choose the 37<sup>th</sup> floor for the first drop, if it breaks, you have a 36-floor two-egg problem, needing up to 8 additional drops. If it doesn't break, you have a 63-floor three-egg problem left. You want to solve that problem with at most 8 drops, so if the next drop breaks the egg, the remaining two-egg problem should be solvable in at most 7 drops, thus the highest floor you can choose for the second drop is <code>37 + 28 + 1 = 66</code>, since 28 floors is the highest you can solve with at most 7 drops and two eggs. If the egg doesn't break, you have a 34-floor three-egg problem with 7 drops left. The highest you can certainly solve with the remaining 6 drops if the egg breaks is 21 (6*7/2), so you can choose floor <code>66 + 21 + 1 = 88</code>. If the egg doesn't break, you have 12 floors left with 6 drops, which is already doable with only two eggs.</p> <p>Systematically, the highest number of floors you can certainly solve with <code>d</code> drops and <code>e</code> eggs is</p> <pre><code> / 1, if d == 1 F(e,d) = | d, if e == 1 \ F(e-1,d-1) + 1 + F(e,d-1), if e &gt; 1 and d &gt; 1 </code></pre> <p>If you have only one drop, you have no choice but to choose the lowest floor of which you do not yet know that the egg doesn't break. If that breaks it, and you tried a higher floor, you don't know the first floor to break the egg.</p> <p>If you have only one egg, you have to check every floor in order until the egg breaks or you run out of drops.</p> <p>Otherwise, if the first drop is from a floor higher than <code>F(e-1,d-1) + 1</code>, you possibly can't find the first breaking floor if the egg breaks. If the first drop is from a lower floor, you can't reach as high with <code>d-1</code> drops if the egg doesn't break, so the first drop should be from floor <code>F(e-1,d-1) + 1</code>. If it breaks, you can solve with the remaining <code>e-1</code> eggs and <code>d-1</code> drops by assumption. If not, you can solve for the next <code>F(e,d-1)</code> floors with the remaining drops and eggs.</p> <p>Conversely, to find how many drops you may need for <code>f</code> floors with <code>e</code> eggs, you have to find</p> <pre><code>D(e,f) = min { d | F(e,d) &gt;= f } </code></pre> <p>You can find that by calculating the <code>F(e,d)</code> matrix, or you can use dynamic programming:</p> <p>If you choose floor <code>s</code> for the first drop, if the egg breaks, you need up to <code>D(e-1,s-1)</code> drops to determine the floor. If the egg doesn't break, you need up to <code>D(e,f-s)</code> drops to determine the floor. So the worst case for choosing floor <code>s</code> for the first drop is</p> <pre><code>WC(s,e,f) = 1 + max { D(e-1,s-1), D(e,f-s) } </code></pre> <p>and the best of the worst case is</p> <pre><code>D(e,f) = minimum { WC(s,e,f) | 1 &lt;= s &lt;= f } </code></pre> <p>(where of course <code>D(e,0) = 0</code>).</p>
    singulars
    1. This table or related slice is empty.
    1. POThree egg proble​m
      singulars
      1. PTQuestion
    1. PTAnswer
    1. This table or related slice is empty.
    1. USDaniel Fischer
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. POThree egg proble​m
      singulars
      1. PTQuestion
    1. This table or related slice is empty.
    1. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    3. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    1. This table or related slice is empty.
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload