Задачи с собеседований: наггетсы

В Макдональдс вы можете заказать куриные наггетсы в коробках по 6, 9 и 20 штук. Каким является максимальное число наггетсов, которое НЕЛЬЗЯ заказать любыми комбинациями этих коробок?

Ответ на задачу

Сначала определим, существует ли такое число.

Понятно, что если мы найдём 6 подряд идущих чисел, которые можно заказать: N0=N, N1=N+1, N2=N+2,…, N5=N+5, то любое следующее за ними M можно представить как M=Ni+6*k. То есть добавив к заказу Ni k коробок по 6, получим заказ M.

Также понятно, что начиная с 6, можно заказать любое число, кратное трём: N=6x+9y=3(2x+3y), можно найти x,y чтобы получить любое число 2x+3y>1.

Дальше нарисуем таблицу 10×10, аналогичную таблице умножения, и расположил в ней числа от 0 до 99. Будем зачёркивать числа, которые можно заказать. Сразу зачеркнем все числа, кратные 3 и число 0. Делаем что-то типа решета Эратосфена. Идём подряд по всем зачёркнутым, начиная от 0, и зачёркиваем все числа, через 6, 9 и 20, начиная от зачёркнутого. В итоге у меня появился зачёркнутый ряд из 6 чисел 44-49, и незачёркнутое число 43 перед ним, что и является ответом.

← Еще задачи с собеседований