Выпуск#20: ITренировка — актуальные вопросы и задачи от ведущих компаний

[qw1]

Ответ к задаче про McDonalds

Сначала определим, существует ли такое число.
Понятно, что если мы найдём 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)

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

[qw1]

Таблицу 10x10*

[Deosis]

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

Тогда, начиная с 26, можно заказать число, равное 0 или 2 по модулю 3.
С 46 можно заказать любое число.
Поэтому 43 — наибольшее число.

ПС. Попробуйте решить задачу для чисел 165, 210, 231, 315.

[qw1]

Чертовски сильная мысль, никогда бы не подумал в таком ключе, что 20 mod 3 = 1, поэтому, добавляя 20, можно сдвигать остатки от деления на 3 на единицу.

ПС. Попробуйте решить задачу для чисел 165, 210, 231, 315.

165 = 3·5·11
210 = 2·3·5·7
231 = 3·7·11
315 = 3·3·5·7
Комбинируя только числа 165 и 231, я могу получить
N = 165·x+231·y = 33·(5x+7y), т.е., начиная с 33·24 можно получить все числа, кратные 33.
Если бы вместо 33 было 11 (т.к. 210 mod 11 = 1), то, добавляя 210·z можно получить любое число, начиная с 23·24+11·210. Но увы, 210 mod 33 = 12, добавляя 12, я не получу все остатки от деления на 33 (33 — не простое число).
Как тут поможет ещё одно не использованное число 315, у меня нет идей.

[qw1]

ПС. Попробуйте решить задачу для чисел 165, 210, 231, 315.

Тут нет решения. Все числа делятся на 3. Значит, любое 3x+1 нельзя заказать :D

[blindmen]

а разве правильный ответ не «все имеющиеся нагетсы + 1 любая коробка»?

[qw1]

Неправильный ответ, т.к. надо выбрать наибольшее, а решение «все имеющиеся нагетсы + 2 любых коробки» заведомо больше вашего )))

[qw1]

Задача на удаление ноды простая, но не всегда имеет решение.
В случае, когда список состоит из 1 ноды, её удаление должно обнулить указатель Head, а его, по условями задачи, у нас нет.

[Andy_U]

Вопрос N1 — 10.

Без комментариев…

Вопрос N2 — 43:

44 = 1*20+4*6
45 = 5*9
46 = 2*20+1*6
47 = 1*20+3*9
48 = 8*6
49 = 2*20+1*9

Дальше — по кругу с шагом 6:

50=44+6
51=45+6
…

Задача N2:

Если все элементы списка имеют один и тот же размер, копируются (и удаляются), то копируем следующий за удаляемым элементом на его место и правим в нем ссылку. Потом исходную копию сдвинутого элемента удаляем. А вот если удаляемый элемент маленький, а следующий большой?

[speciman]

Правим ссылку?
Это нужно ?

[Andy_U]

О! Нет, конечно. Спасибо за уточнение.

[mickvav]

Но вылезание задачи про односвязный список в продакшене вызовет серьезные вопросы к архитектуре…

[Andy_U]

Задача N 3:

# -*- coding: utf-8 -*-

import itertools


if __name__ == '__main__':

    k = 3
    symbols = 'ab'
    
    for i in range(1, k+1):
        for j in itertools.product(symbols, repeat=i):
            print(''.join(j))

[Koneru]

Ну что проверит 3 задача…

2 строки кода

Умение написать примитивную регулярку?

var fileContent = fs.readFileSync("hello.cpp", "utf8");
fileContent.replace(/\/\*.*\*\/|\/\/.*\n/g,"");

[RiaD]

string path = "//path";

[Koneru]

Ваша правда, ну буду модифицировать регулярку(уже дело принципа)).

[qw1]

да там ещё и другие проблемы:
1) жадная звёздочка \/\/.*\n скушает всё от первого коммента // до конца файла.
2) жадная звёздочка \/\*.*\*\/ скушает всё между первым и последним комментом:

int /* hello */ test = 1; /* world */

после замены останется: int

3) Нужно учесть смешивание стилей комментирования:

// /*
int x;
// */

Ваш regex зачистит всё.

[qw1]

Ну и, такая замена fileContent.replace(/\/\/.*?\n/g,"");
из

#include <stdio.h> // hello
#include <stdlib.h> // world

сделает некорректный код

#include <stdio.h> #include <stdlib.h> 

[Koneru]

Кармы не хватает, но +

[IIvana]

Вопрос 1 — n=10. Решал по-честному, с уравнением (14+k)/(14+2k) = 17/20

Задача 1 как всегда решается в одну строчку на неземном и волшебном

f l k = concat . take k . tail . iterate (liftM2 (:) l) $ [[]]

main = print $ [f "ab" 3, f "abcd" 1]

[["a","b","aa","ab","ba","bb","aaa","aab","aba","abb","baa","bab","bba","bbb"],["a","b","c","d"]]

[naething]

Про наггетсы было на Numberphile: www.youtube.com/watch?v=vNTSugyS038

[SkyL1ne]

Наггетсы: что не так с числом 37?

[Andy_U]

Все так, его тоже нельзя «набрать» указанными числами, но оно не максимальное. 43 больше.

[johnklymenko]

Нужно наибольшее число.

[nickolaym]

Про удаление комментариев.

1) внутри строк — комментарии резать нельзя

foo(
  "this is /*not*/ a //comment!",
  '/*', '*/', '//', bar(), buz(),
  "this is not a \"line end /* and this is not a comment */",
  "multiline
  /* text with fake comments */
  goes on",
  "mismatched /* in a string"
);

2) строки с переносами

foo(); // multiline tail comment\
continued on the next line\
and this is still tail comment!!!

3) инлайновые комменты преобладают над концевыми

/* this is // inline comment */ foo(); // this is /* tail comment
bar();

Потрахаетесь с регулярочкой. Ох потрахаетесь...

Хотя, безусловно, лексер C++ — автоматный, так что регулярку родить можно.

P.S. раскрасчик кода на хабре — лажает с многострочными комментариями. Тоже, небось, студенты писали на собеседовании.

[qw1]

'/*', '*/', '//',
Прикольно. Уже и забыл, что так можно.