Колби


Submit solution


Points:100 (partial)
Time limit:1.0s
Memory limit:64M
Author:

Tags
Conditionals
Difficulty
Easy

Имало едно време един аптекар. Той продавал всякакви лекарства и отвари, които приготвял сам. Освен, че бил много вещ в тайните на лековете, той бил и много прецизен в съотношенията, които използвал. Един ден на местния панаир си купил една огромна кутия с N колби, които били еднакви по форма и цвят, но всяка следваща била по-голяма от предишните. На дъното на всяка от тях били изписани последователно числата от 1 до N. Аптекарят побързал да попита странният продавач как да разбере колко литра се събират във всяко от бурканчетата. Продавачът му казал: „Тези бурканчета са вълшебни. В първaта колба никога не поставяй нищо, тъй като колкото и да наливаш в нея тя ще е винаги празна. Всяка следваща колба събира толкова литри, колкото ако към номера на предишната колба прибавиш литрите, които събира предходната колба. И помни – счупиш ли колба с нечетен номер няма да се случи нищо, но счупиш ли колба с четен номер всички колби с четни номера ще изчезнат ”.

Не щеш ли докато мъкнел огромната кутия към къщи аптекарят се спънал, кутията се залюла и една от колбите се изтъркулила и се счупила. В миг всички колби, заедно с местата си с четни номера изчезнали. Аптекаря започнал да се вайка „ защо трябваше да падне точно колба с четен номер...”. Но накрая се прибрал и си казал „Е, не е чак толкова лошо. Все пак ми останаха всички нечетни колби”.

Години наред, пък и до ден днешен наливал приготвената отвара в колба, която му се виждала приблизително равна на количеството, което е приготвил. За нещастие отварите му взаимодействат с остатъчния въздух в колбите и се развалят. За да не се случва това, аптекарят трябва да намери най-малката колба, която събира количеството приготвена отвара.

Помогнете на горкия аптекар като напишете програма, която извежда номерът на търсената колба.

Ограничения

N <= 1 000 000

Вход

Броят на колбите и количеството на отварата. Отварата винаги се събира в поне една от колбите (т.е. винаги има решение).

Изход

Номерът на най-малката колба, която побира отварата

Примери

Вход Изход Обяснение
10 5 5 Най-малката колба, която можем да ползваме е 4, но тя е с четен номер и за това избираме следващата по-големина.

Comments


  • 1
    kiketo
     commented on Oct. 24, 2018

    На тест 7,10 и 11 ми дава грешни отговори. Може ли да напишите какви са входните данни за да го тествам локално?


  • 0
    lssah
     commented on Sept. 27, 2018

    В примера, който е даден в условието на задачата пише, че колба 4 би трябвало да може да побере 5 литра, но по шаблона за изчисляване на капацитета на колбите аз изкарвам, че 4-та колба би трябвало да събира 4 литра. Капацитетът на 4та колба е равен на номера на предходната(3) и на капацитетът на още по-предходната, което е колба 2, която е с капацитет 1. Така аз изкарвам, че капацитетът на колба 4 трябва да е също 4, а в пояснението към примерния изход пише друго. Явно нещо погрешно изчислявам капацитета на колбите. Някаква насока?


    • 1
      I.kunev1974
       commented on Sept. 28, 2018

      Здравей. Капацитетът на всяка колба е равен на капацитета на предходната колба плюс номера на предходната колба, както е по условие. Колба № 1 побира 0 литра. Колба № 2 побира 1 литър (№ на колба 1 + литрите на колба 1) Колба № 3 побира 3 литра (№ на колба 2 + литрите на колба 2) Колба № 4 побира 6 литра (№ на колба 3 + литрите на колба 3) и т.н.


      • 0
        lssah
         commented on Oct. 3, 2018

        Да, схванах, благодаря много. Бях се объркал, че се взима номерът на предходната и се сумира с литрите на ПО-предходната :)


  • 1
    plamen.hhh
     commented on Sept. 10, 2018

    Определено не беше easy тая задача.


  • -1
    3akobah
     commented on July 2, 2018 edit 9

    И при мен гърми на три теста(Java) с IR, а решението е на три реда, без цикли - едно просто квадратно уравнение и толкова. Не знам къде може да се сбърка.

    EDIT: Оказа се, че количеството течност, което ни подават може да не е цяло число. Ако на някой му е интересно как адачата се решава на 1 ред може да погледне в GitHub-a ми. :)


  • 0
    neobg2002
     commented on July 1, 2018

    Много тъжно и на мен ми връща IR на три теста!!! На Java съм и не съм наясно особено с (java.lang.NumberFormatException). Нямам парсване на стрингове само интове ползвам в случая и все пак е греда 3/10 теста гърмя. Малко насоки ще са от полза искам ги тия три теста :))).


  • 0
    stoychevamaria89
     commented on June 29, 2018

    Здравейте!

    Решавам на C# и всички тестове, които си измисля, включително примерния, на Visual Studio ми дават верен отговор. Когато си предам решението обаче, ми връща "Invalid Return". Какво означава това?

    Благодаря!


  • 0
    ivo.georgiev.varna
     commented on June 10, 2018 edited

    Някой админ би ли погледнал какво не е наред с решението ми със PHP. При мен работи, но в системата ми дава incorrect response на test case 9,10,11. Когато пробвам на localhost със по големичък N ми дава грешка PHP. Fatal error: Allowed memory size of 134217728 bytes exhausted (tried to allocate 36 bytes). Това ли е причината и тук? Пробвах със ini_set('memory_limit', '-1'); но не става тук.


  • 0
    pavel.atanasov2001
     commented on Jan. 14, 2018

    По колко литра се пишат първите две колби?


    • 1
      iordanbalt
       commented on April 19, 2018 edited

      Първата е 0 а втората е 1