Задача 3 — если под "попадет" понимать "останется" — то надо просто взять максимум 1 и результата функции.
Кот
rc i = go i 1 1 where
go i r b | i < b + r = (p, q)
| otherwise = go i (r+1) (b+r)
where p | i<=b = 0 | otherwise = i-r
q | i>=b+r-1 = 0 | otherwise = i-r+1
g x = go where
go 1 = x
go i = p l + p r where (l, r) = rc i
p 0 = 0
p i = (go i - 1) / 2
main = print $ g 2 3
........
0.5
g [] = 0
g [x] = x
g (x:y:xs) = max (x + g xs) $ g (y:xs)
main = do
print $ g [3, 2, 7, 10]
print $ g [3, 2, 5, 10, 7]
print $ g [5, 5, 10, 100, 10, 5]
print $ g [1, 2, 3]
print $ g [1, 20, 3]
.........
13
15
110
4
20
Задача 1 — мой кот находит не то решение, которое приведено, но тоже правильное — при нечетном количестве 0 можно кидать в любое множество
Кот
g 0 _ = [[]]
g _ [] = []
g n (x:xs) = map (x:) (g (n-1) xs) ++ g n xs
c l = snd . minimum . map (\x -> (abs (2 * sum x - s), x)) $ g n l where
s = sum l
n = length l `div` 2
main = do
print $ c [3, 4, 5, -3, 100, 1, 89, 54, 23, 20]
print $ c [23, 45, -34, 12, 0, 98, -99, 4, 189, -1, 4]
........
[3,5,-3,89,54]
[23,-99,4,189,4]
Из дальнейших попыток поиграться с сабжевой задачей варианты с добавлением такой же площади если приклеивать желтые куски одинаковой ширины с 3 или 4 сторон приводят к тривиальным (не настолько интересным) уравнениям, вариант достройки прямоугольника до квадрата в 2 раза большей площади приводит к ровно такому же сид эквэйшену, как и для Пифагоровых троек, а вариант как у автора, только чтобы желтая площадь была в 2 раза меньше синей решается аналогичными кустарными рассуждениями, приводящими к сид (как это по-русски?) уравнению вида:
6хх = сщ где а = щ + 2х, б = с + 2х
например при х = 1 беря с = 3 и щ = 2 получаем а = 4, б = 5 и синяя площадь аб = 20 а желтая площадь (а+х)(б+х) — аб = 30 — 20 = 10 и в 2 раза меньше синей.
Похоже, что целый класс задач сводится к сид эквэйшенам подобного простого вида.
Та же кустарщина с Пифагоровыми тройками: впишем мелкий целочисленный квадрат в угол большого, останется "уголок", из которого тоже должно быть можно сложить полный квадрат. То есть отрезав от каждой "ноги" уголка хвостики, ими можно было заполнить оставшееся пустое место обрезанного уголка до квадрата. При ширине "ноги" х и пропорции отрезания а к б получаем (сразу безо всякой алгебры) волшебную формулу:
аа = 2бх, что очень похоже на волшебную формулу выше. И так же берем любой четный (по очевидным причинам) полный квадрат (а следовательно четное а), факторизуем его и получаем все тройки, задаваемые данным а. Например:
а = 2: б = 2, х = 1 — переводя к Пифагору м = а + б = 4, н = а + х = 3, к = а + б + х = 5
или
а = 100: бх = 5000, пусть б = 5, х = 1000; тогда м = 105, н = 1100, к = 1105 и т.д., т.е. каждое четное а принесет нам пачку троек. хотя в данном случае тройка получилась кратная, можно сократить на 5 — но если надо отсекать кратные тройки можно предварительно факторизовать а и не группировать в б и х одинаковые составляющие
Моему далекому от Бурбакизма мозгу проще оперировать геометрическими кустарными аналогиями, чем производить формальные символьно-алгебраические преобразования без бумажки. Поэтому (в обозначениях автора) я бы вырезал правый нижний кусок (удалил 2 одинаковых куска разного цвета) и получил бы (заменив разность в-х например с)
сх + 2хх = са = с(х+щ) (о Боже, мозг, ну зачем ты выбрал щ? наверное потому что так проще набирать не переключая раскладку?)
откуда со всей очевидностью выходим на сокровенную формулу 2хх = сщ, где задавая любой х можем получить все варианты через факторизацию.
Его можно силой затащить на дно, привязав веревкой к коряге )) И тогда уровень воды поднимется — по той же логике крайних значений — представьте что вы везли в лодке огромный воздушный шар )) И это стройно укладывается в модель — при плотности камня больше плотности воды уровень опустится, при меньше — поднимется. А если камень деревянный, и не затаскивать его на дно, а позволить плавать свободно после выкидывания за борт — то вангую что уровень не изменится — но надо аккуратнее разобрать этот вариант для уверенности )
я не думаю, что составители задачи будут в восторге от такого ответа, но квайнопись сильно зависит от языка — а он не был озвучен. Или это интервью в ту компанию, где кроме С языков не знают? ))
Вопрос 2 — на физфаке нас учили проверять формулы и модели устремляя какие-либо величины к крайним значениям. Допустим, у нас камень из страшного вещества с огромной плотностью, диаметром сантиметр и массой тонну. Пока он лежит в лодке — лодка сильно погружена в воду и вытесняет существенный объем. Когда мы выкинем камень, его объем почти не скажется на результате, за то лодка существенно поднимается и уровень воды опустится. Варианты когда плотность камня меньше плотности воды или воздуха рассматривать лень — думаю ответа выше вполне достаточно.
зависит от представления отрицательных чисел — в обратном, дополнительном до 1 или дополнительном до 2 коде. где-то достаточно просто занулить знаковый бит по И по маске, где-то просто прибавить максимальное число разрядной сетки умноженное на знаковый бит, сдвинутый вправо на ту же величину разрядной сетки — получается мы прибавляем макс_сигнед_инт умноженный на 1 если число отрицательное и на 0 если положительное — и получаем модуль числа.
но это уже детали реализации. стравлю 200 денег, что составители задачи хотели увидеть именно такое решение, как написано выше
Регулярно наблюдаю на самом компетентном математическом форуме рунета очередные темы с предложениями новых авторских алгоритмов, асимптотически превосходящих лучшие существующие аналоги. Где регулярно авторов разочаровывают, что, например, сложение и умножение — это не О(1), а О(n). Вы конечно хитро спрятались за явными интами, но обычно асимптотическую сложность принято оценивать у абстрактного алгоритма без привязки к конкретным деталям реализации убогой конкатенации иммутабельных строк. В том же Хаскеле с его автовыводом типов при автоматическом расширении с интов до интеджеров асимптотика существенно изменится (при одном и том же коде!), но "честная" алгоритмическая останется какой и была. Другое дело, что вы не рассказываете про "честную", а ограничиваетесь кустарной-наколеночной, да еще языко-платформозависимой. Но при этом позиционируете себя как эксперта в этой области, и еще обучаете потенциальных авторов очередных супер-алгоритмов, о которых я писал в начале этого комментария.
Имхо, получается только первый вопрос более-менее нетривиален, учитывая что ответ надо дать не кодом а в результате устных рассуждений. Ну и третья задача допускает алгоритм, немного интереснее очевидного (опубликовал выше).
Про лампочки — баян (к тому же спорный), про степень двойки — трижды баян, но далеко не все языки дают доступ к битовому представлению чисел, поэтому альтернативный однострочник
на неземном волшебном
f n = n==1 || r==0 && f q where (q,r) = quotRem n 2
про сортированный массив — тоже очевидно.
Но для школьников старших классов вполне подходящие задачки на факультатив.
Ради интереса - чуть менее тривиальное решение последней задачи
f 0 a 0 = [a]
f 0 _ _ = []
f d a n | c > 9 = []
| c == 0 = [c] >>= f'
| otherwise = [c, c-1] >>= f' where
d1 = d + 1
c = div n d1
d' = div d 10
f' v = f d' (v:a) (n-v*d1)
toi = foldr (\x a -> a*10 + x) 0
g n = map toi . f (10^(length $ show n)) [] $ n
main = do
mapM (\x -> putStrLn $ show x ++ " " ++ show (g x)) [10000000000000..10000000000010]
Вопрос 1 — 6*6 > 31 так что задача решаема. Вариантов — море, простейший — 6-ричная система.
Задача 3 — если под "попадет" понимать "останется" — то надо просто взять максимум 1 и результата функции.
Задача 2 — децкий сат
Задача 1 — мой кот находит не то решение, которое приведено, но тоже правильное — при нечетном количестве 0 можно кидать в любое множество
Из дальнейших попыток поиграться с сабжевой задачей варианты с добавлением такой же площади если приклеивать желтые куски одинаковой ширины с 3 или 4 сторон приводят к тривиальным (не настолько интересным) уравнениям, вариант достройки прямоугольника до квадрата в 2 раза большей площади приводит к ровно такому же сид эквэйшену, как и для Пифагоровых троек, а вариант как у автора, только чтобы желтая площадь была в 2 раза меньше синей решается аналогичными кустарными рассуждениями, приводящими к сид (как это по-русски?) уравнению вида:
6хх = сщ где а = щ + 2х, б = с + 2х
например при х = 1 беря с = 3 и щ = 2 получаем а = 4, б = 5 и синяя площадь аб = 20 а желтая площадь (а+х)(б+х) — аб = 30 — 20 = 10 и в 2 раза меньше синей.
Похоже, что целый класс задач сводится к сид эквэйшенам подобного простого вида.
Та же кустарщина с Пифагоровыми тройками: впишем мелкий целочисленный квадрат в угол большого, останется "уголок", из которого тоже должно быть можно сложить полный квадрат. То есть отрезав от каждой "ноги" уголка хвостики, ими можно было заполнить оставшееся пустое место обрезанного уголка до квадрата. При ширине "ноги" х и пропорции отрезания а к б получаем (сразу безо всякой алгебры) волшебную формулу:
аа = 2бх, что очень похоже на волшебную формулу выше. И так же берем любой четный (по очевидным причинам) полный квадрат (а следовательно четное а), факторизуем его и получаем все тройки, задаваемые данным а. Например:
а = 2: б = 2, х = 1 — переводя к Пифагору м = а + б = 4, н = а + х = 3, к = а + б + х = 5
или
а = 100: бх = 5000, пусть б = 5, х = 1000; тогда м = 105, н = 1100, к = 1105 и т.д., т.е. каждое четное а принесет нам пачку троек. хотя в данном случае тройка получилась кратная, можно сократить на 5 — но если надо отсекать кратные тройки можно предварительно факторизовать а и не группировать в б и х одинаковые составляющие
Моему далекому от Бурбакизма мозгу проще оперировать геометрическими кустарными аналогиями, чем производить формальные символьно-алгебраические преобразования без бумажки. Поэтому (в обозначениях автора) я бы вырезал правый нижний кусок (удалил 2 одинаковых куска разного цвета) и получил бы (заменив разность в-х например с)
сх + 2хх = са = с(х+щ) (о Боже, мозг, ну зачем ты выбрал щ? наверное потому что так проще набирать не переключая раскладку?)
откуда со всей очевидностью выходим на сокровенную формулу 2хх = сщ, где задавая любой х можем получить все варианты через факторизацию.
Отлично. Сигн по знаковому биту, выделенному маской и сдвинутому в 0 позицию даже проще чем модуль.
Его можно силой затащить на дно, привязав веревкой к коряге )) И тогда уровень воды поднимется — по той же логике крайних значений — представьте что вы везли в лодке огромный воздушный шар )) И это стройно укладывается в модель — при плотности камня больше плотности воды уровень опустится, при меньше — поднимется. А если камень деревянный, и не затаскивать его на дно, а позволить плавать свободно после выкидывания за борт — то вангую что уровень не изменится — но надо аккуратнее разобрать этот вариант для уверенности )
Квайн:
1проверяется в любом РЕПЛе
я не думаю, что составители задачи будут в восторге от такого ответа, но квайнопись сильно зависит от языка — а он не был озвучен. Или это интервью в ту компанию, где кроме С языков не знают? ))
Вопрос 2 — на физфаке нас учили проверять формулы и модели устремляя какие-либо величины к крайним значениям. Допустим, у нас камень из страшного вещества с огромной плотностью, диаметром сантиметр и массой тонну. Пока он лежит в лодке — лодка сильно погружена в воду и вытесняет существенный объем. Когда мы выкинем камень, его объем почти не скажется на результате, за то лодка существенно поднимается и уровень воды опустится. Варианты когда плотность камня меньше плотности воды или воздуха рассматривать лень — думаю ответа выше вполне достаточно.
зависит от представления отрицательных чисел — в обратном, дополнительном до 1 или дополнительном до 2 коде. где-то достаточно просто занулить знаковый бит по И по маске, где-то просто прибавить максимальное число разрядной сетки умноженное на знаковый бит, сдвинутый вправо на ту же величину разрядной сетки — получается мы прибавляем макс_сигнед_инт умноженный на 1 если число отрицательное и на 0 если положительное — и получаем модуль числа.
но это уже детали реализации. стравлю 200 денег, что составители задачи хотели увидеть именно такое решение, как написано выше
del
r = (a+b-abs(a-b))/2;надеюсь взятие модуля числа и деление на 2 сдвигом недороги на неуказанной абстрактной платформе, где будет исполняться кот
Регулярно наблюдаю на самом компетентном математическом форуме рунета очередные темы с предложениями новых авторских алгоритмов, асимптотически превосходящих лучшие существующие аналоги. Где регулярно авторов разочаровывают, что, например, сложение и умножение — это не О(1), а О(n). Вы конечно хитро спрятались за явными интами, но обычно асимптотическую сложность принято оценивать у абстрактного алгоритма без привязки к конкретным деталям реализации убогой конкатенации иммутабельных строк. В том же Хаскеле с его автовыводом типов при автоматическом расширении с интов до интеджеров асимптотика существенно изменится (при одном и том же коде!), но "честная" алгоритмическая останется какой и была. Другое дело, что вы не рассказываете про "честную", а ограничиваетесь кустарной-наколеночной, да еще языко-платформозависимой. Но при этом позиционируете себя как эксперта в этой области, и еще обучаете потенциальных авторов очередных супер-алгоритмов, о которых я писал в начале этого комментария.
Имхо, получается только первый вопрос более-менее нетривиален, учитывая что ответ надо дать не кодом а в результате устных рассуждений. Ну и третья задача допускает алгоритм, немного интереснее очевидного (опубликовал выше).
Про лампочки — баян (к тому же спорный), про степень двойки — трижды баян, но далеко не все языки дают доступ к битовому представлению чисел, поэтому альтернативный однострочник
про сортированный массив — тоже очевидно.
Но для школьников старших классов вполне подходящие задачки на факультатив.
Должно быть, Эльфийский
Картинки с теткой-стеклодувщицей нет — не стал читать