Помогите пожалуйста решить задачу Треугольник Максима! Она осталась ещё с областной олимпиады того года, а так решить и не могу!
Вот задача:
Треугольник Максима Имя входного файла: 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
24.10.2010 17:14
Надеюсь, это со старого АЦМ, а не с проходящего прямо сейчас?
ForesTop
24.10.2010 17:16
Цитата(TarasBer @ 24.10.2010 14:14)
Надеюсь, это со старого АЦМ, а не с проходящего прямо сейчас?
Это задания с областной олимпиады 2009 года!
TarasBer
24.10.2010 17:29
Хорошо. Подсказка - последовательность данных можно разбить на треугольники ft[i-1], ft[i], b[i] - две последовательно идущие ноты и указание, к какой из них ближе звук треугольника. Из этой тройки чисел можно определить полуинтервал, в котором лежит звук треугольника. Теперь пересекаем все полуинтервалы для всех троек получаем ответ.
ForesTop
24.10.2010 17:38
А как определить полуинтервал? Я просто ещё школьник! И толком не знаю как это сделать!
TarasBer
24.10.2010 17:40
Вот смотри, например: есть число икс. Вы знаем про него только то, что оно ближе к 0, чем к 2. Это что означает?
ForesTop
24.10.2010 17:43
0<x<1
TarasBer
24.10.2010 17:49
Почти, но не совсем: Икс имеет право быть отрицательным. Если вместо 0 и 2 будут a и b, то какой ответ тогда?
ForesTop
24.10.2010 18:00
(a>=x<b) and (a<=x<b)
TarasBer
24.10.2010 18:09
(a>=x<b) and (a<=x<b) Подставляем вместо a и b числа 0 и 2, получаем, что икс от 0 до 2. А должно получиться, что икс он минус бесконечности до единицы. Переход от частного к общему не удался, думай ещё.
ForesTop
24.10.2010 18:20
Может быть: c=b/2 x<=c
TarasBer
24.10.2010 18:30
Уже ближе, но. Подставляем в качестве a и b числа 1 и 3. Получаем, что по твоей формуле икс должно быть <= 1.5. Хотя понятно, что на самом деле икс должно быть <= 2. Так что ещё думай.
ForesTop
24.10.2010 18:46
Может быть: c=(a+b)/2 x<=c
TarasBer
24.10.2010 18:56
Это если a <= b. А если a > b?
ForesTop
24.10.2010 20:12
Или:
if a<=b then x<=(a+b)/2 else x>=(a+b)/2;
TarasBer
24.10.2010 20:23
Во, уже лучше. Теперь надо учесть, что если вместо "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
24.10.2010 23:22
Спасибо Вам большое!
Cheburashka
24.10.2010 23:52
У нас была в прошлом году эта задача, тоже на региональной олимпиаде... Когда увидел решение, я удивился насколько она просто Сейчас попробую понять, как рассуждали Вы
gabapentin side effects in elder
8.12.2021 7:45
cialis urgente
Это текстовая версия — только основной контент. Для просмотра полной версии этой страницы, пожалуйста, нажмите сюда.