Ah! I didn't realize that this is a published problem from the contest. My first approach (maybe not related to the initial question)
a) Put the next car of left lane b) If you cannot, put on the right on c) If you cannot, and free space on left + free space on right < length of the next car, it's done d) Exchange a set of cars from left lane with a set of cars from right lane, so one side has enough space to allocate the next car. (this is the tricky part, algorithm? dynamic programming?) e) go to a Angel "Java" Lopez @ajlopez On Mon, Jul 22, 2013 at 3:25 PM, Luke Pebody <[email protected]> wrote: > Sure, this means that at most 200 cars can fit on the ferry. But the > statement of the problem does not disallow a data set consisting of: > Line 1 - 1 > Line 2 - 100 > Lines 3-20,000,000 - 100 > Lines 20,000,001 - 0 > > > > On Mon, Jul 22, 2013 at 7:23 PM, Guilherme Puglia <[email protected]>wrote: > >> The first line of input contains a single integer between* 1 and 100: >> the length of the ferry* (in metres). >> >> For each car in the queue there is an additional line of input specifying >> the* length of the car* (in cm, an integer* between 100 and 10000 >> inclusive)*. >> >> Guilherme Puglia >> >> >> On Mon, Jul 22, 2013 at 3:17 PM, Luke Pebody <[email protected]>wrote: >> >>> Disagree. >>> >>> >>> On Mon, Jul 22, 2013 at 6:50 PM, Guilherme Puglia >>> <[email protected]>wrote: >>> >>>> You can imply it from the input constraints. >>>> >>>> Guilherme Puglia >>>> >>>> >>>> On Mon, Jul 22, 2013 at 2:49 PM, Angel Java Lopez < >>>> [email protected]> wrote: >>>> >>>>> Any limits in the number of cars? >>>>> >>>>> >>>>> On Mon, Jul 22, 2013 at 1:24 PM, ANUP SINGH >>>>> <[email protected]>wrote: >>>>> >>>>>> there is a queue of cars. we have to load the cars on ferry. there >>>>>> are two lanes on ferry. the car should be loaded in the order as they >>>>>> arrive. we are given ferry length and length of cars. we can load a car >>>>>> either on left lane or right lane. we have to load the cars in such a way >>>>>> that maximum cars can be loaded. >>>>>> >>>>>> Sorry my English is bad :) >>>>>> >>>>>> >>>>>> On Mon, Jul 22, 2013 at 9:45 PM, Guilherme Puglia < >>>>>> [email protected]> wrote: >>>>>> >>>>>>> I think you should find another subproblem. >>>>>>> >>>>>>> First, what do you need to answer? >>>>>>> >>>>>>> Second, Can you rewrite the original problem in order to simplify >>>>>>> it? I mean, do we really need to consider both lanes? >>>>>>> >>>>>>> Regards, >>>>>>> >>>>>>> Guilherme Puglia >>>>>>> >>>>>>> >>>>>>> On Mon, Jul 22, 2013 at 8:48 AM, anup1pma >>>>>>> <[email protected]>wrote: >>>>>>> >>>>>>>> for each car we can load it to left lane or right lane on the >>>>>>>> ferry. so there can be some overlapping sub problems. here ferry >>>>>>>> length can >>>>>>>> be 10000 cm. so array[10001][10001][n] is not possible, here n is >>>>>>>> number of >>>>>>>> cars. >>>>>>>> >>>>>>>> -- >>>>>>>> You received this message because you are subscribed to the Google >>>>>>>> Groups "Google Code Jam" group. >>>>>>>> To unsubscribe from this group and stop receiving emails from it, >>>>>>>> send an email to [email protected]. >>>>>>>> To post to this group, send email to [email protected]. >>>>>>>> To view this discussion on the web visit >>>>>>>> https://groups.google.com/d/msgid/google-code/2630e766-11d6-4d60-b16e-e2aca4917006%40googlegroups.com >>>>>>>> . >>>>>>>> For more options, visit https://groups.google.com/groups/opt_out. >>>>>>>> >>>>>>>> >>>>>>>> >>>>>>> -- >>>>>>> You received this message because you are subscribed to the Google >>>>>>> Groups "Google Code Jam" group. >>>>>>> To unsubscribe from this group and stop receiving emails from it, >>>>>>> send an email to [email protected]. >>>>>>> To post to this group, send email to [email protected]. >>>>>>> To view this discussion on the web visit >>>>>>> https://groups.google.com/d/msgid/google-code/CAKfgAVUPxu0cdDD-_yvgq9HcaYpsHjVe-vZ9LThY7aZ-0aixLg%40mail.gmail.com >>>>>>> . >>>>>>> >>>>>>> For more options, visit https://groups.google.com/groups/opt_out. >>>>>>> >>>>>>> >>>>>>> >>>>>> >>>>>> -- >>>>>> You received this message because you are subscribed to the Google >>>>>> Groups "Google Code Jam" group. >>>>>> To unsubscribe from this group and stop receiving emails from it, >>>>>> send an email to [email protected]. >>>>>> To post to this group, send email to [email protected]. >>>>>> To view this discussion on the web visit >>>>>> https://groups.google.com/d/msgid/google-code/CAJNr433TpGe%3DuWRbcqgnQSk6nQm68m1vb8Cp%3Dih4y1t93ofH1A%40mail.gmail.com >>>>>> . >>>>>> >>>>>> For more options, visit https://groups.google.com/groups/opt_out. >>>>>> >>>>>> >>>>>> >>>>> >>>>> -- >>>>> You received this message because you are subscribed to the Google >>>>> Groups "Google Code Jam" group. >>>>> To unsubscribe from this group and stop receiving emails from it, send >>>>> an email to [email protected]. >>>>> To post to this group, send email to [email protected]. >>>>> To view this discussion on the web visit >>>>> https://groups.google.com/d/msgid/google-code/CAMs%2BDqK0gUNhGsdS1Rs-FiHmLK0dp%3DxanK_unDyiyc5BWiQUyA%40mail.gmail.com >>>>> . >>>>> >>>>> For more options, visit https://groups.google.com/groups/opt_out. >>>>> >>>>> >>>>> >>>> >>>> -- >>>> You received this message because you are subscribed to the Google >>>> Groups "Google Code Jam" group. >>>> To unsubscribe from this group and stop receiving emails from it, send >>>> an email to [email protected]. >>>> To post to this group, send email to [email protected]. >>>> To view this discussion on the web visit >>>> https://groups.google.com/d/msgid/google-code/CAKfgAVUxX8MC3gCUeSiAMjr6aemSTiAqQZoz7jyEt2p_4NZusA%40mail.gmail.com >>>> . >>>> >>>> For more options, visit https://groups.google.com/groups/opt_out. >>>> >>>> >>>> >>> >>> -- >>> You received this message because you are subscribed to the Google >>> Groups "Google Code Jam" group. >>> To unsubscribe from this group and stop receiving emails from it, send >>> an email to [email protected]. >>> To post to this group, send email to [email protected]. >>> To view this discussion on the web visit >>> https://groups.google.com/d/msgid/google-code/CADat-GeadsPH1j3WGFWJJF5hwUv21uvqzu7Df7W2cpKtOU9uqA%40mail.gmail.com >>> . >>> >>> For more options, visit https://groups.google.com/groups/opt_out. >>> >>> >>> >> >> -- >> You received this message because you are subscribed to the Google Groups >> "Google Code Jam" group. >> To unsubscribe from this group and stop receiving emails from it, send an >> email to [email protected]. >> To post to this group, send email to [email protected]. >> To view this discussion on the web visit >> https://groups.google.com/d/msgid/google-code/CAKfgAVUF23PV_fXJLotvSyhf1C12MNqLaOnwJiYgT4K48_vfkg%40mail.gmail.com >> . >> >> For more options, visit https://groups.google.com/groups/opt_out. >> >> >> > > -- > You received this message because you are subscribed to the Google Groups > "Google Code Jam" group. > To unsubscribe from this group and stop receiving emails from it, send an > email to [email protected]. > To post to this group, send email to [email protected]. > To view this discussion on the web visit > https://groups.google.com/d/msgid/google-code/CADat-GdJ9NN77ztMJojf1yeT5C-V1L9erW74hNuWOiX1DLAYvQ%40mail.gmail.com > . > > For more options, visit https://groups.google.com/groups/opt_out. > > > -- You received this message because you are subscribed to the Google Groups "Google Code Jam" group. To unsubscribe from this group and stop receiving emails from it, send an email to [email protected]. To post to this group, send email to [email protected]. To view this discussion on the web visit https://groups.google.com/d/msgid/google-code/CAMs%2BDqLt09jWXXEx9%3Duc9J%3D_n3BtNgMz_WEU%3DtxsYHka4HyNVQ%40mail.gmail.com. For more options, visit https://groups.google.com/groups/opt_out.
