Помогите, пожалуйста, с алгоритмом

[Sрy]

Помогите, пожалуйста, с задачкой.

Взята она с сайта с олимпиадными задачами.
Суть её следующая.
Последовательность Recaman-а определена так:

a0 = 0
Для m, больших 0:
a(m) = a(m-1) - m, если эта разность больше нуля и её до этого момента в последовательности не было;
a(m) = a(m-1) + m, иначе.

Вот первые несколько членов последовательности:
0, 1, 3, 6, 2, 7, 13, 20, 12, 21, 11, 22, 10, 23, 9...

Задание состоит в том, чтобы по введённому порядковому номеру k вывести k-ый член последовательности.

Вообще, эту задачу мне нужно сдать на Хашкеле, но пока что я хочу сдать её на другом языке, который я знаю чуть получше (ruby, C). И возникла проблема с придумыванием алгоритма, поскольку решение в лоб (в смысле, просто переписать рекуррентное соотношение, ну и добавить поиск по массиву для проверки, встречалось ли число в последовательности ) не годится для больших k (0 <= k <= 500000). Буду очень признателен, если подскажете эффективное решение данной задачи.

[luitzen]

Ну, вот тут не сообщается о каких-то способах вычисления, отличных от описанного Вами .

Наверное, если массив (или иную структуру данных) держать упорядоченной, то с поиском по нему всё будет обстоять не так плохо

У Вас опечатка?

Spy писал(а):

a(m) = a(m+1) + m

[Xaositect]

На Хаскелле красиво должно писаться это дело
Можно, например, построить бесконечное дерево, путем в котором будет последовательность

[Sрy]

luitzen писал(а):

У Вас опечатка?

Да, конечно, прошу прощения. Должно стоять a(m) = a(m-1) + m.

Вот, набросал тут на руби.

$a = [0]


def isNumberInSequence(number)
  for i in 0...$a.size-1
     if($a[i] == number)
       return true
     end
     i+=1
   end
   return false
  
end



def recaman(m)
  if(m == 0) 
    return 0
  end
   if(recaman(m-1) - m > 0 and !isNumberInSequence(recaman(m-1) - m)) 
     $a.push(recaman(m-1) - m)
     return recaman(m-1) - m
    else 
      $a.push(recaman(m-1) + m)
      return recaman(m-1) + m
    end

  
end

puts recaman(20)

Но это не совсем правильно работает. Ошибка в заполнении массива... вот только где?

[Dandan]

Зачем так извращаться и каждый раз делать поиск, просто как ассоциативный массив сохраняйте значения. Т.е. a[x]=1, если x встретилось в последовательности (по умолчанию a[x]=0 должно быть).

[Sрy]

Dandan писал(а):

Зачем так извращаться и каждый раз делать поиск, просто как ассоциативный массив сохраняйте значения. Т.е. a[x]=1, если x встретилось в последовательности (по умолчанию a[x]=0 должно быть).

Спасибо. Переписал. Избавился от рекурсии заодно. Работает.

$a = [0]
$as = []


def recaman(m)
  for k in 0..m-1
    $as[k] = 0
  end
  for i in 1..m
   if($a[i-1] - i > 0 and $as[$a[i-1]-i] == 0)
     $as[$a[i-1]-i] = 1
     $a[i] = $a[i-1] - i
     else
      $as[$a[i-1] + i] = 1
      $a[i] = $a[i-1] + i
    end
  end
  return $a[m]
  end
   
   
while((x = gets.to_i) != -1)
 p recaman(x)
end

Но для больших чисел спож выдаёт либо time limit exceeded, либо runtime error (NZEC). Нельзя ли всё-таки как-то оптимизировать алгоритм? Или эту задачу по определению нельзя сдать на руби в силу его медленности?

[Dandan]

я так понимаю в задаче даётся список индексов, а не один. А вы же для каждого индекса начинаете всё с начала. Из-за этого и TLE.

[luitzen]

Spy, мне кажется, что единственная цель этого задания — это подружить Вас с Haskell.
Дескать, попробуйте написать без циклов, на одной лишь хвостовой рекурсии. Сам с Haskell не дружу.

Для браузера написал вот что:

function recaman(n){

if (n == 0) {return 0};

var already = new Array(); // ну, как бы ассоциативный
already[0] = true;

var previous = 0;
var number = 1;

while (number <= n){
   var candidate = previous - number;
   if (candidate <= 0 || already[candidate]) {candidate = previous + number;}
   already[candidate] = true;
   previous = candidate;
   number++;
   }
   
return candidate;

}

Высчитывает recaman(500000) за пару секунд.

Интересно, кстати, иметь оценку сверху для членов этой последовательности.
Ну, типа $\forall n\; (a_{n} < 8n)$ или наподобие .

[Sрy]

Спасибо! На руби получилось Теперь пойду переписывать на Хашкель.

И ещё, вопрос по второй задачке.
Суть её такова:
Я хочу построить дом. Но у меня есть только 4 стены с длинами сторон a, b, c, d. Я хочу сделать из них четырёхугольный дом с наибольшой площадью.
На вход подаются кол-во тестовых случаев и сами случаи в виде значений четырёх сторон.
На выходе- максимальная площадь из площадей всех четырёхугольников, которые можно из этих сторон составить.

Здесь я воспользовался формулой вычисления площади произвольного четырёхугольника по его сторонам.
На руби выглядит так:

include Math

def area()
  
  str = readline.chop
str1 = str.split(' ')
a = str1[0].to_f
b = str1[1].to_f
c = str1[2].to_f
d = str1[3].to_f


s = ( a + b + c + d ) / 2.0

ar = sqrt((s-a)*(s-b)*(s-c)*(s-d))
p ar
end

n = gets.to_i
for i in 1..n
  area()
end

И это работает, на spoj.pl задачу зачли.
Теперь, переписываю на Haskell:

import System.Exit
main :: IO ExitCode
main = do str <- getLine
          run (read str)

g str = [x, y, z, a]
     where [x,y,z,a] = (map read . words) str
  
        
run :: Integer-> IO ExitCode
run 0 = return ExitSuccess
run x = do
        str <- getLine
        let [b, c, d, e] = g str
        print (geoprob b c d e)
        run (x-1) 

geoprob:: Double->Double->Double->Double->Double
geoprob b c d e = sqrt( ( p - b ) * (p - c ) * ( p - d ) * ( p - e ) )
               where p = (b + c + d + e)/2

Но тут уже вылазит TLE. Чесс говоря, не очень понимаю, как тут можно сократить время работы. Если использовать формулу площади четырехугольника как полупроизведение диагоналей на синус угла между ними, то ведь тоже вылезут квадратные корни, умножения...
Можно ли как-то иначе?

[Someone]

Sрy в сообщении #197544 писал(а):

Здесь я воспользовался формулой вычисления площади произвольного четырёхугольника по его сторонам.

Sрy в сообщении #197544 писал(а):

a = str1[0].to_f
b = str1[1].to_f
c = str1[2].to_f
d = str1[3].to_f


s = ( a + b + c + d ) / 2.0

ar = sqrt((s-a)*(s-b)*(s-c)*(s-d)) 

Это верно только для четырёхугольника, вписанного в окружность.

[Sрy]

Someone писал(а):

Это верно только для четырёхугольника, вписанного в окружность.

Да. Но на ruby задачу зачли, поэтому я и продолжал использовать эту формулу на Хашкеле.
А вот как снизить количество вычислений - не знаю...
Перерыл много источников, но как выразить площадь, используя меньшее количество умножений, не нашёл.

[Sрy]

Сдал сегодня эту задачку на С.
Изначально был wrong answer, но после исправления float на double стало всё нормально.
А на Хашкеле до сих пор не получилось. Причём, если в проге на Хашкеле сделать тип возвращаемой функции Float-ом, то TLE не будет, а будет также wrong answer.
То бишь нужно как-то ускорить операцию ввода, больше идей нет (всё-таки сдал на двух языках, поэтому вряд ли дело в оптимальности формулы).
Подскажите, пожалуйста, знатоки Хашкеля!

[mr.Aleph]

Sрy писал(а):

Подскажите, пожалуйста, знатоки Хашкеля!

Если у вас есть тестовые данные, то можно развлечься профилированием =)

На самом деле дело тут я думаю
0) Во многих промежуточных результатах (функция g в этом отношении ой как не оптимальна на мой взгляд, и видимо она не зафьюзилась).
1) в излишней ленивости - надо добавить strictness аннотации (специфическое расширение ghc)

Но это пальцевые рассуждения. Дайте тест, на котором профилировать =)