|
Олимпиада по информатике
|
|
|
gifer | Дата: Понедельник, 19.10.2009, 21:04 | Сообщение # 31 |
gifer
Ранг: Первоклашка (?)
Группа: Пользователи
|
| Сообщений: |
29 |
| Награды: |
0 |
| Статус: |
Offline |
|
Как бы вы решили такую задачу:
Два города соединены прямой дорогой длиной ровно l метров. В начальный момент времени велосипедист начинает движение из города в A в город B со скоростью v1 метров/секунду, а пешеход начинает движение из города B в город A со скоростью V2 м/с. Когда один из них достигает города, дорога кончается, таким образом, велосипедист или пешеход должен развернуться и продолжить движение в противоположном направлении по этой же дороге, сохраняя изначальную скорость. В результате, велосипедист и пешеход путешествуют между городами A и B до бесконечности.
Ваша задача заключается в том, чтобы вычислить число раз, когда они встретятся в течении первых t секунд. Если они встречаются ровно через t секунд после начала движения, эта встреча также должна засчитываться.
Входные данные
Единственная строка содержит четыре целочисленных числа: l, v1, v2 и t. Все числа лежат в пределах 1...10^9.
Выходные данные
Выведите единственное число - количество встреч велосипедиста и пешехода в течении первых t секунд.
Пример входных данных #1
1000 10 1 200
Пример выходных данных #1
2
Пример входных данных #2
4 4 3 4
Пример выходных данных #2
4
19.10.2009
Сообщение отредактировал gifer - Понедельник, 19.10.2009, 23:55
|
|
|
|
| |
|
|
SergeySml | Дата: Понедельник, 19.10.2009, 23:04 | Сообщение # 32 |
| Сообщений: |
161 |
| Награды: |
1 |
| Статус: |
Offline |
|
Не проверял, писал в блокноте, но должно работать. Типичная задача на отскок шарика от стенки к стенке...
Program zadacha;
var
v1,v2,L,t,n,i,x1,x2:integer;
f1,f2: boolean;
begin
write('vq,v2,L,t = ');
read(vq,v2,L,t);
n:=0;
x1:=0;
x2:=0;
f1:=true;
f2:=false;
For i:=1 to t do
begin
if f1 then inc(x1,v1) else dec(x1,v1);
if f2 then inc(x2,v2) else dec(x2,v2);
if (x1=0) or (x1=L) then f1:=not f1;
if (x2=0) or (x2=L) then f2:=not f2;
if x1=x2 then inc(n);
end;
Writeln('n=',n);
end.
19.10.2009
|
|
|
|
| |
|
|
gifer | Дата: Понедельник, 19.10.2009, 23:50 | Сообщение # 33 |
gifer
Ранг: Первоклашка (?)
Группа: Пользователи
|
| Сообщений: |
29 |
| Награды: |
0 |
| Статус: |
Offline |
|
Это решение неверно... Как я понял у вас учитываются только время встреч в целое число секунд. Однако это не так. Исследуя второй пример, я пришел к выводу, что встречи бывают примерно в 0,57 с, 1,75 с, 2,95 с, и 4 с. Т. е. моменты встреч находятся в непрерывном отрезке [0;t]. Таким образом, цикл здесь не поможет. Ваша программа на втором тесте дает ответ 0.
19.10.2009
|
|
|
|
| |
|
|
SergeySml | Дата: Вторник, 20.10.2009, 07:44 | Сообщение # 34 |
| Сообщений: |
161 |
| Награды: |
1 |
| Статус: |
Offline |
|
gifer, Как я понял, из условия задачи, речь идет о дискретных величинах. Причем уровень дискретности задан типом - целые. Мы имеем МОДЕЛЬ, а не реальное явление. С этой точки зрения задача решена верно.
Если рассматривать Вашу точку зрения, то следует задавать скорости вещественными числами, для координат х1, х2, счетчика времени i выбрать вещественный тип. Задавать величины скоростей с определенной степенью точности (хотя это и не обязательно). И, наконец, применить цикл While или Repeat, где изменение времени будет происходить через выбранный промежуток (степень точности!), а моменты встреч фиксироваться по условию: abs(abs(x1)-abs(x2))<=0.001(выбранная степень точности). Ну и конечно приращение координат на ДОЛЮ от введенного значения скорости.
В Basic можно и циклом For. Но, вероятно, и приводимое мной решение можно улучшить: if abs(abs(x1)-abs(x2))<=1 then inc(n);
20.10.2009
Сообщение отредактировал SergeySml - Вторник, 20.10.2009, 08:03
|
|
|
|
| |
|
|
gifer | Дата: Вторник, 20.10.2009, 10:05 | Сообщение # 35 |
gifer
Ранг: Первоклашка (?)
Группа: Пользователи
|
| Сообщений: |
29 |
| Награды: |
0 |
| Статус: |
Offline |
|
Типичная ошибка... Нигде в условие не написано, что учитываются встречи только в целое количество времени. Целыми являются только и лишь ТОЛЬКО l, v1, v2 и t (именное это вытекает из условия но ничего больше). Многие школьники на начальном этапе видят в условиях больше чем есть на самом деле.
В последнем Вашем решении Вы предлагаете опять расматривать дискретные промежутки времени, а как это видать из условия, это не есть верно... Кроме того, мне просто интересно, сколько ваше решение будет работать при экстремальных данных (например, 1000 1 1000000 1000000000). В олимпиадных задачах обычно есть ограничение времени работы программы. В данном случае 2 секунды.
Кстати, эта задача предлагалась школьникам на региональных соревнованях.
20.10.2009
Сообщение отредактировал gifer - Вторник, 20.10.2009, 10:07
|
|
|
|
| |
|
|
SergeySml | Дата: Вторник, 20.10.2009, 13:13 | Сообщение # 36 |
| Сообщений: |
161 |
| Награды: |
1 |
| Статус: |
Offline |
|
В таком случае:
Нужно искать число "преломлений" относительного движения объектов...
Я знаю как решается задача!
20.10.2009
|
|
|
|
| |
|
|
Adit | Дата: Понедельник, 09.11.2009, 01:55 | Сообщение # 37 |
Adit
Ранг: Дошколенок (?)
Группа: Я - учитель
|
| Сообщений: |
12 |
| Награды: |
0 |
| Статус: |
Offline |
|
Вообще решение любой задачи начинается с листа бумаги. Я вот на задачу посмотрел, и вот что получилось, в координатах x(t) движение объектов ломанная линия, т.е. задача сводится нахождению точек пересечений ломанных, уравнения на отдельном отрезке получить не проблема, пересечение линий найти тоже.
09.11.2009
|
|
|
|
| |
|
|
gifer | Дата: Вторник, 10.11.2009, 18:29 | Сообщение # 38 |
gifer
Ранг: Первоклашка (?)
Группа: Пользователи
|
| Сообщений: |
29 |
| Награды: |
0 |
| Статус: |
Offline |
|
Adit, Ваш подход как раз совпадает с моим. Только я сами уравнения прямых не нахожу, я сразу составляю диофантово уравнение и нахожу количество его решений.
10.11.2009
|
|
|
|
| |
|
|
мыха | Дата: Четверг, 12.11.2009, 13:34 | Сообщение # 39 |
мыха
Ранг: Школьник (?)
Группа: Я - учитель
|
| Сообщений: |
97 |
| Награды: |
0 |
| Статус: |
Offline |
|
В этом году проводятся олимпиады по информатике для 7-8 классов.. Кто - нибудь принимал участие в подобных? Может знаете что там примерно? Уж, надеюсь, в 7 классе не будет программирование
12.11.2009
|
|
|
|
| |
|
|
K@tti | Дата: Четверг, 12.11.2009, 15:29 | Сообщение # 40 |
K@tti
Ранг: Академик (?)
Admin
Группа: Администраторы
Должность: информатика
|
| Сообщений: |
6010 |
| Награды: |
78 |
| Статус: |
Offline |
|
Quote (мыха) В этом году проводятся олимпиады по информатике для 7-8 классов.. Кто - нибудь принимал участие в подобных? Может знаете что там примерно? Уж, надеюсь, в 7 классе не будет программирование У нас олимпиады только в 9-11 кл.
12.11.2009
|
|
|
|
| |
|
|
chernysh8 | Дата: Четверг, 12.11.2009, 16:34 | Сообщение # 41 |
| Сообщений: |
1503 |
| Награды: |
21 |
| Статус: |
Offline |
|
"Блажен, кто верует"
Решение задач составлением программы.
"По номеру квартиры определить подъезд и этаж. Задаётся количество этажей, подъездов, квартир." Примерно такая первая задача. Остальные в том же духе. Четвёртый год наша школа в олимпиадах по такой информатике не участвует.
Первую задачу я решил, потому и запомнил текст. В остальных до меня не дошло условие. Больно не пинайте, я самоучка, решение задач "изучал" часа два на Бейсике 10 лет тому назад.
12.11.2009
|
|
|
|
| |
|
|
gifer | Дата: Четверг, 12.11.2009, 19:22 | Сообщение # 42 |
gifer
Ранг: Первоклашка (?)
Группа: Пользователи
|
| Сообщений: |
29 |
| Награды: |
0 |
| Статус: |
Offline |
|
Насколько я знаю, у нас задачи на программирование начинаются только с олимпиад 9 класса. В восьмом классе предлагают просто составить словесный алгоритм решения задачи, на худший случай дадут несколько логических задачек. Насчет 7 класса - в первый раз слышу. У нас все с 8 ездят.
12.11.2009
|
|
|
|
| |
|
|
мыха | Дата: Воскресенье, 15.11.2009, 15:46 | Сообщение # 43 |
мыха
Ранг: Школьник (?)
Группа: Я - учитель
|
| Сообщений: |
97 |
| Награды: |
0 |
| Статус: |
Offline |
|
gifer, а есть у вас примеры таких задач для 8 класса?
вообще не могу ничего найти кроме программирования в олимпиадах
15.11.2009
|
|
|
|
| |
|
|
K@tti | Дата: Воскресенье, 15.11.2009, 16:02 | Сообщение # 44 |
K@tti
Ранг: Академик (?)
Admin
Группа: Администраторы
Должность: информатика
|
| Сообщений: |
6010 |
| Награды: |
78 |
| Статус: |
Offline |
|
Quote (мыха) вообще не могу ничего найти кроме программирования в олимпиадах На РМО у нас задали такой вопрос. Ответ был таков: не ждите в олимпиадах ничего, кроме программирования. Все остальные темы у нас идут на конкурсах.
15.11.2009
|
|
|
|
| |
|
|
мыха | Дата: Воскресенье, 15.11.2009, 16:15 | Сообщение # 45 |
мыха
Ранг: Школьник (?)
Группа: Я - учитель
|
| Сообщений: |
97 |
| Награды: |
0 |
| Статус: |
Offline |
|
у нас для 7-8 классов сказали будут основы только... многие только начинают изучать ее в 8 классе. я задачки хочу найти для тренировки учащимся на алгоритмику, логику, кодирование но уровень семи-висьмикласников
15.11.2009
|
|
|
|
| |
|
