Пятничные задачки

← →
MBo © (2006-04-07 14:13) [0]

1. Дано предложение:
Это предложение содержит _ букв, _ слогов, _ слов
Впишите вместо прочерков числа (прописью) так, чтобы это предложение
стало правдивым.

2. Имеется двумерный массив MxN, элементы которого упорядочены по
возрастанию слева направо и сверху вниз. Необходимо за минимальное количество
операций определить, встречается ли в нем элемент, равный X.

3. В массиве длины N содержатся все целые числа от 0 до N, кроме
какого-то одного. Найти пропущенное число, если использовать
дополнительные массивы нельзя.
А что, если пропущено два числа?

4. Семеро друзей - Антонов, Борисов, Васильев, Глебов, Дмитриев, Егоров
и Иванов - по странному стечению обстоятельств имеют "совпадающие"
имена, причем ни один из них не является "тезкой" своей фамилии.
Кроме того, о них известно следующее:
- Все, кроме Антонова и Глебова, уже женаты.
- Невесте Егора очень не нравится фамилия ее жениха.
- Фамилия Глеба совпадает с именем Иванова.
- Жены Дмитриева и Ивана - родные сестры.
- Тот, чье имя совпадает с фамилией Бориса, женат, и его фамилия
совпадает с именем Егорова.
- Иван, Егор и Василий - брюнеты.
- Остальные четверо, в числе которых Иванов, Егоров и Васильев, -
блондины.
Как фамилия Василия?

5. У вас имеется 10 монет, среди которых могут быть и фальшивые.
Известно, что настоящие монеты весят одинаково, и фальшивые
(если они есть) тоже весят одинаково). Кроме того, известно, что
хотя бы одна из монет - настоящая.
Как за 3 взвешивания подтвердить или опровергнуть, что все ваши
монеты - настоящие.

6. Нужно организовать круговой турнир для N игроков, так,
чтобы все сыграли друг с другом за наименьшее число туров (например,
для четного N будет N-1 туров по N/2 матчей в каждом.
Интересует алгоритм составления расписания.

Задачи, связанные с шахматами, в которых я не силён и достойно
проконтролировать решения не могу, однако мне они кажутся великолепными,
и кому-то может быть интересно порешать:

7. Профессор Мориарти и полковник Моран играют в шахматы по телеграфу.
Они пересылают ходы пользуясь стандартной краткой нотацией:
указывается номер хода, затем фигура, делающая ход (если ходит пешка,
то указывается только конечное поле; при взятии пешкой указывается
вертикаль, на которой она стояла, и конечное поле),
поле на которое делается ход. Также отмечаются взятия, шахи и маты.
Например: 27.Ke5 (на двадцать седьмом ходу белые сыграли конем на е5),
12...Ф:e3+ (на двенадцатом ходу черный ферзь взял белую фигуру на поле е3
и объявил шах), 42.d8Лх (белая пешка идет на d8 превращается в ладью и
объявляет мат).
Шерлок Холмс переоделся в почтальона и перехватил телеграмму с очередным ходом.
После этого, при помощи дедуктивного метода, ему удалось однозначно востановить
все предыдущие ходы в партии. Пример: Холмс перехватил ход 2...Л:a5.
Тогда вся партия была такой 1.b4 a5 2.ba5 Л:a5
Какова максимальная длина такой партии?

8. Правила, по которым ходит шахматная фигура, можно описать в виде
множества векторов всех возможных ходов. Например, для коня это множество
содержит 8 векторов:
{(1,2), (1,-2), (2,1), (2,-1), (-1,2), (-1,-2), (-2,1), (-2,-1)}
Однако можно и придумать какую-нибудь новую фигуру
с другим набором ходов. Например, {(1,1),(-1,1),(1,-1)}

Можно ли придумать такую фигуру, назовем ее "дракон", которая обладает двумя свойствами:
1) Дракон из любой клетки шахматной доски может добраться до любой другой клетки (за один или несколько ходов)
2) На шахматной доске можно расставить более 32 драконов так, чтобы они не били друг друга

Если драконов не существует, докажите это. Если существуют, то какое максимальное число драконов можно разместить на шахматной доске?

← →
Vlad Oshin © (2006-04-07 14:45) [1]

> 8. Правила, по которым ходит шахматная фигура, можно описать
> в виде
> множества векторов всех возможных ходов. Например, для коня
> это множество
> содержит 8 векторов:
> {(1,2), (1,-2), (2,1), (2,-1), (-1,2), (-1,-2), (-2,1),
> (-2,-1)}
> Однако можно и придумать какую-нибудь новую фигуру
> с другим набором ходов. Например, {(1,1),(-1,1),(1,-1)}
>
> Можно ли придумать такую фигуру, назовем ее "дракон", которая
> обладает двумя свойствами:
> 1) Дракон из любой клетки шахматной доски может добраться
> до любой другой клетки (за один или несколько ходов)
> 2) На шахматной доске можно расставить более 32 драконов
> так, чтобы они не били друг друга
>
> Если драконов не существует, докажите это. Если существуют,
> то какое максимальное число драконов можно разместить на
> шахматной доске?

Имхо, драконов не существует. Потому что, ставя дракона и назначая ему хоть один ход, на том поле, куда он пойдет автоматически не должен стоять другой дракон. Таким образом, добавляя 1 дракона, исключаем 2 поля доски.
Т.е. лучший дракон - конь. Их можно поставить 32.

← →
ferr © (2006-04-07 14:49) [2]

> В массиве длины N содержатся все целые числа от 0 до
>N, кроме
> какого-то одного. Найти пропущенное число, если
>использовать
>дополнительные массивы нельзя.
> А что, если пропущено два числа?

поясните пожалуйста...
А то очень много решений лезет за N*log(N), но ясно что так не правильно. Какая оценка?

← →
Ega23 © (2006-04-07 14:52) [3]

> Остальные четверо, в числе которых Иванов, Егоров и Васильев,
> - блондины.

Но-но! Нифига я не блондин! :о)

← →
Sandman25 © (2006-04-07 14:55) [4]

5. Весы со стрелкой?

← →
MBo © (2006-04-07 14:57) [5]

>Vlad Oshin
>Таким образом, добавляя 1 дракона, исключаем 2 поля доски.
Этого недостаточно - ведь он может стоять так, что ход будет за пределы доски.

>ferr © (07.04.06 14:49) [2]
>Какая оценка?
Ну оценка - это, думаю, в данном случае - слишком сильная подсказка.

← →
Kaban (2006-04-07 14:57) [6]

8.
Назовем драконом фигуру, которая движется на 1 клетку вправо, влево, вверх, вниз (ограниченная версия ладьи). Расставим драконов по черным (белым) клеткам.

Очевидно, что оба условия выполняются

← →
MBo © (2006-04-07 14:58) [7]

>Sandman25 © (07.04.06 14:55) [4]
>5. Весы со стрелкой?

Чашечные больше-меньше

← →
Kaban (2006-04-07 14:58) [8]

а более, сори...

← →
ferr © (2006-04-07 14:59) [9]

8) {-8, -8} {1, 0} {0, 1}
расставить как шашки

← →
MBo © (2006-04-07 14:59) [10]

>Kaban (07.04.06 14:57) [6]
второе условие - больше 32

← →
antonn © (2006-04-07 15:01) [11]

5. делим на 2 группы, по 5 штук. взвешиваем - если равны идем дальше (у нас в каждой группе минимум по 1 настоящей).
берем одну из этих групп, и в ней отбираем по 2 монеты и взвешиваем. Оставшуюся монету взвешиваем с одной из этих 4х. Если группы по 2е равны по весу и равны по весу 1 оставшаяся и одна из группы => все настоящие.

← →
ferr © (2006-04-07 15:04) [12]

глупость запостил...

← →
Kaban (2006-04-07 15:08) [13]

3.

1. Каждому числу от 0 до N поставить в соответствие N первых простых чисел

2. Во время первого прохода цикла посчитать произведение простых чисел, соответствующих элементам массива

3. Во время второго прохода цикла вычислить остаток от деления произведения на простое число соответствующее индексу массива

4. Если остаток не равен 0, искомое число найдено

5. Нужен механизм для работы с ОЧЕНЬ большими цифрами :)))

← →
MBo © (2006-04-07 15:11) [14]

>Kaban (07.04.06 15:08) [13]
Не надо больших чисел, пусть будут разумные.

>antonn © (07.04.06 15:01) [11]
А если на втором шаго попалось ФН=ФН
Как однозначно для оставшейся монеты выяснить?

← →
Sandman25 © (2006-04-07 15:18) [15]

const s = "это предложение содержит одиннадцать слов, двадцать шесть слогов, семьдесят три буквы; function Letters: integer; var I : integer; begin Result := 0; for I := 1 to length(s) do if not (s[I] in [" ", ","]) then inc(Result); end; function Slogov: integer; var i : integer; begin result := 0; for I := 1 to length(s) do if s[I] in ["à", "ÿ", "î", "¸", "è", "û", "ó", "þ", "å", "ý"] then inc(result); end; begin Caption := IntToStr(slogov) + " " + IntToStr(Letters); end;

← →
McSimm © (2006-04-07 15:24) [16]

Это предложение содержит восемьдесят пять букв, двадцать шесть слогов, одиннадцать слов
Это предложение содержит восемьдесят шесть букв, двадцать шесть слогов, одиннадцать слов
Это предложение содержит восемьдесят восемь букв, двадцать восемь слогов, одиннадцать слов

← →
antonn © (2006-04-07 15:25) [17]

MBo © (07.04.06 15:11) [14]
А если на втором шаго попалось ФН=ФН
Как однозначно для оставшейся монеты выяснить?
значит на 3ем шаге взять одну из групп ФН, а в другой группе поменять одну монету на "оставшуюся" и взвесить:)

← →
Vlad Oshin © (2006-04-07 15:30) [18]

> Vlad Oshin
> >Таким образом, добавляя 1 дракона, исключаем 2 поля доски.
>
> Этого недостаточно - ведь он может стоять так, что ход будет
> за пределы доски.

но тогда он не обойдет доску!

← →
Jeer © (2006-04-07 15:46) [19]

Kaban (07.04.06 15:08) [13]

Все проще:)
Вот неоптимальный:

1. Отсортировать массив на месте.
2. Циклом пройти до первого несовпадения индекса и значения.

> 3. В массиве длины N содержатся все целые числа от 0 до
> N, кроме
> какого-то одного. Найти пропущенное число, если использовать
> дополнительные массивы нельзя.
> А что, если пропущено два числа?

← →
McSimm © (2006-04-07 15:46) [20]

> Sandman25 © (07.04.06 15:18) [15]

неправильно :)
по условию "содержит _ букв"

> семьдесят три буквы

← →
Sandman25 © (2006-04-07 15:54) [21]

McSimm © (07.04.06 15:46) [20]

А что делать, великая русский языка :)
Вы лучше у себя число букв пересчитайте :)

← →
McSimm © (2006-04-07 15:56) [22]

> число букв пересчитайте

ой :)))

← →
MBo © (2006-04-07 16:09) [23]

>antonn © (07.04.06 15:25) [17]
>значит на 3ем шаге взять одну из групп ФН, а в другой группе поменять одну монету на "оставшуюся" и взвесить:)

Сам понимаешь - мы еще не знаем - пары ФН или другие одинаковые

>Sandman25 © (07.04.06 15:18) [15]
коварный переборщик ;)

Vlad Oshin © (07.04.06 15:30) [18]

> Vlad Oshin
>но тогда он не обойдет доску!

Не исключено, что могут существовать драконы, для которых есть нужная расстановка, причем часть битых полей за краем, а внутренние битые - бьются многими фигурами сразу

← →
Sandman25 © (2006-04-07 16:09) [24]

Если с "букв", то
этопредложениесодержитодиннадцатьсловдвадцатьсемьслоговсемьдесятчетыребукв

← →
Sandman25 © (2006-04-07 16:10) [25]

MBo © (07.04.06 16:09) [23]

Перебор был сначала уменьшен на бумаге (число слов, 10-11), потом я устал считать буковки :)

← →
McSimm © (2006-04-07 16:12) [26]

> Если с "букв", то

А если без "четыре букв" и без пробелов-запятых, то решений найти не могу :(

← →
MBo © (2006-04-07 16:22) [27]

>McSimm
73-26-11 у sandman - верное решение

← →
McSimm © (2006-04-07 16:38) [28]

Значит я неправильно понял условие.
Я полагал, что из реальной фразы спрятаны слова и их надо найти.
поэтому варианты "в этом предложении 73 букв" - исключил из рассмотрения.
Надо было добавить, что слова необходимо изменять в соответвии с грамматикой.

← →
Sandman25 © (2006-04-07 16:38) [29]

3.
Result := 0;
for I := 0 to N-1 do
Result := Result xor A[I];
for I := N to Next2 do
Resutt := Result xor I;
Next2(N) - ближайшее неменьшее N число, являющееся степенью двойки.
После прохождения результат покажет, какого числа нет, если отбросить старшие биты, число сохраненных бит равно log2 (Next2(N))

← →
Sandman25 © (2006-04-07 16:41) [30]

Sandman25 © (07.04.06 16:38) [29]

for I := N+1 to Next2-1 do

← →
MBo © (2006-04-07 16:47) [31]

>Sandman25 © (07.04.06 16:38) [29]

ОК. Работает верно!

Однако задача по силам школьнику.

← →
default © (2006-04-07 16:50) [32]

3. можно пройтись циклом по массиву найдя сумму чисел массива
пропущенно число: [0+1+2+...N] - CalcSum
0+1+2+...N=N(N+1)/2

← →
Sandman25 © (2006-04-07 16:51) [33]

MBo © (07.04.06 16:47) [31]

Однако задача по силам школьнику.

Естественно. Если под этим понимать уровень необходимых знаний. Однако хотел бы я посмотреть на этого школьника :)

← →
Sandman25 © (2006-04-07 16:53) [34]

default © (07.04.06 16:50) [32]

Слона-то я и не заметил :)

← →
MBo © (2006-04-07 16:54) [35]

>Sandman25 © (07.04.06 16:51) [33]
> Однако хотел бы я посмотреть на этого школьника :)

[32]
;)

← →
Sandman25 © (2006-04-07 16:57) [36]

MBo © (07.04.06 16:54) [35]

Уже видел, сижу пристыженный :)
Кстати, я сдаюсь насчет 5 задачи. Ответы будут в понедельник?

← →
Jeer © (2006-04-07 16:57) [37]

Sandman25 © (07.04.06 16:51) [33]

Никто никого не ограничивает в методах.
Как снизу, так и сверху:))

← →
MBo © (2006-04-07 17:06) [38]

>насчет 5 задачи.
Она IMHO весьма сложная, так что сдаваться быстро не стоит.
Первый шаг - как antonn написал, по 5 на чашку.
На каждом шаге, если разный вес, становится ясно, что фальшивые есть, поэтому можно рассматривать только случаи одинакового веса.
Для одного взвешивания это наборы на каждой чашке
ННННН
ННННФ
НННФФ
ННФФФ
НФФФФ
Дальше пока помолчу.

← →
Symbios © (2006-04-07 17:06) [39]

<<5. У вас имеется 10 монет, среди которых могут быть и фальшивые.
Известно, что настоящие монеты весят одинаково, и фальшивые
(если они есть) тоже весят одинаково). Кроме того, известно, что
хотя бы одна из монет - настоящая.
Как за 3 взвешивания подтвердить или опровергнуть, что все ваши
монеты - настоящие>>

хорошая задача!!!

Могу предложить задачку попроще, но с единственным решением.

Есть 5 ящиков с золотом, из них один с фальшивым. Известно что фальшивое легче настоящего. Одним взвешиванием определить ящик с фальшивым золотом.

← →
antonn © (2006-04-07 17:10) [40]

MBo © (07.04.06 16:09) [23]
Сам понимаешь - мы еще не знаем - пары ФН или другие одинаковые
угу, в 12 ночи еще не работается:)
я так понял, задача сводится к определению 2 замеров из 5 монет, где одна точно настоящая?
тогда может так (монеты - 12345):
5+2 = 3+4
1+5 = 3+4
если выполняется, значит все настоящие.

← →
antonn © (2006-04-07 17:10) [41]

MBo © (07.04.06 17:06) [38]
зачем подсказывать? :)

← →
MBo © (2006-04-07 17:19) [42]

>зачем подсказывать? :)
Это только инициирование, чтобы по изначально неверному пути не ходили. Там ещё много над чем подумать осталось

>5+2 = 3+4
>1+5 = 3+4
>если выполняется, значит все настоящие.
контрпример: ФНФНН

← →
Sandman25 © (2006-04-07 17:24) [43]

MBo © (07.04.06 17:06) [38]

Спасибо за намек, подумаю на выходных.

← →
antonn © (2006-04-07 17:24) [44]

Symbios © (07.04.06 17:06) [39]
Есть 5 ящиков с золотом, из них один с фальшивым. Известно что фальшивое легче настоящего. Одним взвешиванием определить ящик с фальшивым золотом.
если весы показывают вес и известен вес монет:
из первого ящика берем 1 монету, из второго 2, из третьего 3...
ложим на весы. считаем на калькуляторе теоретический вес всех положенных монет как настоящих. взвешиваем, и отнимаем от теоретического и смотрим, в какой колонке "недобор"...

имхо, если весы true/false, и не известен вес - в один завес не пройдет...

← →
antonn © (2006-04-07 17:27) [45]

MBo © (07.04.06 17:19) [42]
контрпример: ФНФНН
н+н = ф+н //бумс, и перевесило
ф+н = ф+н
или я чего то не понял?.. Три раза должно быть равно

← →
antonn © (2006-04-07 17:30) [46]

а если наоборот...

← →
oldman © (2006-04-07 17:31) [47]

При 1-м взешивании 5:5, если а=b, имеем 9 вариантов расположения:

12 34 5

ФН ФН Ф
ФН ФН Н
ФФ ФН Ф
ФФ ФН Н
ФФ ФФ Н
ФФ ФФ Ф (быть не может из условия)
НН ФН Н
НН ФН Ф
НН НН Ф
НН НН Н
далее проводим два взвешивания: (1+2):(3+5) и (1+2):(4+5)
Если при обоих взвешиваниях а=b, все монеты настоящие,
Если хоть при одном a<>b, есть хоть одна фальшивая.
Проверяйте, опровергайте. :)

← →
antonn © (2006-04-07 17:39) [48]

oldman © (07.04.06 17:31) [47]
ФНФФН

← →
MBo © (2006-04-07 17:54) [49]

>antonn © (07.04.06 17:27) [45]
Я неправильно записал:
ННФНФ
3,4 - ФН
1,5 и 2,5 - тоже ФН

← →
Yar_Guest (2006-04-07 18:05) [50]

4. Дмитриев?

>Yar_Guest (07.04.06 18:05) [50]
>4. Дмитриев?

Верно

MBo © (07.04.06 17:54) [49]
ну я так и понял - [46] :)

oldman © (07.04.06 18:06) [51]
я про то, что если по порядку попадется ФНФФН, то получим:
(1+2):(3+5) - Ф+Н : Ф+Н
(1+2):(4+5) - Ф+Н : Ф+Н
небыло ниодного <>, значит нет фальшивых? :)

> antonn © (07.04.06 18:25) [53]

С вероятность 50% либо угадаем, либо нет... :(
Щас еще подумаю. Должен же быть простой ответ. Я знаю задачки МВо. :)))

oldman © (07.04.06 18:27) [54]
С вероятность 50% либо угадаем, либо нет... :(
но факт, что может быть, вероятностей здесь быть не должно:)
а то так я с вероятность 50% могу динозавра живого встретить - либо встретить, либо нет:))

oldman © (07.04.06 18:27) [54]
Щас еще подумаю. Должен же быть простой ответ. Я знаю задачки МВо. :)))
может оторваться от 5 монет и 2 взвеса? я спать пойду, а вы отрывайтесь:))

4. Дмитриев

вот ж... уже решили

2МВо

Первое взвешивание 5:5 - правильное решение?

5.
берём любые четыре монеты
могут быть следующие комбинации:
НННН
НННФ( + ННФН, НФНН, ФННН)
ННФФ(+ НФНФ, НФФН, ФФНН, ФНФН, ФННФ)
НФФФ(+ ФНФФ, ФФНФ, ФФФН)
ФФФФ,
из оставшихся берём любые две монеты и взвешиваем их
при равновесии могут быть следующие комбинации:
НН
ФФ
вариант ФФФФ и ФФ одновременно - невозможен по условию задачи
берём теперь две монеты вышевзвешенные и начинаем взвешивать их с двумя монетами четвёрки два раза по схеме: abcd, ef ---> ab, ef; cd, ef
как видно из выписанных комбинаций, только в случае всех настоящих монет равновесие не нарушится ни на каком из взвешиваний

пардон, что-то я совсем ерунду написал

присоединяюсь к вопросу [59]

>Первое взвешивание 5:5 - правильное решение?

В известном мне решении первое взвешивание именно такое.

5.
первый ход: 5:5 abcde fghij
дальше берём из одной кучки в пять монет четыре любые(fghi) и сравниваем
с другой кучкой из пяти монет два раза по схеме: abcd:fghi, bcde:fghi
если равновесие не нарушилось нигде, то монеты все настоящие
неверующие в работоспособность метода могут выписать комбинации и проверить

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

5. Вобщем если есть монеты a,b,c,d,e,f,g,h,i,j

Делаем три взвешивания. Если в результате хотя бы в одном случае был перевес одной из групп то можно утверждать что в среди монет есть.
Рассмотрим случай когда все три раза весы будут уравновешены:

1 взвешивание a+b+c+d+e = f+g+h+i+j

если равенство выполняется следовательно количество нормальных монет - четное. т.е. >=2

2 взвешивание a+b+c+d = e+f+g+h

если выполняется это равенство значит среди этих восьми монет опять таки четное кол-во >=2 нормальных монет.

отсюда вывод монеты i и j одинаковы . i=j, также видно что монета e имеет ту же фальшивость/нефальшивость (i=j=e)

по второму взвешиванию видно что среди монет e,f,g,h -минимум одна нормальная.

значит третье взвешивание:
3. Взвешиваем f+g+h=e+i+j
А так как известно что e=i=j и то что хотя бы одна монета из шести должна быть нормальной, то видим что все шесть нормальные, а из этого по результатам второго взвешивания видно что первые 4 монеты тоже нормальные.

SergP © (08.04.06 20:53) [66]
ага
первые два взвешивания я такие пробовал, но вот наличие нормальных монет не делал поэтому третье взвешивание не шло

> default © (09.04.06 01:41) [67]

Я тоже долго не мог понять как, пока не написал на бумаге:
a+b+c+d+e = f+g+h+i+j
a+b+c+d = e+f+g+h

и тогда я увидел что 2*e=i+j
а так как i=j то e=i=j

SergP © (09.04.06 08:59) [68]
я точно тоже самое писал!
только вот инвариант - наличие настоящих монет, не использовал поэтому третий шаг не был виден

3.
для случая 2 пропущенных чисел, если N достаточно небольшое, можно так:
a+b=[0+1+2+...+N]-CalcSum=k1 (1), (по ранее изложенному)
проходя по массиву считаем произведение чисел(если нуль встретился, то на него не умножаем)
если нуль не встретился, то ответ: 0, k1
если нуль есть, то считаем:
ab=(1*2*...*N)/(CalcProduct)=k2 (2)
далее из уравнений (1) и (2) находим a и b
на оптимальность не претендую

Пятничные задачки Найти похожие ветки