Интересные интересности и задачи/головоломки

[Poma][a]

100%-ное попадание..
Но можно пару вопросов?

k+(k-1)+(k-2)+...+(k-i)>=100

Это понятно.. Вариант должен позволять найти любой этаж.. от сюда такое неравенство..

(i+1)(2k-i)>=200

Как же решить неравенство с 2-мя переменными? (кроме перебора)
Мой вариант..
Разобьем все числа от 1 до 100 на промежутки вида :
1 14
15 27
28 39
40 50
...

Кидаем шарики с этажей из 2-го столбца.. Как только он разбился, берем число из 1-ого столбца.. и начинаем кидать с него до числа из 2-го.. как только шарик разбился - это и есть ответ..

[Аватар]

кроме перебора

А чем плохой способ для целочисленного неравенства? Подбором и решил. С учетом i<k здесь даже система неравенств. Если программой, то элементарно решается. Твой то способ тоже методом тыка

[Poma][a]

А чем плохой способ для целочисленного неравенства?

Вынужден согласиться..

Подбором и решил.

Ясненько..

С учетом i<k здесь даже система неравенств.

Ага..

Твой то способ тоже методом тыка

Отчасти..

А что с 3-ей?

[Аватар]

А что с 3-ей?

Сложней чем 1-ая? Смотря кто решает
Команд - 2^k
Игр - 2^(k-1)+2^(k-2)+...+2^1+2^0=2^k-1

Отчасти..

Ни чего не отчасти. Мы пришли к одному и тому же ряду (14,27,39,50,...), дальше одинаково, только мой подход получения этого ряда более аналитический, а твой полностью эмпирический

[Poma][a]

Сложней чем 1-ая? Смотря кто решает

Наоборот..
Мое :
После каждой игры вылетает одна команда..
После первой игры осталось N-1 к
После 2-ой - N-2
После N-1 - осталась 1 к.

Ни чего не отчасти.

Я пришел чисто из логики..
Чем ближе в сотне, тем меньше попыток, посему размеры группы, на которые я сокращаю должон постоянно уменьшаться.. на сколько? - на 1.. отсюда вывод : на первую группу k попыток, на 2-ую k-1, на n : k-n+1..
Теперь супер тупой перебор.. получаем 14..
Так что тут НЕ все решение переборное, а лишь его часть

[Аватар]

Я пришел чисто из логики..

К тому, что такой ряд должен быть я тоже чисто из логики. Иначе откуда взяться формулам для его создания? А теперь прикинь m этажей и n шариков. Много просто подбором в лоб решишь? Там скорее всего какая-то рекурсия R(m,n) от R(m-1,n-1). А вторую задачу ты красивше решил, за что +. У меня тупо в лоб

[Poma][a]

Много просто подбором в лоб решишь?

Дык из Вашего же

k+(k-1)+(k-2)+...+(k-i)>=100

всё и вытечет.. подобрать такие i и k, что i < k и усё..

И раз пошли решения, то тогда я поспрашиваю..

И так.. 2 задачи, которые я не решил..
Если Вы знаете, как их решать, то желательно, намекнуть, где у меня косяк, как что-то можно сделать лучше, как решить такую-то проблемку и прочее..

Сумма цифр
Вес: 1
Функция f(x) рекурсивно заменяет число на сумму его цифр, пока не останется одна цифра. Например, f(1234) = f(10) = f(1) = 1. Найти f(2013!)

Мои мысли..

Вадим давно предложил способ вычисления конечной суммы числа за O(1)..
Это вот так :
if n mod 9 = 0 then result := 9
else result := n mod 9
(для натуральных чисел)
Но увы, он не привел док-во..
Я же доказать это не могу..

Но если делать по формуле Вадима, то ответ будет 9.
Осталось доказать, что формула работает корректно и совершенно верна..

Представим число N ввиде 9*k+p
Причем p in [1..9]
Осталось найти способ заявить, что p - искомая цифирка..
А как это сделать я не знаю..


Сортировка восьми чисел
Вес: 4
Есть восемь последовательно записанных чисел, которые вы не видите. Можно попросить друга упорядочить любые два из них, указав их индексы. Например, если вы попросили упорядочить второе и пятое числа, то ваш друг во второе число поместит минимум из этих двух чисел, а в пятое - максимум (при этом не известив вас, сделаны какие-либо изменения или нет). За какое минимальное число просьб вы сможете гарантированно упорядочить все числа? Обоснование минимальности не требуется.


Думается мне, что ответ - 16..
Поясню.. у г. Кнута в 3-м томе поставлена задача о поиске оптимальной сортировки..
И ответ 16 возможен лишь при сортировке вставками и слияниями..но 1) она ужасно описана 2) мы не можем ее использовать, т.к. нам не говорят, была ли замена..

Что делать - я без малейшего понятия..
Посему прошу хелп..
И да.. помню была тема.. отсортировать 4 числа.. там Аватар решал.. только поиск бунтует.. да и 8 <> 4..

[Аватар]

1. Используй признак делимости на 9
2. 19 - ищи сеть Бетчера

[Poma][a]

Используй признак делимости на 9

Если число делится на сумму своих цифр, то оно делится на 9..
И к чему это прикрутить?

19 - ищи сеть Бетчера

Спасибо!

[Аватар]

Если число делится на сумму своих цифр, то оно делится на 9

Число делится на 9 если сумма его цифр делится на 9
Если число делится на 9, то и сумма его цифр делится на 9
И прикрутить к 9*k+p. И лучше p in [0..8].
Поищи доказательство этого признака, должно помочь