Архив Айгуст —
архив помогалки Августа
«Никто не вечен… В отличие от знаний»
Внимание!
  Материалы на данном сайте представляют собой архивную копию форума «Айгуст - помогалка Августа» на момент октября 2019 года с целью сохранения знаний. Все права на материалы принадлежат их авторам. Материалы представлены в открытый доступ в ознакомительных целях, запрещено их коммерческое использование без согласования с авторами. Администрация сайта не несёт ответственности за содержание материалов, в том числе за наличие вредоносных закладок в коде, используйте любой предоставленный код на свой страх и риск. Рекомендуется проверять любые файлы вручную и перезаливать на собственный хостинг, дабы избежать возможной модификации или исчезновения в будущем.

Едем дальше

iGust
Сообщений: 52
19.01.2012 15:14:17
Едем дальше
Новогодненькая, пока праздничный дух не сошел на нет.

В ряд стоит бесконечное число урн, в которых могут лежать камни. Известно, что в урне с номером n+m лежит столько камней, сколько в урнах с номерами n и m в сумме, либо на один больше. В урне с номером 9999 лежит 3333 камня. Во второй урне камней нет, а в третьей есть.

Сколько камней в 2012-й урне?
#17805
InfinitI
Основатель
Сообщений: 1191
19.01.2012 15:28:53
Re: Едем дальше

X(m+n)=X(n)+X(m)+1
Или
X(m+n)=X(n)+X(m)
#17807
kent
Сообщений: 2041
19.01.2012 15:33:14
Re: Едем дальше
Я не очень понял. Например, 5 = 1 + 4 = 2 + 3.
Значит в 1 и 4 урнах вместе лежит столько же камней, сколько во 2 и 3 вместе взятые?
А если количество камней разное, то сколько лежит в 5 урне? Один из вариантов, неизвестый?
Хотя следовательно (1, 4) и (2, 3) условие не делают .
#17808
iGust
Сообщений: 52
19.01.2012 15:46:10
Re: Едем дальше
Инфинити правильно написал.

f(n+m) = f(n) + f(m) || f(n) + f(m) + 1

Соответственно, в 5-й урне лежит либо столько же, сколько в 1-й и в 4-й вместе, либо на один больше.
Соответственно, в 5-й урне лежит либо столько же, сколько во 2-й и в 3-й вместе, либо на один больше.

О соответствии количества камней в (1 + 4) и (2 + 3) в условии ничего не сказано.

Добавил дополнительное условие: во второй урне камней нет, а в третьей есть. С ним будет проще.
#17809
iGust
Сообщений: 52
19.01.2012 15:57:52
Re: Едем дальше
Igust:
О соответствии количества камней в (1 + 4) и (2 + 3) в условии ничего не сказано.

Поясню пока не разорвали. Допустим, в 50-й урне 10 камней (с потолка пример), в 40-й — 8, в 60-й — 11, а в 100-й — 20.

Как видите условие соблюдено. f(100) = f(50) + f(50) = 20; f(100) = f(40) + f(60) +1 = 20. В первом случае единичка не добавилась, а во втором добавилась. Условие позволяет.

При этом f(40) + f(60) = 19 != f(50) + f(50) = 20.
#17810
Shogal
Программист
Сообщений: 519
19.01.2012 16:01:51
Re: Едем дальше
А n может равняться m?
F(2) = F(1)+F(1) (+1)? ?
#17811
iGust
Сообщений: 52
19.01.2012 16:11:45
Re: Едем дальше
А n может равняться m?

Это хороший вопрос. Может. Тогда f(2n) = f(n) + f(n) (+1), да.
#17812
Shogal
Программист
Сообщений: 519
19.01.2012 16:22:44
Re: Едем дальше
Тогда в первой урне 0 камней.
Во второй - ноль.
В третьей - ровно один.
В четвертой - ровно один.
В пятой: (4я+1я)=1+0,(3я+2я)=1+0, полкчаем 1, а с учетом возможного +1 получим 1 камень, либо 2.
<s>Шестая: (5я+1я)=1..2+0 = 1..2, (4я+2я)=1+0 = 1, (3я+3я)=1+1=2. Итого получаем снова 1..2
Седьмая: (6я+1я) = 1..2, (5я+2я) = 1..2, (4я+3я) = 2, тут уже может получится от 2 до 3 камней.</s>
Не знаю что делать дальше, прогонять до 9999 что ли...) Или подумать)
#17816
Shogal
Программист
Сообщений: 519
19.01.2012 16:28:54
Re: Едем дальше
Есть идея - развернуть программно подсчет верхней и нижней границы, и на 9999 урне остановиться и посмотреть, какие у нас набежали границы, а потом смотреть, верхнюю брать или нижнюю)
#17817
Shogal
Программист
Сообщений: 519
19.01.2012 16:38:39
Re: Едем дальше
Восьмая: (7я+1я) = 2..3, (6я+2я) = 1..2, (5я+3я) = 2..3, (4я+4я) = 2. Получаем 2..3.
Девятая: (8я+1я) = 2..3, (7я+2я) = 2..3, (6я+3я) = 2..3, (5я+4я) = 2..3. Получаем 2..4.
Десятая: (9я+1я) = 2..4, (8я+2я) = 2..3, (7я+3я) = 3..4, (6я+4я) = 2..3, (5я+5я) = 1..2+1..2 = 2..4. Получаем 3..4.
11я: (10я+1я) = 3..4, (9я+2я) = 2..4, (8я+3я) = 3..4, (7я+4я) = 3..4, (6я+5я) = 1..2+1..2 = 2..4. Получаем 3..5.
#17819
Shogal
Программист
Сообщений: 519
19.01.2012 16:43:28
Re: Едем дальше
Кто-нибудь, посчитайте дальше, а то программу писать лень, а я всё жду, когда напоремся на диапазон, который не будет влезать в конечный))
#17820
Shogal
Программист
Сообщений: 519
19.01.2012 16:47:17
Re: Едем дальше
Блин, весь мой подсчет в жопу засунуть, в шестом ящике точно 2)) Если 4я+2я = 1, а 3я+3я = 2, то должно обоим удовлетворять, то есть ровно 2))
#17821
iGust
Сообщений: 52
19.01.2012 16:48:18
Re: Едем дальше
:-)
#17822
Shogal
Программист
Сообщений: 519
19.01.2012 16:49:47
Re: Едем дальше
И так, гарантировано:
1: 0
2: 0
3: 1
4: 1
5: 1..2
6: 2
Ваня, проверь, нигде ли не хромает логика в рассуждениях? А то если из первых 6 где-то неправильно, но дальнейшие черновые подсчеты тоже неправильно пойдут)
#17823
Shogal
Программист
Сообщений: 519
19.01.2012 17:13:43
Re: Едем дальше
Ладно, если предположить что в первых 6 не напортачено, пойдем дальше: (в скобках чтобы долго не писать - номера, а к макс. границе сразу прибавляю вероятную единицу)
7: (6+1): 2..3, (5+2): 1..3, (4+3): 2..3, итог 2..3
8: (7+1): 2..4, (6+2): 2..3, (5+3): 2..4, (4+4): 2..3, итог: 2..3
9: (8+1): 2..4, (7+2): 2..4, (6+3): 3..4, (5+4): 2..4, итог: 3..4
10: (9+1): 3..5, (8+2): 2..4, (7+3): 3..5, (6+4): 3..4, (5+5): 2..5, итог: 3..4
11: (10+1): 3..5, (9+2): 3..5, (8+3): 3..5, (7+4): 3..5, (6+5): 3..5, итог: 3..5
12: (11+1): 3..6, (10+2): 3..5, (9+3): 4..6, (8+4): 3..5, (7+5): 3..6, (6+6): 4..5, итог: 4..5
13: (12+1): 4..6, (11+2): 3..6, (10+3): 4..6, (9+4): 4..6, (8+5): 3..6, (7+6): 4..6, итог 4..6
14: (13+1): 4..7, (12+2): 4..6, (11+3): 4..7, (10+4): 4..6, (9+5): 4..7, (8+6): 4..6, (7+7): 4..7, итог: 4..6
Никто закономерность не видит?))
#17827
iGust
Сообщений: 52
19.01.2012 17:15:27
Re: Едем дальше
Shogal: И так, гарантировано:
1: 0
2: 0
3: 1
4: 1
5: 1..2
6: 2

Сейчас всё верно.
#17828
Shogal
Программист
Сообщений: 519
19.01.2012 17:19:20
Re: Едем дальше
Чуть перефразирую таблицу:
_1: 0..0
_2: 0..0
_3: 1..1
_4: 1..1
_5: 1..2
_6: 2..2
_7: 2..3
_8: 2..3
_9: 3..4
10: 3..4
11: 3..5
12: 4..5
13: 4..6
14: 4..6
#17829
Shogal
Программист
Сообщений: 519
19.01.2012 17:47:27
Re: Едем дальше
Ладно, расскажу: Min(N) = floor(N/3), Max(N) = floor((N-1)/2)
Получим тогда:
Min(9999) = 3333, Max(9999) = 4999
Получаем нижнюю границу.
Значит во всех остальных урнах бралось по нижней границе, тогда получим:
Min(2012) = 670
Походу это ответ)
#17830
iGust
Сообщений: 52
19.01.2012 18:03:43
Re: Едем дальше
Превосходно! Всё верно, кроме «во всех остальных урнах бралось по нижней границе». Например, в 9990-й урне вполне могло взяться не по нижней. Я не знаю точно начиная с какой урны мог влезть лишний камушек, но точно не с 2012-й, так что на ответе это не отразилось.

Действительно, допустим, f(2012) = 671.
Тогда минимум f(4024) = 1342, а минимум f(8048) = 2684.

9999 - 8048 = 1951, а минимум f(1951) = 650. Стало быть, минимум f(9999) был бы 650 + 2684 = 3334, при этом известно что в 9999-й урне на самом деле 3333 камня. Вот и слава.

2:0 в вашу пользу.

P. S. Первую задачу я привел без изменений. Вторую подкорректировал. Закрепим закономерность последовательности, — третью задачу я придумал сам. Выходные. Те же место и время.
#17832

Другие темы раздела