Пятничные задачки. Вася Пупкин и компания...

← →
MBo © (2009-10-09 09:46) [0]

1. Вася Пупкин пришел на карнавал. Оказалось, что он там никого не узнает,
а вот его гражданская наружность известна всем даже в маске.
Все люди пронумерованы от 1 до N. За какое минимальное время можно выяснить,
ху из мистер Пупкин, если единственное допустимое действие - вопрос i-му человеку,
знает ли он j-того (function Knows(i, j: Integer): Boolean)

2. Вася Пупкин наблюдал процесс подачи документов в ВУЗ по новым правилам.
Абитуры много, выстроилась огромная живая очередь. Каждый стоящий запоминает
стоящего прямо перед ним, и, возможно, еще кого-то одного в любом месте очереди.
Васю заинтересовала получающаяся структура данных, и он описал ее так:

Дан указатель на первый элемент односвязного прошитого списка из элементов типа
PNode = ^TNode;
TNode = record
Name: string;
Next: PNode;
Any: PNode;
end;

Next - указывает на след. элемент списка или равен Nil для последнего элемента (первый в очереди)
Any - указывает на любой элемент списка (спереди или сзади) или равен Nil.

Теперь Васе необходимо за O(N) времени создать глубокую копию исходного списка такую,
что если в исходном списке Any i-го элемента указывает на j-й элемент,
то такое же отношение должно быть и между элементами копии списка.
Допускается выделять память только под N элементов для копии списка.
Исходный список после операции копирования должен быть в исходном состоянии.

3. Васе Пупкину нужно выделить группу студентов-первокурсников для
проведения педагогического эксперимента по следующим критериям:
Сумма баллов выбранной группы должна быть максимальной. Однако соседние в списке
студенты могут быть знакомы, и одновременно их брать для участия в эксперименте
нельзя. Вася формализовал задачу так:
Дан массив натуральных чисел. Как эффективно найти подпоследовательность
с максимальной суммой при условии, что соседние элементы не могут входить в
подпоследовательность. Например, для массива [1,51,3,1,100,199,3]
maxSum = 51 + 1 + 199 = 251

4. Васе Пупкину нужно написать программу, выводящую энное по порядку из крутых
чисел. Число является крутым, если в его разложении на множители присутствуют
только простые числа из заданного списка.
Например, крутые числа для списка [2, 3]: 1, 2, 3, 4, 6, 8, 9, 12, 16...
Функция может выглядеть так:
function Cool(const N: Integer; const Primes: array of Integer): Integer;
Cool(8, [2, 3]) должно выдать 12
ДЛя простоты можно, в принципе, ограничиться списком из трех чисел.
Чему равно, например, Cool(1000, [2, 3, 5]) ?

5. Вася Пупкин пишет программу для вывода списка файлов в папке красивым образом.
Красота должна быть такая -
а) Если файлов нет - выводится {}
б) Один файл с именем A - {A}
в) Два файла A B - {A и B}
г) Более двух - {A, B и С}, или {A, B, C, D и E}
NB: запятой перед "и" нет.

Сохранять весь список и форматировать его потом - некошерно, считать файлы заранее - тоже.

P.S. В оригинале - дается нечто, поддерживающее IEnumerable. На мой взгляд, FindXXX
функции аналогичны существенным методам этого интерфейса, так что можно решать, кому как удобнее.

6. У каждого из 100 заключенных в тюрьме есть уникальный номер.
Номера всех заключенных разложили случайным образом в 100 коробок.
Коробки расставили в линию в коридоре, в который по одному пускают заключенных.
Каждый заключенный может посмотреть содержимое не более 50 коробок.
После этого он выходит из коридора через другую дверь, и никаким образом не
может передать информацию еще не входившим в комнату заключенным, т.к.
все содержимое коридора приводится к начальному состоянию.

Если все 100 заключенных найдут свои номера, их выпустят.
Если хотя бы один из 100 не найдет своего номера в 50 коробках, которые он открыл
- всех казнят. Зэки могут договориться между собой до похода первого из них в комнату
о том, как они будут открывать коробки.

Возможно ли создать стратегию, при которой у заключенных будут неплохие шансы спастись?

← →
MBo © (2009-10-09 09:58) [1]

Уточнение 1. на всякий случай:
Вася - единственный, которого знают все, а он не знает никого. Для остальных это неверно.

← →
KilkennyCat © (2009-10-09 10:26) [2]

я бы по первой задаче еще хотел бы уточнение: спрашивать вежливо?

← →
TUser © (2009-10-09 10:33) [3]

А что такое "глубокая копия"?

← →
Kolan © (2009-10-09 11:08) [4]

Глубокая копия, значить скопировать все полностью, чтобы новый список был точ-в-точ как первый.

← →
Дмитрий С © (2009-10-09 11:38) [5]

> 2. Вася Пупкин наблюдал процесс подачи документов в ВУЗ
> по новым правилам.
> Абитуры много, выстроилась огромная живая очередь. Каждый
> стоящий запоминает
> стоящего прямо перед ним, и, возможно, еще кого-то одного
> в любом месте очереди.

А в чем тут проблема? Найти самый первый элемент?

← →
Kolan © (2009-10-09 12:20) [6]

№ 5

function TForm3.FormatFileList(const Directory: string): string; var CurrentFile: TSearchRec; Delimiter: string; PreviousDelimiterPos: Integer; begin Result := ""; if DirectoryExists(Directory) then begin try PreviousDelimiterPos := -1; if FindFirst(Directory + "*.*", faAnyFile, CurrentFile) = 0 then begin repeat if (CurrentFile.Name <> ".") and (CurrentFile.Name <> "..") and ((CurrentFile.Attr and faDirectory) = 0) then begin Delimiter := ""; if Result <> "" then begin Delimiter := " и "; if PreviousDelimiterPos <> -1 then begin Result[PreviousDelimiterPos] := ","; Delete(Result, PreviousDelimiterPos+1, 1); end; PreviousDelimiterPos := Length(Result)+1; end; Result := Result + Delimiter + CurrentFile.Name end; until FindNext(CurrentFile) <> 0; end; finally FindClose(CurrentFile); end; Result := "{"+Result+"}"; end; end;

Хочется сказать Васи, что он извращенец, потому что считать список файлов сразу гораздо проще и понятнее.

← →
Bless © (2009-10-09 12:39) [7]

1) Ну, за N-1 точно можно :) Можно быстрее?

← →
Skyle © (2009-10-09 12:43) [8]

Дайте-ка я тоже попробую №5 :)

function SuperDir(AFolder : String) : String; var SR : TSearchRec; LastName : String; begin Result := ""; LastName := ""; if FindFirst(IncludeTrailingBackSlash(AFolder) + "*.*", faAnyFile, SR) = 0 then begin if (SR.Name <> ".") and (SR.name <> "..") then LastName := SR.Name; while FindNext(SR) = 0 do begin if (SR.Name <> ".") and (SR.name <> "..") and (SR.Attr and faDirectory = 0) then begin if Length(LastName) > 0 then begin if (Length(Result) = 0) then Result := LastName else Result := Result + ", " + LastName; end; LastName := SR.Name; end; end; if Length(Result) > 0 then Result := Result + " è " + LastName else Result := LastName; FindClose(SR); end; Result := "{" + Result + "}"; end;

← →
MBo © (2009-10-09 12:45) [9]

>Kolan © (09.10.09 12:20) [6]
Отлично работает!
Интересно, можно ли без трюка с Delete обойтись....

← →
MBo © (2009-10-09 12:53) [10]

>Bless © (09.10.09 12:39) [7]
> Можно быстрее?
нет.

← →
Bless © (2009-10-09 12:56) [11]

2) Допускается выделять память только под N элементов для копии списка.

Кроме этих N элементов вообще больше ни одной переменной нельзя завести?

← →
MBo © (2009-10-09 12:58) [12]

>Skyle © (09.10.09 12:43) [8]

Работает.
Тоже хитрО использует информацию о выходной строке ;)

← →
MBo © (2009-10-09 12:59) [13]

>Кроме этих N элементов вообще больше ни одной переменной нельзя завести?

Можно.
Лишние O(N) нельзя.

← →
MBo © (2009-10-09 13:16) [14]

З.Ы.
к 5.
атрибут faAnyFile - faDirectory позволит не заморачиваться на папки и точки.

← →
Bless © (2009-10-09 14:16) [15]

2)
function Clone(list: PNode); var p1, p2: PNode; begin //вставляем в список после каждого текущего узла новый узел. //т.е. список вида node1 -> node2 -> node3 превращаем в список вида node1 -> new1 -> node2 -> new2 -> node3 -> new3 p1 := list; while p1 <> nil do begin p2 := new(TNode); p2^.next := p1^.next; p1^.next := p2; p1 := p2^.next; end; //теперь разбираем наш удлиненный вдвое список на два: //- исходный //- и новый, состоящий из узлов new_i. p1 := list; if p1 <> nil then result := p1^.next; else result := nil; repeat p2^.name := p1^.name; p2 := p1^.next; p1^.next := p2^.next; if p1.next <> nil then p2^.next := p1^.next^.next; if p1^.any <> nil then p2^.any := p2.any^.next; p1 := p1^.next; until p1=nil; end;

← →
Bless © (2009-10-09 14:25) [16]

Прошу прощения, вариант выше - с ошибками. Вроде исправил. Хотя я в Delphi не проверял, поэтому уверенности, что исправил все, нет :) Но думаю, идея понятна.

function Clone(list: PNode); var p1, p2: PNode; begin //вставляем в список после каждого текущего узла новый узел. //т.е. список вида node1 -> node2 -> node3 превращаем в список вида node1 -> new1 -> node2 -> new2 -> node3 -> new3 p1 := list; while p1 <> nil do begin p2 := new(TNode); p2^.next := p1^.next; p1^.next := p2; p1 := p2^.next; end; //теперь разбираем наш удлиненный вдвое список на два: //- исходный //- и новый, состоящий из узлов new_i. p1 := list; if p1 <> nil then result := p1^.next; else result := nil; repeat p2 := p1^.next; //восстанавливаем прежнее значеие поля next у узла node_i p1^.next := p2^.next; //заполняем правильными значениеями поля name, next, any у узла new_i. p2^.name := p1^.name; if p1^.next <> nil then p2^.next := p1^.next^.next; else p2^.next := nil; if p1^.any <> nil then p2^.any := p2.any^.next; else p2^.any := nil; p1 := p1^.next; until p1=nil; end;

← →
McSimm © (2009-10-09 14:27) [17]

> 1) Ну, за N-1 точно можно

А как ? Ведь единственное доказательство, что k - Вася это
Knows[k,j] = true, j=1..N без k;
Т.е. все N-1 вопросов надо задать Васе, но для этого надо знать кто он

← →
McSimm © (2009-10-09 14:28) [18]

> Knows[k,j] = true, j=1..N без k;

= false

← →
Kolan © (2009-10-09 14:29) [19]

Bless, вы считаете, что удлинив список в двое вы соблюли условие о том, что «допускается выделять память только под N элементов для копии списка»?

← →
MBo © (2009-10-09 14:30) [20]

>Bless © (09.10.09 14:16) [15]

Супер!

← →
Дуб © (2009-10-09 14:31) [21]

> McSimm © (09.10.09 14:27) [17]

Берес чела, задаем вопрос про другого. Если "Нет", то далее. Если все Нет, то Вася. Если да, то переходим к нему(потенциальный Вася) и задаем ему исключая его и тех кого он спрашивал до этого.

← →
Bless © (2009-10-09 14:31) [22]

> Kolan © (09.10.09 14:29) [19]
>
> Bless, вы считаете, что удлинив список в двое вы соблюли
> условие о том, что «допускается выделять память только под
> N элементов для копии списка»?

Ну да. Я и выделил N НОВЫХ элементов под копию списка.
Кстати, ошибки исправил не все:
нужно поменять
else result := nil;
на
else begin result := nil; exit; end;

← →
MBo © (2009-10-09 14:32) [23]

>Kolan © (09.10.09 14:29) [19]
Да, ведь новый список все равно нужно создавать, а количество вставляемых узлов равно конечному количеству в новом списке.

← →
Дуб © (2009-10-09 14:33) [24]

> то переходим к нему(потенциальный Вася) и задаем ему исключая
> его и тех кого он спрашивал до этого.

то переходим к тому на кого да, и задаем оставшимся.

← →
McSimm © (2009-10-09 14:34) [25]

Поправка, есть два доказательства.
Knows[k,j] = false, j=1..N без k;
Knows[i,k] = true, i=1..N без k;

Например, N = 5, k = 2
* 1 1 0 1
0 * 0 0 0
1 1 * 1 1
1 1 1 * 0
0 1 0 1 *

Что-то не придумаю, как доказать любое из утверждений за N-1 просмотров

← →
Дуб © (2009-10-09 14:35) [26]

> то переходим к тому на кого да, и задаем оставшимся.

тьфу - опять криво написал. Ну, в общем понятно.

← →
Bless © (2009-10-09 14:36) [27]

> McSimm © (09.10.09 14:27) [17]
>
>
> > 1) Ну, за N-1 точно можно
>
> А как ? Ведь единственное доказательство, что k - Вася это
>
> Knows[k,j] = true, j=1..N без k;
> Т.е. все N-1 вопросов надо задать Васе, но для этого надо
> знать кто он

Берем любого человека с номером i и спрашиваем "знаешь ли ты человека с номером j?".
Если он отвечает "да", то он точно не Вася Пупкин, потому что Вася тут никого не знает и ответить "да" не может. Следовательно i-го можно исключить.
Если он отвечает "нет", то j-ый - точно не Вася Пупкин, потому что его знают все. Значит?, j-го можно исключить.
В любом случае в результате одного вопроса кого-то одного можно исключить :)

← →
MBo © (2009-10-09 14:36) [28]

>ошибки исправил не все
Главное, идея понятна.
Детали я пытался на бумажке отследить, были проблемки, но шлифовка-отладка спасет.

>McSimm
Каждый вопрос обязательно исключает одного человека из пары.
Я когда решал, разбил список на пары (при нечетном числе один отдыхает), исключил половину, остаток снова поделил на пары и т.д. Для N = 2^M понятно, что N-1 вопрос, при некруглых числах тоже можно это показать.
A-B -
C-D
E

2 вопроса

оставшийся из AB
-\\- CD
3 вопроса

ABCD
E
4 вопроса

Но линейный подход, как Дуб и Bless говорят, проще:

A-B-C-D-E
исключаем одного из A или B, оставшегося присоединяем к хвосту списка, повторяем с первой парой и т.д.

понял, спасибо

№1

> За какое минимальное время можно выяснить

Если предположить, что кто-то, кроме Пупкина, знает только одного, то минимальное время равно N попыток.
Поскольку, если предположить, что сразу попадаем на этого кого-то, то за N-1 вопрос он знает 2 человек.
На следующем вопросе все становится ясно.

← →
Franzy (2009-10-09 16:13) [32]

К 6 задаче - видимо, выигрышной стратегии нет и все решает случай. Ведь зеки не могут ни переставлять коробки, ни передавать сообщения своим и вообще как-то влиять на выбор следующих за ними. Т.е. прошедшие первыми могут помочь своим только фактом того, что найдя свой номер, увеличат шансы следующих.

>видимо, выигрышной стратегии нет
Есть стратегия с существенными шансами на успех.
Задача очень сложная, так что могу дать первоначальную наводку...

> Но линейный подход, как Дуб и Bless говорят, проще:
>
> A-B-C-D-E
> исключаем одного из A или B,

и по индукции показывается, что это минимальный ответ. Писал быстро - шел на собрание в школу, спешил.

> MBo © (09.10.09 17:11) [33]

У Шекспира кажется, почти такая же есть - при выборе жениха. По №6. 3 шкатулки и вагон участников. А вообще интересно - по теории игр.

> Есть стратегия с существенными шансами на успех.
> Задача очень сложная, так что могу дать первоначальную
> наводку...

На ум приходит только следующее:
1ый зек открывает ящики с 1-50
2ой - 2-51
3ий - 3-52
...
52ый - 1 и 52-100
53ий - 1-2 и 53-100
...
Но если подумать, то шанс при такой стратегии ничтожно мал.

> Дмитрий С © (09.10.09 19:11) [35]

Я думаю, что главное, что тут требуется, это с вероятностью 1 обеспечить выборку всех номеров. И возможно каждого номера равное число раз.

Вот доказательство пока не приведу.

> Но если подумать, то шанс при такой стратегии ничтожно мал.

Мал, но видимо выше если дать все на абс. случайный откуп. Т.к. при последнем существует ненулевая вероятность невыбрки всех номеров.

← →
SP (2009-10-10 14:44) [37]

6. Если учесть то, в случае если первый заключенный не найдет своего номера - то всех все равно казнят, не зависимо от действий остальных, то можно рассматривать только ситуацию когда он нашел свой номер. Тогда получается что второму имеет смысл искать свой номер в оставшихся 50-ти ящиках... ибо при этом вероятность будет 50/99.

Т.е. заключенные должны поделить ящики на 2 группы и искать свои номера в них по очереди.
Например:
1 зек. ящики 1-50 (вероятность 50/100=1/2).
2 зек. ящики 51-100 (если первый зек не влетел, то вероятность 50/99, иначе уже все пофиг).
3 зек. ящики 1-50 (если первые 2 зека не влетели, то вероятность 49/98, иначе уже все пофиг).
и т.д.

ИМХО

По номеру №3
Пишу, то что успел придумать 1 минуту.
Исходим из того, что все баллы положительные.
Начинаем с 2го по списку. Если число больше своих соседей, то делаем их отрицательными. Продолжаем сравнивать до предпоследнего. Находим сумму положительных чисел.
Возвращаемся в исходное состояние. Повторяем от конца к началу списка.
Сравниваем суммы и смотрим, какой из 2х вариантов лучше. Его и берём.
Метод не самый эффективный, но зато быстрый.

← →
SP (2009-10-10 20:55) [39]

> McSimm © (09.10.09 14:34) [25]
>
> Поправка, есть два доказательства.
> Knows[k,j] = false, j=1..N без k;
> Knows[i,k] = true, i=1..N без k;
>
> Например, N = 5, k = 2
> * 1 1 0 1
> 0 * 0 0 0
> 1 1 * 1 1
> 1 1 1 * 0
> 0 1 0 1 *
>
> Что-то не придумаю, как доказать любое из утверждений за
> N-1 просмотров

Да тут вроде и без примеров ясно.
i:=1; j:=N; while i<j do if know(i,j) then inc(i) else dec(j);
и в результате имеем в i - номер Васи Пупкина, а вся эта беда выполнится за N-1 итераций.

← →
SP (2009-10-10 21:09) [40]

№3
Сумму найти в принципе просто: SummaSubArray(0,A);

function SummaSubArray(i:integer; var A:array of integer):integer; var S2:integer; begin if i>high(A) then Result:=0 else if i=high(A) then Result:=A[i] else begin Result:=SummaSubArray(i+1,A); S2:=A[i]+SummaSubArray(i+2,A); if Result<S2 then result:=S2; end; end;

А вот как найти последовательность будет чуть труднее.

Пятничные задачки. Вася Пупкин и компания... Найти похожие ветки