Задачка про визирей

← →
default © (2005-01-24 09:41) [80]

марсианин © (23.01.05 23:14) [55]
я уже понял, просто экзамен был, невыспанный вчера был, извини

← →
MBo © (2005-01-24 10:02) [81]

>default © (23.01.05 18:38) [30]
>да и MBo тоже, интересно было бы его решение посмотреть

твое решение лучше и наглядней.

procedure ReOrder(var a: array of Integer); var n, Start, SwapPos: Integer; begin n := Length(a); Start := 1; while true do begin SwapPos := Start; while true do begin if Odd(SwapPos) then SwapPos := n - 1 - (SwapPos div 2) else SwapPos := SwapPos div 2; if SwapPos = Start then Break; Swap(a[SwapPos], a[Start]); end; while a[Start] > a[Start - 1] do begin if Start = n div 2 then Exit; Inc(Start); end; end; end;

марсианин © (23.01.05 20:44) [45]

> [29] default © (23.01.05 18:38)
> 1. Дан массив, содержащий некоторую перестановку чисел 0..N-1
> Отсортировать его за О(N) операций и с O(1) доп. памяти.

>тоже не понимаю.. ведь это рядовая задача сортировки. быстрая >сортировка требует O(n*log n) операций, а нам чего, нужно >изобрести алгоритм СУПЕР-сортировки???

Сортировка произвольных данных действительно O(n*log n), но у нас есть очень важная информация о числах в массиве - то, что они не повторяются, представляют собой набор последовательных целых от 0 до n-1, т.е. для каждого элемента известно его место.

← →
default © (2005-01-24 10:10) [82]

кстати задача [29] решима и достаточно просто особенно на фоне ветки в [36], но туда лучше не смотреть - нечестно!
kaif © (24.01.05 00:40) [70]
Вы решили задачу нарушив правила, пальцы загибать нельзя, тогда
уж проще чтобы каждый называл колпак впереди стоящему, просто делая паузы в ответе - тут заподозрить невозможно - мало-ли я думаю - перед смертью не надышишься как говорится...

← →
MBo © (2005-01-24 10:31) [83]

>default © (24.01.05 10:10) [82]
>кстати задача [29] решима и достаточно просто
Да, она несравненно проще.

← →
default © (2005-01-24 10:44) [84]

MBo © (24.01.05 10:02) [81]
я тоже хотел это вариант проверить!переставлять я так стал с самого начала, но вот до определения следующего элемента Start дело не дошло, после своего варианта хотел и этот проверить, но не стал - всё равно времени лучше линейного в данной задаче быть не может...

← →
palva © (2005-01-24 12:21) [85]

Я даже вычислил фамилию последнего визиря. Это был Илларионов.

← →
kaif © (2005-01-24 13:51) [86]

default © (24.01.05 10:10) [82]
кстати задача [29] решима и достаточно просто особенно на фоне ветки в [36], но туда лучше не смотреть - нечестно!
kaif © (24.01.05 00:40) [70]
Вы решили задачу нарушив правила, пальцы загибать нельзя

Я решал уже с расчетом продать идею губернаторам. Пальцы гнуть они умеют.

← →
uw © (2005-01-24 14:07) [87]

kaif © (24.01.05 00:25) [64]
...Если его казнили (это главная информация), то одним черным меньше - теперь черных нечетное число.

А как ты понял, что именно эта информация главная?

← →
uw © (2005-01-24 15:05) [88]

kaif © (24.01.05 00:25) [64]

И еще вопрос: почему, после того как этого черного убрали, паритет черных опять стал нечетным?

← →
default © (2005-01-24 17:34) [89]

MBo © (24.01.05 10:02) [81]
хотя вру, я по-другому переставлял

← →
default © (2005-01-25 23:33) [90]

Собрал султан N своих мудрецов и поместил в темницу
сказал им: завтра вас выведут на площадь
поставят в колонну по 1 человеку
каждому на голову наденут колпак
одного из трех цветов - красный, зеленый, синий
причем стоящий сзади будет видеть цвета колпаков каждого стоящего впереди него
но не будет видеть цвета колпака тех, кто за ним и своего собственного
каждую минуту будут бить в гонг и при этом один мудрец должен сказать цвет колпака
если этот цвет совпадет с цветом его колпака - он останется в живых
если нет - ему отрубят голову
в случае молчания головы отрубят всем
(каждый раз цвет называет разный мудрец, разумеется)
мудрецы за ночь посовещались и придумали алгоритм
сколько мудрецов можно 100% спасти
нужно решение с максимум 1 потерянным мудрецом
трёхмерная вариация первой задачи, сложнее

← →
jack128 © (2005-01-26 00:35) [91]

default © (25.01.05 23:33) [90]
Так вроде то же решение, что и для "двумерной" задачи катит.
обозначим 0 - красный колпак, 1 - зеленый, 2 - синий. Первый визирь называет сумму колпаков по модулю 3. Каждый следующий исходя из услышанного и того, что он видит перед собой может назвать цвет своего колпака (его цвет = 3 - (сумма колпаков, которые он видит + плюс сумма того, что он слышал)...

← →
jack128 © (2005-01-26 00:35) [92]

jack128 © (26.01.05 0:35) [91]
его цвет = 3 - (сумма колпаков, которые он видит + плюс сумма того, что он слышал) div 3

← →
jack128 © (2005-01-26 00:54) [93]

jack128 © (26.01.05 0:35) [92]
его цвет = 3 - (сумма колпаков, которые он видит + плюс сумма того, что он слышал) mod 3
пора спать :)

← →
default © (2005-01-26 08:27) [94]

jack128 © (26.01.05 00:54) [93]
что-то я не понял
какая сумма колпаков?если всех, то она известна заранее и получается никто не погибнет, а минимум 1 всегда может
если какого-то цвета, то ерунда получается

default © (26.01.05 8:27) [94]
блин, аналогии со своим же решением [13] не видишь? В твоем решении последний визирь называет сумму по модулю два, а у меня по модулю 3, вот и вся разница. C формулой я , возможно, действительно намудрил, вот программка иллюстрирующая алгоритм

//визири индексируются так, как они стоят в коллоне, а не так, как они говорят цвет своего колпака
procedure TForm1.Button1Click(Sender: TObject);
const
N = 50; // кол-во цветов
Count = 100; // кол-во визирей

function Check(Index: Integer; Arr: array of Integer): boolean;
var
i: Integer;
LSum, RSum: Integer;
begin
LSum := 0;
for i := low(Arr) to Index - 1 do
inc(LSum, Arr[i]);
// LSum - Сумма тех колпаков, которые он видит
RSum := 0;
for i := Index + 1 to high(Arr) - 1 do
inc(RSum, Arr[i]);
// LSum - Сумма тех колпаков, которые он слышал, за исключением последнего визиря, он называл не цвет своего колпака, а вычисленную величину
i := (LSum + RSum + Arr[Index]) mod N; // это то, что назвал последний визирь
i := i - (LSum + RSum) mod N;
if i < 0 then inc(i, N);
Result := i = Arr[Index];
end;

var
Visirs: array[0..Count - 1] of Integer;
i: Integer;
begin
for i := Low(Visirs) to high(Visirs) do
Visirs[i] := Random(N);
for i := low(Visirs) to high(Visirs) do
if not Check(i, Visirs) then
raise Exception.Create("Opps " + IntToStr(i));
end;

initialization
Randomize;

jack128 © (26.01.05 12:12) [95]
понятно
на счёт аналогии - я в первом варианте оперировал с чётностью, а не с остатком(хоть численно это одно и тоже) поэтому прямой аналогии нет тут

default © (26.01.05 12:35) [96]
я в первом варианте оперировал с чётностью, а не с остатком(хоть численно это одно и тоже)
А что такое четность числа?

jack128 © (26.01.05 12:39) [97]
я же писал в [96]
хоть численно они и равны прямой аналогии НЕТ!
это чистая психология!если бы я оперировал остатком то обобщение я бы тоже моментально сделал на любое число цветов, вот в чём дело

default © (26.01.05 12:42) [98]
чистая психология!
А. Ну это да.. Я нашел решение быстро, потому что решал исходную задачу через XOR, который тоже является суммой по модулю..

В условии не сказано, можно ли называть цвет колпака стоящего впереди. Значит можно 8)

Задачка про визирей Найти похожие ветки