e-Olymp 3604. Крейсерская скорость

Задача

Выдающийся ямайский спринтер Усейн Болд выиграл на Олимпиаде-2012 две золотые медали на дистанциях 100 и 200 метров.

Эти обе дистанции нам интересны тем, что могут при определённом научном подходе, предоставлять тренеру информацию в определении оптимального состава сборной команды страны для эстафеты 4×100 метров.

Так как обе дистанции очень коротки, то тактика бега здесь довольно проста: сначала спортсмен за какое-то стартовое время (время разгона) разгоняется до своей максимально возможной на данный момент скорости, а оставшуюся часть дистанции бежит с этой постоянной скоростью, которую назовём крейсерской скоростью. Естественно, что при формировании команды в эстафету нужно на старт ставить спортсмена, который на этой дистанции показывает наилучшее время, а на 3 оставшихся этапа отбирать из числа оставшихся спортсменов трёх с наилучшей крейсерской скоростью.

Тренер легкоатлетической сборной вашей страны поручил вам, как одному из лучших программистов, помочь ему с формированием состава сборной на эстафету. Для оказания оперативной помощи тренеру вам необходимо быстро решить следующую задачу: зная результаты спортсмена на дистанциях 100 и 200 метров, определить его крейсерскую скорость. Вам также известно, что крейсерская скорость и время разгона каждого из спортсменов на протяжении ваших исследований не изменялись.

Входные данные

В единственной строке задано 2 вещественных числа, разделённых единичным пробелом, соответственно результат спортсмена на дистанциях 100 и 200 метров.

Выходные данные

единственной строке выведите крейсерскую скорость спортсмена с точностью не менее 6-ти знаков после запятой.

Тесты

Входные данные Выходные данные
9.63  19.32 10.319917
12.49  21.30 11.350737
7.46  13.58 16.339869

Код программы:

Решение задачи

Для решения этой задачи мы воспользуемся формулами скорости. Нам было дано время прохождения двух дистанций в 100 метров и 200 метров. Так как спортсмен разгоняется на дистанции 100 метров, то оставшиеся 100 метров из 200 он бежит с постоянной скоростью. Чтобы узнать время за сколько он пробегает вторые 100 метров, мы отнимает из второго времени первое. Дальше мы пользуемся формулой нахождения скорости по расстоянию и времени [latex]\frac{s}{t}[/latex]. Полученая скорость и будет крейсерской скоростью.

Ссылки

 

  • Задача на сайте e-olymp
  • Код решения в Ideone

 

e-olymp 519. Сумма квадратов

Latest posts by Иван Василевский (see all)

Как лучше кодировать квадрат?

Как лучше кодировать квадрат?

Условие задачи
Найти сумму квадратов двух чисел.

Входные данные
Два целых числа [latex]a[/latex] и [latex]b[/latex]. Числа не превышают [latex]10^9[/latex] по абсолютной величине.

Выходные данные
Выведите одно целое число [latex]a^2 + b^2.[/latex] Continue reading

MS9. Шифрование символов

Задача
Зашифруйте текст из входного потока, заменяя каждый символ результатом сложения по модулю два его кода и кода предыдущего символа текста. Первый символ шифровать не нужно.

Входные данные
Последовательность символов.

Выходные данные
Зашифрованная последовательность символов, напечатанная через пробел.

Тесты

входные данные выходные данные
the five boxing wizards jump quickly.

t 292 306 165 236 312 341 320 165 228 320 351 330 325 316 167 270 329 349 316 325 314 330 179 244 340 335 333 176 258 347 327 303 313 323 350 213
pack my box with five dozen liquor jugs

p 274 295 313 171 250 351 185 228 320 351 184 270 329 337 324 168 236 312 341 320 165 232 322 355 324 321 174 248 318 331 347 339 339 178 244 340 323 333
.!+= ;::—_//»‘ @#%

. 112 119 165 125 150 175 174 148 135 235 189 141 115 112 103 96 160 134 109

Код программы

Решение задачи
Объявляем 2 символьные переменные. Считываем первый символ и выводим его. Остальные символы будут считываться в цикле, пока не произойдет переход на следующую строку.По мере ввода запоминаем старый символ во 2 переменной и выводим посредством простого уравнения [latex] \left |2\cdot a + b\right | [/latex].

Ссылки

A 325. Простые делители числа

Задача
Дано натуральное число [latex]n[/latex]. Получить все простые делители этого числа.

Входные данные
Натуральное число [latex]n[/latex]

Выходные данные
Все его простые делители напечатанные через пробел

Тесты

входные данные выходные данные
2 2
7 7
50 2 5 5
169 13 13
583 11 53
2368 2 2 2 2 2 2 37
73890 2 3 3 5 821
885066 2 3 7 13 1621
6943960340 2 2 5 97 1787 2003

Код программы

Решение задачи
Для решения задачи мы проверяем все числа от 2 до [latex]\sqrt{n}[/latex]. Если число является делителем [latex]n[/latex], то мы его выводим и делим [latex]n[/latex] на это число. Повторная проверка на простоту не требуется так как мы ведем поиск снизу, а значит число полученное после проверки уже не может делиться на составное. В конце, если остается простой делитель больше, то он выводиться так же.

Ссылки

e-olymp 1281. Простая задачка Шарика

Задача
Ещё задолго до того, как Шарик нашёл умную книжку, утерянную Печкиным, когда он только начинал свои эксперименты по распиливанию шахматных досок, когда ещё на шахматной доске белые поля были белыми, а чёрные – чёрными, он задал одну из своих первых задачек Матроскину.

«Сколько разных последовательностей длины [latex]n[/latex] можно составить из клеток распиленных шахматных досок, если ни в одной из последовательностей никакие три белых поля не должны идти подряд»?

Матроскин так и не решил ещё эту задачку, так что ваша задача помочь ему.

Входные данные
Длина последовательности [latex]n[/latex] ([latex]n ≤ 64[/latex]).

Выходные данные
Вывести количество указанных последовательностей.

Тесты

Входные данные Выходные данные
1 2
2 4
3 7

Код программы

Решение
Для решения задачи воспользуемся рекуррентным соотношением [latex]f \left( n \right) = f \left( n-1 \right)+f \left( n-2 \right)+f \left( n-3 \right)[/latex], где [latex]f[/latex] — функция, возвращающая ответ на поставленную задачу. Из условия следует, что для любой последовательности рассматривать следует только три варианта её последних элементов: …Ч, …ЧБ, …ЧББ (где Ч — чёрная клетка, Б — белая), так как в случае, если конец последовательности квадратов содержит только чёрный квадрат, чёрный и белый или чёрный и два белых, то нарушить последовательность могли только предшествующие этим окончаниям, которые имеют длины 1, 2, и 3 соответственно, последовательности. Именно это и влечёт справедливость указанного выше рекуррентного соотношения. Значения [latex]f \left( n \right)[/latex] при [latex]n \le 3[/latex] можно вычислить вручную и сохранить, а остальные вычислять в цикле с использованием предыдущих, вплоть до получения требуемого.

Ссылки
Код на ideone.com
Задача с сайта e-olymp.com.
Засчитанное решение.

e-olymp 5062. Максимальный подпалиндром

Задача

Из данной строки удалите наименьшее количество символов так, чтобы получился палиндром (строка, одинаково читающаяся как справа налево, так и слева направо).

Входные данные: 

Непустая строка длиной не более [latex]100[/latex] символов. Строка состоит только из заглавных латинских букв.

Выходные данные:

Вывести строку-палиндром максимальной длины, которую можно получить из исходной вычёркиванием нескольких букв. При наличии нескольких решений необходимо вывести одно (любое) из них.

Тесты

 №  Входные данные  Выходные данные
 1 QWEERTYY YY
 2  QWEERT EE
 3 BAOBAB BAOAB
 4  ABCDCBA  ABCDCBA

Код программы

Засчитанное решение на e-olymp.

Решение

Так как палиндром читается одинаково как справа налево, так и слева направо, то максимальным подпалиндромом будет наибольшая общая подстрока двух строк: исходной строки [latex]s_1[/latex] и этой же строки, но записанной в обратном порядке [latex]s_2[/latex] (как, если бы мы её читали справа налево). Для нахождения их наибольшей общей подстроки следует заполнить таблицу [latex]D[/latex] размером [latex] (n+1)\times(n+1) [/latex], где [latex]n[/latex]-длина строки. Заполнять таблицу будем методом аналогичным поиску длины наибольшей общей подстроки, но в каждой ячейке [latex]D_{i j}[/latex] таблицы будем хранить наибольшую подстроку строки, содержащей только первые [latex]i[/latex] символов [latex]s_1[/latex], и строки, содержащей только [latex]j[/latex] первых символов [latex]s_2[/latex]. В ячейках [latex]D_{0 j}[/latex] и [latex]D_{i 0}[/latex] будем хранить пустые строки. Если [latex]i[/latex]-й символ строки [latex]s_1[/latex] равен [latex]j[/latex]-ому символу строки [latex]s_2[/latex], то в ячейку [latex]D_{i j}[/latex] запишем конкатенацию строки из ячейки [latex]D_{i-1 j-1}[/latex] и данного символа. Иначе в ячейке [latex]D_{i j}[/latex] будем хранить наибольшую из строк [latex]D_{i-1 j}[/latex] и [latex]D_{i j-1}[/latex]. Таким образом в ячейке [latex]D_{n n}[/latex] будет хранится наибольший подпалиндром исходной строки.

Ссылки