Задача на вероятнось Опции

[Witaliy]

Задание
Все чистые носки сохраняются в большой и глубокой коробке. Всего в ней находится N левых и M правых носков. Автор решил через нехватку времени избрать две наугад. Подсчитайте, какая вероятность того, что автор выбрал именно одну левую и один правый носок.
Входные данные
В единственной строке заданы два числа N и M – количество левых и правых носков в коробке.
Исходные данные
Выведите вероятность того, что избраны наугад два носка окажутся правыми и левыми, соответственно. Ответ следует вывести в виде несократимой арифметической дроби a/b.
Ограничение:
0 <= N,M <= 106
2 <= N+M.
Пример введения 1
4 5
Пример введения 2
7 0
Пример выведения 1
5/9
Пример выведения 2
0/1

Понятия не имею как решаються подобные задачи, буду благодарен за любую помощь.
Спасибо.

[Lapp]

Понятия не имею как решаються подобные задачи

"Подобные задачи" решаются примерно так:

var
  i,m,n,a,b: integer;

begin
  ReadLn(m,n);
  a:=2*n*m;
  b:=(n+m)*(n+m-1);
  for i:=2 to (n+m)*(n+m-1) do while (a mod i=0)and(b mod i=0) do begin
    a:=a div i;
    b:=b div i
  end;
  WriteLn(a,'/',b);
  ReadLn
end.

[Witaliy]

Отлично роботает, но есть тайм лимит... наверно в сокращении дроби.. помогите пожалуйста.

[volvo]

Ну, избавься от цикла: найди НОД a и b, и подели оба числа на него (так будет немного быстрее, чем гонять цикл)... Хотя я даже не представляю, что надо задать во входных данных, чтобы был тайм-лимит.

[Witaliy]

Для найдения НОД тоже нужно такой-же цикл

[volvo]

Нет, не такой же... Для того, чтобы найти НОД чисел 102 и 106, достаточно 7 итераций (то есть, всего 7 раз числа будут сравниваться с 0, и будет браться остаток от деления большего на меньшее)... В вышеприведенном задании (a mod i = 0) и (b mod i = 0) проверяется 43055 раз при тех же входных данных. А это и взятие остатка, и проверка на 0. Почувствуй разницу...

[Witaliy]

Да, єто правда.
Вот я вроде сделал:

var
  m,n,a,b: int64;
   i : longint;
begin
  ReadLn(m,n);
  a:=2*n*m;
  b:=(n+m)*(n+m-1);
  while (a mod 2 = 0) and (b mod 2 = 0) do
   begin
   a := a div 2;
   b := b div 2;
   end;
    while (a mod 3 = 0) and (b mod 3 = 0) do
   begin
   a := a div 3;
   b := b div 3;
   end;
     while (a mod 5 = 0) and (b mod 5 = 0) do
   begin
   a := a div 5;
   b := b div 5;
   end;
       while (a mod 7 = 0) and (b mod 7 = 0) do
   begin
   a := a div 7;
   b := b div 7;
   end;
  if (a=0) then
  WriteLn(0,'/',1)
 else
   if (b=0) then
  WriteLn(1,'/',0)
 else

  WriteLn(a,'/',b)
end.

Но где-то неверный ответ, подскажите пожалуйста в чем может быть проблема.
Спасибо.

Сообщение отредактировано: Witaliy - 26.02.2009 16:28

[volvo]

А что, обязательно делать вручную? Между прочим, семеркой простые числа не заканчиваются, тогда и 11 проверяй, и 13, и так далее... Чего ты остановился?

Я бы сделал так:

function GCD (A: longint;  B: longint): longint;
begin
  while (a <> 0) and (b <> 0) do
    if a >= b then a := a mod b else b := b mod a;
  GCD := a + b;
end;

var
  m,n,a,b: longint;
  nod: longint;
begin
  ReadLn(m,n);
  a:=2*n*m;
  b:=(n+m)*(n+m-1);

  nod := GCD(a, b);
  writeln(a div nod, '/', b div nod);
  ReadLn
end.

и ЧТО тут может не работать???

[Witaliy]

тут извините, N <= 1000000, я ошибся. Для 1 1000000 зависает программа (лимит времени 5 сек). В мое программе выше проходит тот тест, что с вашей не проходит, но на следующих северный ответ. Я понима. что ваш вариант отличен, но что-то в нем неверно.

Сообщение отредактировано: Witaliy - 26.02.2009 17:15

[Lapp]

N <= 1000000 ... (лимит времени 5 сек)

Это нужно было сказать раньше (и не в скобках). Ессно, я расслабился при N<=106 ..
Деза, батенька!

[Witaliy]

Очень прошу извинения, не посмотрел..... помогите пожалуйста сделать что-то
спасибо.

[volvo]

Не знаю, чего там у тебя зависает, но:

function GCD (A: int64;  B: int64): int64;
begin
    while (a <> 0) and (b <> 0) do
      if a >= b then a := a mod b else b := b mod a;
    GCD := a + b;
end;

var
  m,n, a,b: int64;
  nod : int64;
begin
  ReadLn(m,n);
  a:=2*n*m;
  b:=(n+m)*(n+m-1);

  nod := GCD(a, b);
  writeln(a div nod, '/', b div nod);

  // Ну, дальше уже твои художества... 
  while (a mod 2 = 0) and (b mod 2 = 0) do
   begin
   a := a div 2;
   b := b div 2;
   end;
    while (a mod 3 = 0) and (b mod 3 = 0) do
   begin
   a := a div 3;
   b := b div 3;
   end;
     while (a mod 5 = 0) and (b mod 5 = 0) do
   begin
   a := a div 5;
   b := b div 5;
   end;
       while (a mod 7 = 0) and (b mod 7 = 0) do
   begin
   a := a div 7;
   b := b div 7;
   end;
  if (a=0) then
  WriteLn(0,'/',1)
 else
   if (b=0) then
  WriteLn(1,'/',0)
 else
  WriteLn(a,'/',b)
end.

прекрасно выдает (причем мгновенно) оба ответа. И оба - одинаковые, что характерно... Ты типы параметров-то менял на int64???

[Witaliy]

Да, прошло (без моих художеств )!!! Не понимаю только в чем разница...

Добавлено через 2 мин.
Наверно из-за типа longint в переменной nod

Добавлено через 5 мин.
Еше вопрос: можете дать еще какие-то формулы для задач с вероятностями.. если можете (и если еще какие-то есть)
Спасибо.

[мисс_граффити]

Классическое определение вероятности: Вероятность равна числу благоприятных исходов к общему числу возможных исходов.
Здесь больше ничего не надо. А вообще в теории вероятности довольно много формул... +комбинаторика еще.