Скачать: CL | DM;

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

← →
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 + " &#232; " + 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]

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

---

← →
MBo ©   (2009-10-09 14:44) [29]

>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, оставшегося присоединяем к хвосту списка, повторяем с первой парой и т.д.

---

← →
McSimm ©   (2009-10-09 14:53) [30]

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

---

← →
oldman ©   (2009-10-09 15:59) [31]

№1


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


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

---

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

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

---

← →
MBo ©   (2009-10-09 17:11) [33]

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

---

← →
Дуб ©   (2009-10-09 17:20) [34]

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

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

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

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

---

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

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

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

---

← →
Дуб ©   (2009-10-10 04:57) [36]

> Дмитрий С ©   (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, иначе уже все пофиг).
и т.д.

ИМХО

---

← →
Наиль ©   (2009-10-10 20:07) [38]

По номеру №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;

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

---

Страницы: 1 2 3 вся ветка

Скачать: CL | DM;



Память: 0.57 MB
Время: 0.01 c