Да те пратят за… пастички

Ето ви пример за една много лесничка задачка, наречена „Пастички“, дадена съвсем наскоро на изпита по JavaScript в Телерик Академия, след уводния курс:

AniG обича сладички неща, особено пастички. Обича и парички да харчи. Разполага със сумата от S лева и би похарчила максимума от нея. Има 3 любими типа пастички: първият струва C1 лева, вторият C2 лева, а третият C3 лева. В магазина пастичките са безброй, но AniG има само S лева.

Условието: AniG трябва да похарчи максимално много от парите си, за да си купи от любимите пастички. Открийте, каква е максималната сума пари (която не надвишава S), която AniG може да похарчи за пастички. 

Входни данни

Входните данни се прочитат от конзолата. На първия ред е дадена сумата S. На втория, третия и четвъртия ред са дадени стойностите C1, C2 и C3. Входните данни ще са винаги валидни и в описания формат. Няма нужда да ги проверявате специално.

Изходни данни

Изходните данни трябва да бъдат отпечатани на конзолата. Отпечатайте най-голямото възможно количество, което AniG може да похарчи.

Как трябва да изглежда решението ви (на JavaScript) 

function solve(params){
  var s = params[0],
     c1 = params[1],
     c2 = params[2],
     c3 = params[3];
     varanswer = 0;
  // Your solution here
  console.log(answer);
}

Ограничения

  • Числото за S е между 1 и 7000, включително.
  • Стойностите за C1, C2 и C3 са между 11 и 7000.
  • Позволено време за работа на програмата ви: 0.1 секунди.
  • Позволена памет: 16 МВ.

Примери 

Тест 1

Тест 2

Тест 3

Входни данни Входни данни Входни данни

110

20 110

13

11

19

15

200

29

17

300

39

Изходни данни

Изходни данни Изходни данни

110

11

107

6 пастички на цена 13 1 пастичка на цена 11 0 пастички на цена 19
1 пастичка на цена 15 1 пастичка на цена 29
1 пастичка на цена 17 2 пастички на цена 39

 

Как се решава задачата без формули?

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

Какво ни казват ограниченията в условието? 

  1. Ограничението за разполагаемата сума S (от 1 до 7000) няма смисъл при нетипизиран език като JavaScript.

Ако това беше C#, щяхме да запазим стойността S в подходящ тип променлива. Освен това, от нас не се изисква да правим проверка на входните данни (по условие те винаги ще са коректни). Остава вариантът това ограничение да има общо с някоя формула, която да ни улесни в пресмятането, само че ние няма да ползваме такава.

  1. Същото важи и за стойностите на C1, C2 и C3.
  2. Времето за работа на програмата, както и паметта, ще варират, в зависимост от скоростта на операциите, които включваме.

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

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

Измисляне на решението

Можем първо да проверим дали в разполагаемата сума не се съдържат точен брой пастички от някой тип, така че да не остава „ресто“. Това обаче не изключва възможността сумата да може да се похарчи изцяло и с комбинация от пастички. По условие, не се иска от нас да извеждаме всички възможни комбинации с еднаква максимална сума (maxValue), достатъчно е да се посочи самата максимална сума.

За да намерим maxValue от разполагаемата S, трябва да разгледаме всички възможни комбинации с различни бройки от трите типа пастички. Сравняваме комбинациите, за да видим коя от тях максимално се доближава по стойност до S и я изписваме като резултат на конзолата:

  console.log(maxValue);

Максимално количество за всеки тип пастичка

В зависимост от цената на пастичката (Cx), ще варират и бройките, които можем да си купим. Диапазонът включва стойности от 0 до максималното количество (maxCx), което можем да купим за сумата S:

maxCx = S/Cx

Важно е да не забравяме, че maxValue може да се получи при комбиниране на различен брой пастички (currentCx) от:

  • всички видове – както се вижда от тест 1 от условието на задачата
  • два от видовете – както се вижда от тест 3 от условието на задачата
  • само един вид – както се вижда от тест 2 от условието на задачата

maxC1

maxC2

maxC3

0

0 0

0

0 currentC3

0

currentC2

0

currentC1

0

0

currentC1

0

currentC3

currentC1

currentC2

0

0

currentC2

currentC3

currentC1 currentC2

currentC3

 

Ако използваме като пример първите тестови входни данни, които са ни дадени, това означава:

  • maxC1 = S/C1 = 110/13 = 8.46 = 8 броя от пастичките на цена C1
  • maxC2 = S/C2 = 110/15 = 7.33 = 7 броя от пастичките на цена C2
  • maxC3 = S/C3 = 110/17 = 6.47 = 6 броя от пастичките на цена C3

Така вече имаме не само maxCx за всеки тип пастичка, но също можем да пресметнем и сумата, която би ни струвало даденото количество. Спрямо входните данни от първия тест, сумите са, както следва:

Брой пастички

0

1 2 3 4 5 6 7

8

Суми

C1x0

C1x1 C1x2 C1x3 C1x4 C1x5 C1x6 C1x7 C1x8

C2x0

C2x1 C2x2 C2x3 C2x4 C2x5 C2x6

C2x7

C3x0 C3x1 C3x2 C3x3 C3x4 C3x5 C3x6

 

Това са стойностите, които ще събираме, за да проверим кои комбинации между тях дават сума, по-малка от S и коя от тези комбинации е равна на или се доближава максимално до S.

Комбиниране на бройките

Преглеждането на всички възможни комбинации между бройките пастички може да се реализира чрез 3 цикъла, вложени един в друг:

cycles1

Записът би бил следният:

for (var i = 0; i <= maxC1; i++) {
   for (var j = 0; j <= maxC2; j++) {
     for (var k = 0; k <= maxC3; k++) {
     }
   }
}

Цикъл 1: обхожда възможните бройки при цена C1, броячът започва от i = 0 и върти, докато стане равен на maxC1

Цикъл 2 (вложен в цикъл 1): обхожда възможните бройки при цена C2, броячът започва от j = 0 и върти, докато стане равен на maxC2

Цикъл 3 (вложен в цикъл 2): обхожда възможните бройки при цена C3, броячът започва от k = 0 и върти, докато стане равен на maxC3

Броячите i, j и k пазят количеството пастички (от 0 до максималната бройка maxCx), като при всяка итерация на дадения цикъл броячът увеличава стойността си с единица. Всеки цикъл се изпълнява, докато броячът му не стане равен на максималната бройка от съответните пастички.

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

Запазване на общ разход

Стойността на количествата от трите типа пастички получаваме, като умножим цената на пастичката Cx по текущата бройка (i, j или k).

Нужна ни е променлива, в която да запазваме общия разход (currentValue) при комбинирането на различните бройки (i, j и k) пастички. За currentValue имаме няколко варианта, според това дали вътре участват всички типове пастички:

  • currentValue = C1*i;
  • currentValue = C2*j;
  • currentValue = C3*k;
  • currentValue = C1*i + C2*j;
  • currentValue = C1*i + C3*k;
  • currentValue = C2*j + C3*k;
  • currentValue = C1*i + C2*j + C3*k;

Следващата стъпка е да сравним общия разход с максималната сума, която търсим. Първоначално сме присвоили на maxValue стойност 0, тъй като това е минималната възможна стойност, която тя може да има (var maxValue = 0). Впоследствие при цикленето на сумите ще присвояваме на maxValue все по-голяма стойност, докато получим максималната.

Запазване на броя пастички

За всеки тип пастичка, можем да запазваме при цикленето с колко броя участва във формирането на maxValue. За целта, си декларираме три променливи currentCx:

var currentC1 = 0, // Amount of C1
    currentC2 = 0, // Amount of C2
    currentC3 = 0; // Amount of C3

Отново изходните им стойности са нулеви, тъй като това е минимумът, но може да са и никакви, т.е. да не правим присвояване на стойност тук, а да го направим впоследствие, в рамките на циклите.

Разписване на решението

Може да видите кода с решението в хранилището в GitHub.

Решението на задачата включваме във функция function solve() {}, която приема като аргумент входни данни под формата на масив от стрингове (това е особеност на системата bgcoder).

Стъпка 1

За прочитане на данните от конзолата, имаме променлива input. Тя участва като аргумент на функцията, затова не я декларираме вътре, а направо я ползваме.

function solve(input) {
  // 1. Convert Srings to Numbers
  input = input.map(Number);
}

За всеки от тестовете можем да декларираме извън функцията отделна променлива (test1, test2 и test3), която накрая подаваме като параметър на функцията solve():

  var test1 = [
    '110',
    '13',
    '15',
    '17'
  ]
  var test2 = [
    '20',
    '11',
    '200',
    '300'
  ]
  var test3 = [
    '110',
    '19',
    '29',
    '39'
  ]
  solve(test1);
  solve(test2);
  solve(test3);

Стъпка 2

В рамките на функцията дефинираме следните променливи:

  • разполагаема сума: var S
  • цена на първи тип пастичка: var C1
  • цена на втори тип пастичка: var C2
  • цена на трети тип пастичка: var C3

С цел спестяване на памет, изреждаме променливите със запетая, вместо да слагаме точка и запетая и var пред всяка от тях:

var S = input[0],
    C1 = input[1],
    C2 = input[2],
    C3 = input[3];

Стойностите, които присвояваме на променливите, съответстват на дадените индекси от масива с входните данни, които подаваме.

function solve(input) {
  // 2. Declare Variables for input values
  var S = input[0], // Money owned
      C1 = input[1], // Price Cake 1
      C2 = input[2], // Price Cake 2
      C3 = input[3], // Price Cake 3
}

Стъпка 3

Дефинираме още променливи: за максималната сума, която трябва да бъде открита и за съответните количества пастички от всеки тип, които ще участват в нея.

function solve(input) {
  // 3. Declare Variables for max sum to be found and counters for cakes
  var maxValue = 0,
      currentC1 = 0, // Amount of C1
      currentC2 = 0, // Amount of C2
      currentC3 = 0, // Amount of C3
}

Стъпка 4

Имаме нужда от функция, която да изчислява максимално количество от даден тип пастичка, което можем да си позволим със сумата S.

function solve(input) {
  // 4. Find max amount of each cake
  // Use function to calculate max amount of each type of cake
  function calculateCurrentAmount(sum, cake) {
      var currentAmount = sum / cake;
      return parseInt(currentAmount);
  }
}

Стъпка 5

След като вече имаме функцията calculateCurrentAmount(), можем да я използваме, за да дефинираме променливи за максималните количества от трите типа пастички и да им присвоим стойности:

function solve(input) {
  // 5. Assign values to new variables for cake max amount
  var maxC1 = calculateCurrentAmount(S, C1); // Max amount of C1 in S
  var maxC2 = calculateCurrentAmount(S, C2); // Max amount of C2 in S
  var maxC3 = calculateCurrentAmount(S, C3); // Max amount of C3 in S
  // console.log(maxC1, maxC2, maxC3);
}

Стъпка 6

Нужна ни е булева променлива, която да сигнализира, когато открием търсената maxValue. Първоначалната стойност на променливата е false. В момента, в който maxFound стане равно на true, цикленето приключва.

function solve(input) {
  // 6. Declare boolean variable to tell us if max sum is found
  var maxFound = false;
}

Стъпка 7

Общият разход за различните комбинации пастички ще пазим в променливата currentValue.

function solve(input) {
  // 7. Declare variable to keep sum for current combination of cakes
  var currentValue = 0;
}

Стъпка 8

Същинското решение е в рамките на циклите, които използваме:

function solve(input) {
  // 8. Use cycles to iterate through all possible cake combinations to form maxValue
  // This approch assumes that maxValue may be formed by one, two or three of the prices
     // Iterate through amount of cakes C1
     for (var i = 0; i <= maxC1; i++) {

       // Iterate through amount of cakes C2
       for (var j = 0; j <= maxC2; j++) {

          // Iterate through amount of cakes C3
          for (var k = 0; k <= maxC3; k++) {
             // Calculate currentValue
             currentValue = C1 * i + C2 * j + C3 * k;

             // Check if currentValue is a valid sum
             if (currentValue > maxValue && currentValue <= S) {
                // Assign currentValue to maxValue
                maxValue = currentValue;
                // Keep value for each cake's count
                currentC1 = i;
                currentC2 = j;
                currentC3 = k;

                if (maxValue == S) {
                   var maxFound = true;
                }
             }
             if (maxFound) {
               break;
             }
          }
          if (maxFound) {
            break;
          }
       }
       if (maxFound) {
         break;
       }
     }
}

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

currentValue = C1 * i + C2 * j + C3 * k;

Правим проверка, дали currentValue надвишава стойността на откритата до момента maxValue: първоначалната стойност на maxValue е 0, но тя ще нараства с всяка следваща по-голяма сума, която образуваме при събирането на бройки от пастичките. Освен да надвишава maxValue, currentValue трябва да бъде по-малка или равна на разполагаемата сума S:

currentValue > maxValue && currentValue <= S

Само ако тези две условия са изпълнени, присвояваме currentValue като стойност на maxValue:

// Assign currentValue to maxValue
maxValue = currentValue;

За наше удобство (по условие не ни го изискват), можем да запазим в currentCx променливите конкретните количества от трите типа пастички, с които е формирана конкретната currentValue.

// Keep value for each cake's count
currentC1 = i;
currentC2 = j;
currentC3 = k;

В рамките на първата проверка, накрая включваме и втора: дали случайно обазуваната дотук maxValue не е равна по стойност на сумата S? Ако да, maxFound ще стане равно на true.

if (maxValue == S) {
  var maxFound = true;
}

Съответно, в края на тялото на цикъл 3 включваме и условие за изход от цикъла: ако maxFound e true, излизаме от цикъла. Но за да излезем и от другите два цикъла, и там трябва да включим същата проверка.

Стъпка 9

Накрая е нужно просто да отпечатаме намерената maxValue:

function solve(input) {
  // 9. Print final result
  console.log(maxValue);
  // console.log(currentC1, currentC2, currentC3);
}

Интересно е да се отбележи, че ако принтираме бройките, с които участва всяка пастичка във формирането на maxValue за всеки от трите тестови входа, ще получим за първия тест други стойности, различни от дадените в условието на задачата:

result2

Резултат по условие:

  • 6 бр. от пастичките на цена C1 = 13
  • 1 бр. от пастичките на цена C2 = 15
  • 1 бр. от пастичките на цена C3 = 17

Причината е, че при цикленето за maxValue се взема първата възможна комбинация, която се доближава максимално до S. В случая, това е:

  • 5 бр. от пастичките на цена C1
  • 3 бр. от пастичките на цена C2
  • 0 бр. от пастичките на цена C3

Как работят циклите?

Вложените цикли функционират по такъв начин, че първо се изпълнява докрай най-вътрешният цикъл. Това означава, че с влизането в цикъл 1 и неговата първа итерация (когато i = 0), биваме препратени към първата итерация (j = 0) на цикъл 2, а той ни препраща към първата итерация на цикъл 3 (k = 0).

Изпълняват се всички итерации на третия цикъл (k = 0 … maxC3) и едва след това се връщаме за втора итерация (j = 1) към цикъл 2. Той обаче ни праща отново към цикъл 3 и едва след като отново извъртим цикъл 3, отиваме за трета итерация (j = 2) в цикъл 2. Това се повтаря, докато не приключим с всички итерации в цикъл 2 (j = 0 … maxC2) – едва тогава се връщаме за втора итерация (i = 1) на цикъл 1.

Но цикъл 1 ни праща пак към първа итерация на цикъл 2, цикъл 2 пък ни праща да минем през цикъл 3, и цялата дълга история с извъртането на цикъл 2 и цикъл 3 се повтаря отново, преди да се върнем за следваща итерация (i = 2) в цикъл 1. Когато извъртим всички итерации (i = 0 … maxC1) на цикъл 1, тогава цикленето най-после приключва.

 

Подробно описание на действията в трите цикъла

1. От цикъл 1, при първата итерация се взема началната стойност на брояча i (var i = 0;). Следва да се изпълни кодът в тялото на цикъл 1. Този код обаче е втори цикъл.

2. Влизаме в цикъл 2 и правим първа итерация там, с начална стойност на j, равна на 0 (var j = 0;). Следва да се изпълни кодът в тялото на цикъл 2. Този код обаче е трети цикъл.

3. Влизаме в цикъл 3 и правим първа итерация там, с начална стойност на k, равна на 0 (var k = 0;). В цикъл 3 нямаме нищо вложено, така че просто продължаваме цикленето вътре. При всяка итерация в цикъл 3, правим проверка, дали максималната сума вече е открита: ако отговорът е положителен, т.е. maxFound е true, излизаме от третия цикъл и се връщаме в цикъл 2. Ако не е, инкрементираме и продължаваме с цикленето тук:

3.1. Инкрементираме k++ и то става равно на 1. Край на първата итерация.

3.2. Проверката (k <= maxC3;) позволява втора итерация, тъй като k е 1, което е по-малко от максималната възможна бройка 6 (maxC3) за пастичките от третия вид. Инкрементираме k++ и то става равно на 2. Край на втората итерация.

3.3. Проверката (k <= maxC3;) позволява трета итерация, тъй като k е 2, което е по-малко от 6 (maxC3). Инкрементираме k++ и то става равно на 3. Край на третата итерация.

3.4. Проверката (k <= maxC3;) позволява четвърта итерация, тъй като k е 3, което е по-малко от 6 (maxC3). Инкрементираме k++ и то става равно на 4. Край на четвъртата итерация.

3.5. Проверката (k <= maxC3;) позволява пета итерация, тъй като k е 4, което е по-малко от 6 (maxC3). Инкрементираме k++ и то става равно на 5. Край на петата итерация.

3.6. Проверката (k <= maxC3;) позволява шеста итерация, тъй като k е 5, което е по-малко от 6 (maxC3). Инкрементираме k++ и то става равно на 6. Край на шестата итерация.

3.7. Проверката (k <= maxC3;) позволява седма итерация, тъй като k е 6, което е равно на 6 (maxC3). Инкрементираме k++ и то става равно на 7. Край на седма итерация.

3.8. Проверката (k <= maxC3;) не позволява следващи итерации, тъй като k вече е 7. Излизаме от цикъл 3 и се връщаме на цикъл 2.

Дотук, при първата итерация на цикъл 2, сме комбинирали следните стойности от трите цикъла:

i = 0 j = 0 k = 0
i = 0 j = 0 k = 1
i = 0 j = 0 k = 2
i = 0 j = 0 k = 3
i = 0 j = 0 k = 4
i = 0 j = 0 k = 5
i = 0 j = 0 k = 6

4. След края на цикъл 3, в цикъл 2 също правим проверка, дали максималната сума вече е открита: ако отговорът е положителен, излизаме от втория цикъл и се връщаме в цикъл 1.  Ако отговорът е отрицателен, инкрементираме j++ (тогава j става равно на 1) и продължаваме цикленето.

4.1. Проверката (j <= maxC2;) позволява втора итерация в цикъл 2, тъй като j е 1, което е по-малко от максималната възможна бройка 7 (maxC2) за пастичките от втория вид.

4.2. Следва отново да се изпълни кодът в тялото на цикъл 2, т.е. имаме нови 7 итерации в цикъл 3.

При втората итерация на цикъл 2, сме комбинирали следните стойности от трите цикъла:

i = 0 j = 1 k = 0
i = 0 j = 1 k = 1
i = 0 j = 1 k = 2
i = 0 j = 1 k = 3
i = 0 j = 1 k = 4
i = 0 j = 1 k = 5
i = 0 j = 1 k = 6

5. След края на цикъл 3, ако проверката за maxFound е отрицателна и се върнем в цикъл 2, там също проверяваме за maxFound, за да можем да излезем от цикъла, ако максималната сума е открита. Ако обаче maxFound все още е false и в цикъл 2, инкрементираме j++ (j става равно на 2) и продължаваме с цикленето там:

5.1. Проверката (j <= maxC2;) позволява трета итерация в цикъл 2, тъй като j е 2, което е по-малко от 7 (maxC2).

5.2. Следва отново да се изпълни кодът в тялото на цикъл 2, т.е. имаме нови 7 итерации в цикъл 3.

При третата итерация на цикъл 2, сме комбинирали следните стойности от трите цикъла:

i = 0 j = 2 k = 0
i = 0 j = 2 k = 1
i = 0 j = 2 k = 2
i = 0 j = 2 k = 3
i = 0 j = 2 k = 4
i = 0 j = 2 k = 5
i = 0 j = 2 k = 6

6. След края на цикъл 3, ако проверката за maxFound е отрицателна в цикли 3 и 2, инкрементираме j++ (j става равно на 3) и продължаваме с цикленето там:

6.1. Проверката (j <= maxC2;) позволява четвърта итерация в цикъл 2, тъй като j е 3, което е по-малко от 7 (maxC2).

6.2. Следват нови 7 итерации в цикъл 3.

7. След края на цикъл 3, отново проверяваме статуса на maxFound и ако е отрицателен в цикли 3 и 2, инкрементираме j, което става равно на 4.

7.1. Проверката (j <= maxC2;) позволява пета итерация в цикъл 2, тъй като j е 4, което е по-малко от 7 (maxC2).

7.2. Следват нови 7 итерации в цикъл 3.

8. Край на цикъл 3, проверка за maxFound и евентуално връщане към цикъл 2, където също проверяваме за maxFound и ако е все още false, инкрементираме j и то става равно на 5.

8.1. Проверката (j <= maxC2;) позволява шеста итерация в цикъл 2, тъй като j е 5, което е по-малко от 7 (maxC2).

8.2. Следват нови 7 итерации в цикъл 3.

9. Край на цикъл 3, проверка за maxFound и евентуално връщане към цикъл 2, където също проверяваме за maxFound и ако е все още false, инкрементираме j и то става равно на 6.

9.1. Проверката (j <= maxC2;) позволява седма итерация в цикъл 2, тъй като j е 6, което е по-малко от 7 (maxC2).

9.2. Следват нови 7 итерации в цикъл 3.

10. Край на цикъл 3, проверка за maxFound и евентуално връщане към цикъл 2, където също проверяваме за maxFound и ако е все още false, инкрементираме j и то става равно на 7.

10.1. Проверката (j <= maxC2;) позволява осма итерация в цикъл 2, тъй като j е 7, което е равно на 7 (maxC2).

10.2. Следват нови 7 итерации в цикъл 3.

11. Край на цикъл 3, проверка за maxFound и евентуално връщане към цикъл 2, където също проверяваме за maxFound и ако е все още false, инкрементираме j и то става равно на 8.

11.1. Проверката (j <= maxC2;) не позволява следващи итерации в цикъл 2, тъй като j е 8, което е по-голямо от 7 (maxC2).

11.2. Правим проверка за maxFound в цикъл 2 и ако ни даде резултат false, се връщаме пак на цикъл 1, където също правим проверка за maxFound.

12. Ако maxFound в цикъл 1 е true, прекратяваме цикленето; ако обаче е false, инкрементираме i++, което става равно на 1 и започва втора итерация в цикъл 1. Изпълняваме кода в тялото на цикъл 1, който ни праща пак към цикъл 2, цикъл 2 ни праща в цикъл 3 и т.н., докато броячът на цикъл 1 стане равен на 9 – тогава излизаме от цикъл 1 и цикленето приключва.

 

Advertisements

Вашият коментар

Попълнете полетата по-долу или кликнете върху икона, за да влезете:

WordPress.com лого

You are commenting using your WordPress.com account. Log Out / Промяна )

Twitter picture

You are commenting using your Twitter account. Log Out / Промяна )

Facebook photo

You are commenting using your Facebook account. Log Out / Промяна )

Google+ photo

You are commenting using your Google+ account. Log Out / Промяна )

Connecting to %s