Помогите решить задачу - Треугольник Максима Опции

[ForesTop]

Помогите пожалуйста решить задачу Треугольник Максима!
Она осталась ещё с областной олимпиады того года, а так решить и не могу!

Вот задача:

Треугольник Максима
Имя входного файла: triangle.in
Имя выходного файла: triangle.out
Максимальное время работы на одном тесте: 2 секунды
Максимальный объем используемой памяти: 64 мегабайта
Максимальная оценка: 100 баллов
С детства Максим был неплохим музыкантом и мастером на все руки. Недавно он самостоятельно сделал несложный перкуссионный музыкальный инструмент - треугольник. Ему нужно узнать, какова частота звука, издаваемого его инструментом.
У Максима есть профессиональный музыкальный тюнер, с помощью которого можно проигрывать ноту с заданной частотой. Максим действует следующим образом: он включает на тюнере ноты с разными частотами и для каждой ноты на слух определяет, ближе или дальше она к издаваемому треугольником звуку, чем предыдущая нота. Поскольку слух у Максима абсолютный, он определяет это всегда абсолютно верно.
Вам Максим показал запись, в которой приведена последовательность частот, выставляемых им на тюнере, и про каждую ноту, начиная со второй, записано - ближе или дальше она к звуку треугольника, чем предыдущая нота. Заранее известно, что частота звучания треугольника Максима составляет не менее 30 герц и не более 4000 герц.
Требуется написать программу, которая определяет, в каком интервале может находиться частота звучания треугольника.
Формат входных данных
Первая строка входного файла содержит целое число п - количество нот, которые воспроизводил Максим с помощью тюнера (2 < п < 1000). Последующие п строк содержат записи Максима, причем каждая строка содержит две компоненты: вещественное число ft - частоту, выставленную на тюнере, в герцах (30 <ft < 4000), и слово «closer» или слово «further» для каждой частоты, кроме первой.
Слово «closer» означает, что частота данной ноты ближе к частоте звучания треугольника, чем частота предыдущей ноты, что формально описывается соотношением: J/J -Лреуг.| < 1/J-i -frpeyr.l
Слово «further» означает, что частота данной ноты дальше, чем предыдущая.
Если оказалось, что очередная нота так же близка к звуку треугольника, как и предыдущая нота, то Максим мог записать любое из двух указанных выше слов.
Гарантируется, что результаты, полученные Максимом, непротиворечивы.
Формат выходных данных
В выходной файл необходимо вывести через пробел два вещественных числа - наименьшее и наибольшее возможное значение частоты звучания треугольника, изготовленного Максимом.
Примеры входных и выходных данных

triangle.in

3
440.0
220.0 closer
300.0 further

triangle.out

30.0 260.0

--------------------------

triangle.in

4
554.0
880.0 further
440.0 closer
622.0 closer

triangle.out

531.0 660.0

[TarasBer]

Надеюсь, это со старого АЦМ, а не с проходящего прямо сейчас?

[ForesTop]

Надеюсь, это со старого АЦМ, а не с проходящего прямо сейчас?

Это задания с областной олимпиады 2009 года!

Сообщение отредактировано: ForesTop - 24.10.2010 13:17

[TarasBer]

Хорошо.
Подсказка - последовательность данных можно разбить на треугольники
ft[i-1], ft[i], b[i]
- две последовательно идущие ноты и указание, к какой из них ближе звук треугольника.
Из этой тройки чисел можно определить полуинтервал, в котором лежит звук треугольника.
Теперь пересекаем все полуинтервалы для всех троек получаем ответ.

[ForesTop]

А как определить полуинтервал?
Я просто ещё школьник! И толком не знаю как это сделать!

[TarasBer]

Вот смотри, например: есть число икс.
Вы знаем про него только то, что оно ближе к 0, чем к 2.
Это что означает?

[ForesTop]

0<x<1

Сообщение отредактировано: ForesTop - 24.10.2010 13:45

[TarasBer]

Почти, но не совсем:
Икс имеет право быть отрицательным.
Если вместо 0 и 2 будут a и b, то какой ответ тогда?

Сообщение отредактировано: TarasBer - 24.10.2010 13:49

[ForesTop]

(a>=x<b) and (a<=x<b)

[TarasBer]

(a>=x<b) and (a<=x<b)
Подставляем вместо a и b числа 0 и 2, получаем, что икс от 0 до 2. А должно получиться, что икс он минус бесконечности до единицы.
Переход от частного к общему не удался, думай ещё.

[ForesTop]

Может быть:
c=b/2
x<=c

[TarasBer]

Уже ближе, но.
Подставляем в качестве a и b числа 1 и 3.
Получаем, что по твоей формуле икс должно быть <= 1.5.
Хотя понятно, что на самом деле икс должно быть <= 2.
Так что ещё думай.

[ForesTop]

Может быть:
c=(a+b)/2
x<=c

[TarasBer]

Это если a <= b.
А если a > b?

Сообщение отредактировано: TarasBer - 24.10.2010 14:57

[ForesTop]

Или:

if a<=b then
x<=(a+b)/2
else
x>=(a+b)/2;

[TarasBer]

Во, уже лучше.
Теперь надо учесть, что если вместо "further" встретилось "closer", то всё наоборот.
То есть псевдокод получается такой:

Код

if (ft[i-1] <= ft[i]) xor closer[i] then // xor - взаимоисключающее или
  x <= (ft[i-1] + ft[i])/2
else
  x >= (ft[i-1] + ft[i])/2;

Такой код пока не может скомпилироваться, это вообще больше похоже на функциональный язык.
Поэтому надо завести переменные max и min, которые выводим в ответ и сделать так:

max := 4000; // числа из условия
min := 30;
for i := 0 to count - 2 do begin // перебираем все пары соседних нот

  if (ft[i-1] <= ft[i]) xor closer[i] then begin
    if max > (ft[i-1] + ft[i])/2 then 
      max := (ft[i-1] + ft[i])/2; //   x <= (a+b)/2 
  end else begin 
    if min < (ft[i-1] + ft[i])/2 then
      min := (ft[i-1] + ft[i])/2; //   x >= (a+b)/2 
  end;
  
end;

[ForesTop]

Спасибо Вам большое!

[Cheburashka]

У нас была в прошлом году эта задача, тоже на региональной олимпиаде... Когда увидел решение, я удивился насколько она просто
Сейчас попробую понять, как рассуждали Вы