Воскресная задачка :D

← →
Alexis © (2005-02-27 11:28) [0]

Решил и я выложить задачку, которая imho, заслуживает внимания...

Два друга договорились встретиться между 12 и 13 часами(включительно). Если первый приходит и не застает другого, то он ждет 16 минут, а если второй приходит и не застает первого, то он ждет 36 минут.
Какова вероятность, что они встретятся?

Удачи :D

← →
GuAV © (2005-02-27 12:16) [1]

0,34(8)

← →
GuAV © (2005-02-27 12:52) [2]

То есть нет, 1 - 0,34(8) = 0,65(1)

← →
Alexis © (2005-03-03 17:36) [3]

Ага :)
В другой раз потяжелее выложу :D

← →
default © (2005-03-03 17:53) [4]

"Дан массив, содержащий некоторую перестановку чисел 0.. N-1
Отсортировать его за О(N) операций и с O(1) доп. памяти."
Вот ещё, её MBo как-то давал
несложная

← →
Uncle Archi © (2005-03-03 20:38) [5]

default © (03.03.05 17:53) [4]
По условию, решение просто:

For i:=0 to n-1 do write(i," ");

Если просто перестановка чисел.

← →
Uncle Archi © (2005-03-03 20:51) [6]

В тему. Попробуйте решить:
"Рассмотрим выражение 1n+2n+3n+4n. На сколько нулей заканчивается его десятичная запись?"
(http://acm.timus.ru/problem.aspx?space=1&num=1295)

А решение лежит на поверхности.
Стоит только попробывать.

← →
default © (2005-03-03 21:14) [7]

Uncle Archi © (03.03.05 20:38) [5]
так низя
надо в массиве переставлять
Uncle Archi © (03.03.05 20:51) [6]
1n+2n+3n+4n=10n, умножение на 10 даёт один нул + число нулей в n
n считаю натуральным

← →
Uncle Archi © (2005-03-03 21:22) [8]

default © (03.03.05 21:14) [7]
Сори, 1n+2n+3n+4n читать как 1^n+2^n+3^n+4^n
А тебе лень на оригинал взглянуть, на Тимусе, там ведь правильно написано.

← →
MBo © (2005-03-04 09:00) [9]

>default © (03.03.05 17:53) [4]
Чтобы не возникало соблазна просто a[i]:=i сделать, можно условие, если не ошибаюсь, так сформулировать:

Массив заполняется так:
a[i]:=2*i+Random(2);
затем выполняется перестановка (случайная перетасовка)
Отсортировать за О(N) операций и с O(1) доп. памяти.

При этом для каждого значения известен целевой индекс, но не наоборот.

← →
default © (2005-03-04 18:54) [10]

Uncle Archi © (03.03.05 21:22) [8]
не сильно сложно доказать, что на конце может быть не более двух нулей
далее можно попытаться не сильно сложным методом найти нужные ограничения на n

← →
GrayFace © (2005-03-04 19:22) [11]

MBo © (04.03.05 9:00) [9]
Вот тупой алгоритм, удволетворяющий условию:
var i,j,k:integer; begin for k:=0 to n-2 do begin i:=a[k]; while (i>k+1) or (i<k) do begin j:=i; i:=a[j div 2]; a[j div 2]:=j; end; end; end;

← →
Uncle Archi © (2005-03-04 20:54) [12]

default © (04.03.05 18:54) [10]
Повторюсь: "Стоит только попробывать".
Нужно правильное решение ?

← →
default © (2005-03-04 21:45) [13]

Uncle Archi © (04.03.05 20:54) [12]
нет
у меня в голове пока только достаточно трудоёмкий путь
но решение будет эффективно если это дело до конца довести
пару условных операторов с недолго вычислимыми(думаю) выражениями...
может в вашем решении подход другой?
более вычислительноёмкий...
намекните немного

← →
default © (2005-03-04 23:33) [14]

Uncle Archi © (04.03.05 20:54) [12]
вообщем понятен принцип
как я говорил максимум в конце может быть два нуля, это можно доказать
для того чтобы данное выражение оканчивалось хотя бы на один нуль оно должно делиться нацело на 10
[1+2^n+3^n+(2^n)*(2^n)]/10=
0.1+2^(n-1)*0.2+2^(n-1)*0.2*2^n+(3^n)/10
в столбцах 1,2,3,4 расположены дробные части слагаемых при
соответствиющих n
n = 1 2 3 4 далее идёт повтор
0.1 0.1 0.1 0.1 0.1
2^(n-1)*0.2 0.2 0.4 0.8 0.6
2^(n-1)*0.2*2^n 0.4 0.6 0.4 0.6
(3^n)/10 0.3 0.9 0.7 0.1
Дроб.часть 0 0 0 0.4
суммы
отсюда видно что при каждом четвёртом значении n начиная с n=1
наше выражение будет содержать минимум один нуль
теперь аналогично нужно сделать для деления на 100, и дальше
алгоритм написать не будет составлять труда
можно, естественно, то что я написал тут и формально изложить

малость съехало...

отсюда видно что при каждом четвёртом значении n начиная с n=1
наше выражение не будет содержать ни одного нуля на конце иначе - минимум один нуль на конце

начиная с n=4
P.S. сори за невнимательность:)

default © (05.03.05 22:30) [18]
Почти, только я это делал без вычислений, я просто посчитал для первых 17 n значение суммы,
а задача решается 4мя строчками:

If n=5 then Write(2) else If n mod 4=0 then Write(0) else If n mod 4=3 then Write(2) else Write(1);

GrayFace © (04.03.05 19:22) [11]
Ошибка вышла небольшая.
var i,j,k:integer; begin for k:=0 to n-2 do begin i:=a[k]; while (i>k*2+1) or (i<k*2) do begin j:=i; i:=a[j div 2]; a[j div 2]:=j; end; end; end;

Воскресная задачка :D Найти похожие ветки