IPB
ЛогинПароль:

> Прочтите прежде чем задавать вопрос!

1. Заголовок темы должен быть информативным. В противном случае тема удаляется ...
2. Все тексты программ должны помещаться в теги [code=pas] ... [/code], либо быть опубликованы на нашем PasteBin в режиме вечного хранения.
3. Прежде чем задавать вопрос, см. "FAQ", если там не нашли ответа, воспользуйтесь ПОИСКОМ, возможно такую задачу уже решали!
4. Не предлагайте свои решения на других языках, кроме Паскаля (исключение - только с согласия модератора).
5. НЕ используйте форум для личного общения, все что не относится к обсуждению темы - на PM!
6. Одна тема - один вопрос (задача)
7. Проверяйте программы перед тем, как разместить их на форуме!!!
8. Спрашивайте и отвечайте четко и по существу!!!

 
 Ответить  Открыть новую тему 
> Помогите решить задачу - Треугольник Максима
сообщение
Сообщение #1


Новичок
*

Группа: Пользователи
Сообщений: 23
Пол: Мужской
Реальное имя: Влад

Репутация: -  0  +


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

Вот задача:

Треугольник Максима
Имя входного файла: 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
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #2


Злостный любитель
*****

Группа: Пользователи
Сообщений: 1 755
Пол: Мужской

Репутация: -  62  +


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


--------------------
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #3


Новичок
*

Группа: Пользователи
Сообщений: 23
Пол: Мужской
Реальное имя: Влад

Репутация: -  0  +


Цитата(TarasBer @ 24.10.2010 14:14) *

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

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

Сообщение отредактировано: ForesTop -
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #4


Злостный любитель
*****

Группа: Пользователи
Сообщений: 1 755
Пол: Мужской

Репутация: -  62  +


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


--------------------
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #5


Новичок
*

Группа: Пользователи
Сообщений: 23
Пол: Мужской
Реальное имя: Влад

Репутация: -  0  +


А как определить полуинтервал?
Я просто ещё школьник! И толком не знаю как это сделать!
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #6


Злостный любитель
*****

Группа: Пользователи
Сообщений: 1 755
Пол: Мужской

Репутация: -  62  +


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


--------------------
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #7


Новичок
*

Группа: Пользователи
Сообщений: 23
Пол: Мужской
Реальное имя: Влад

Репутация: -  0  +


0<x<1

Сообщение отредактировано: ForesTop -
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #8


Злостный любитель
*****

Группа: Пользователи
Сообщений: 1 755
Пол: Мужской

Репутация: -  62  +


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

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


--------------------
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #9


Новичок
*

Группа: Пользователи
Сообщений: 23
Пол: Мужской
Реальное имя: Влад

Репутация: -  0  +


(a>=x<b) and (a<=x<b)
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #10


Злостный любитель
*****

Группа: Пользователи
Сообщений: 1 755
Пол: Мужской

Репутация: -  62  +


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


--------------------
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #11


Новичок
*

Группа: Пользователи
Сообщений: 23
Пол: Мужской
Реальное имя: Влад

Репутация: -  0  +


Может быть:
c=b/2
x<=c
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #12


Злостный любитель
*****

Группа: Пользователи
Сообщений: 1 755
Пол: Мужской

Репутация: -  62  +


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


--------------------
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #13


Новичок
*

Группа: Пользователи
Сообщений: 23
Пол: Мужской
Реальное имя: Влад

Репутация: -  0  +


Может быть:
c=(a+b)/2
x<=c
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #14


Злостный любитель
*****

Группа: Пользователи
Сообщений: 1 755
Пол: Мужской

Репутация: -  62  +


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

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


--------------------
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #15


Новичок
*

Группа: Пользователи
Сообщений: 23
Пол: Мужской
Реальное имя: Влад

Репутация: -  0  +


Или:

if a<=b then
x<=(a+b)/2
else
x>=(a+b)/2;
blink.gif
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #16


Злостный любитель
*****

Группа: Пользователи
Сообщений: 1 755
Пол: Мужской

Репутация: -  62  +


Во, уже лучше.
Теперь надо учесть, что если вместо "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;



--------------------
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #17


Новичок
*

Группа: Пользователи
Сообщений: 23
Пол: Мужской
Реальное имя: Влад

Репутация: -  0  +


Спасибо Вам большое!
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #18


Бывалый
***

Группа: Пользователи
Сообщений: 195
Пол: Мужской
Реальное имя: Сергей

Репутация: -  2  +


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


--------------------
♣♣♣
"Себя великим не считай, гордясь величьем предков,
Величья не добудешь ты и золота ценою!
Хоть светит на небе луна, но отраженным светом -
Чужою славой не живи, не будь второй луною!!!"
♣♣♣
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #19


Гость






cialis urgente
 К началу страницы 
+ Ответить 

 Ответить  Открыть новую тему 
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 





- Текстовая версия 9.08.2022 5:55
500Gb HDD, 6Gb RAM, 2 Cores, 7 EUR в месяц — такие хостинги правда бывают
Связь с администрацией: bu_gen в домене octagram.name