Треугольник Максима

Для поиска решения в процессе последовательного чтения данных следует сужать частотный отрезок поиска [min, max], который первоначально можно положить равным [30, 4000]. На каждом шаге мы имеем некоторую текущую частоту T, а также знаем ближе или дальше она по звучанию предыдущей ноты P. Анализируя это, мы можем уменьшить отрезок поиска, если средняя точка X находится между T и P, здесь X=(T+P)/2.

Рассмотрим всевозможные варианты, которые могут возникнуть при сравнении предыдущей и текущей частоты:

• P = T, результат сравнения любой (на самом деле, ни один из возможных не подходит) - в данном случае эта информация не уточняет частотный отрезок и не подразумевает каких-либо действий;
• P < T, результат closer - частота не меньше X и в случае, когда min < X нужно min присвоить X;
• P < T, результат further - частота не больше X и в случае, когда max > X нужно max присвоить X;
• P > T, результат closer - частота не больше X и в случае, когда max > X нужно max присвоить X;
• P > T, результат further - частота не меньше X и в случае, когда min < X нужно min присвоить X;

В результате обработки всех частот в качестве ответа следует вывести полученный отрезок [min, max]. Заметим, что в качестве переменных здесь следует использовать вещественные числа, поддерживающие точность до 10 знаков.

Алгоритмическая реализация вышеописанной идеи:

  min = 30; max = 4000
  read(P)
  for i = 1..n-1{
    read(T, s)
    X = (P + T) / 2
    if(s == ' closer'){
      if(T > P && min < X) min = X
      if(T < P) and (max > X) max = X
    }else{
      if(T < P) and (min < X) min = X
      if(T > P) and (max > X) max = X
    }
    P = T
  }
  write(min, ' ', max)

[Обсуждение] [Все попытки] [Задача]