Главная страница
Top.Mail.Ru    Яндекс.Метрика
Текущий архив: 2005.03.27;
Скачать: CL | DM;

Вниз

Воскресная задачка :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, и дальше
алгоритм написать не будет составлять труда
можно, естественно, то что я написал тут и формально изложить


 
default ©   (2005-03-04 23:34) [15]

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


 
default ©   (2005-03-04 23:37) [16]

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


 
default ©   (2005-03-04 23:39) [17]

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


 
default ©   (2005-03-05 22:30) [18]

Uncle Archi ©   (04.03.05 20:54) [12]
покатит?


 
Uncle Archi ©   (2005-03-06 10:16) [19]

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 ©   (2005-03-07 18:57) [20]

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;



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

Текущий архив: 2005.03.27;
Скачать: CL | DM;

Наверх




Память: 0.51 MB
Время: 0.043 c
1-1110424363
SerKom
2005-03-10 06:12
2005.03.27
Как узнать, есть ли обработчик события у компонента?


1-1110900914
Руслана
2005-03-15 18:35
2005.03.27
Можно ли отловить такое событие...


6-1106741376
Vadim X
2005-01-26 15:09
2005.03.27
THTTP SendForm


9-1104704810
Trip
2005-01-03 01:26
2005.03.27
Потестируйте мой скринсэйвер на GLScene ?


4-1108312250
Алексей
2005-02-13 19:30
2005.03.27
Не получается, отловить сообщения комбобокса, переполнение стека