e-olymp 1266. CD

Вам предстоит длительное путешествие на автомобиле. К сожалению, у Вас в машине есть только магнитофон, а лучшая музыка записана на компакт дисках. У Вас есть чистая магнитофонная лента с длительностью звучания [latex]N[/latex] минут. Вам нужно выбрать песни для записи на магнитофонную ленту таким образом, чтобы не используемое на ней место было минимально.

Предположения:

  • количество треков на CD не превышает [latex]100[/latex]
  • ни один трек не длится более [latex]N[/latex] минут
  • длина каждого трека выражена целым числом
  • [latex]N[/latex] также целое [latex](0\leq[/latex][latex]N\leq[/latex][latex]200)[/latex]

Программа должна найти максимально возможную длину записи треков на ленту с соблюдением того же порядка треков, что и на CD.

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

Входные данные содержат несколько строк. В каждой строке сначала задано число [latex]N[/latex], далее количество треков и длительность звучания каждого трека. Все числа разделены пробелами. Например, в первой строке входных данных первым задано [latex]N=5[/latex], далее количество треков [latex]s=3[/latex], первый трек имеет длительность [latex]1[/latex] минуту, второй — [latex]3[/latex] минуты, и последний — [latex]4[/latex] минуты.

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

Выведите строку «sum:» и далее продолжительность записи.

Входные данные Выходные данные
5 3 1 3 4
10 4 9 8 4 2
20 4 10 5 7 4
90 8 10 23 1 2 3 4 5 7
45 8 4 10 44 43 12 9 8 2
sum:5
sum:10
sum:19
sum:55
sum:45

Код:

Ссылка на засчитанное решение

Ссылка на ideone

Ссылка на ideone

Алгоритм решения построен на методе динамического программирования.

Возможны два варианта:

  1. Либо трек не попал на диск, следовательно длинна уже записанных треков на диск [latex](d[j][i])[/latex] равна предыдущему числу ранее записанных треков [latex](d[j][i-1])[/latex].
  2. Либо трек попал на диск, а значит [latex]d[j][i][/latex] равно максимуму из суммы ранее записанных треков [latex](d[j][i-1])[/latex] и суммы заданной длинны [latex]arr[i][/latex] c [latex]d[j-arr[i]][i-1]][/latex], где [latex]d[j-arr[i]][i-1]][/latex] равен сумме уже записанных треков при предыдущем элементе массива [latex]arr[i-1][/latex]

А712

Задача

Дана квадратная матрица [latex]A[/latex] порядка [latex]n[/latex]. Получить матрицы [latex]\frac{1}{2}(A+A^{*}) (1)[/latex] и [latex]\frac{1}{2}(A-A^{*}) (2)[/latex].

Тесты:

Ввод Вывод (1) Вывод (2)
3
1 2 3
2 4 6
1 4 8
1 2 2
2 4 5
2 5 8
0 0 1
0 0 1
-1 -1 0

Код:

Ссылка на ideone.

Сначала, вводим размер матрицы и саму матрицу, сразу же транспонируем ее. Теперь каждый элемент обычной матрицы прибавляем к транспонированному и отнимаем от транспонированного в последствии умножая на [latex]\frac{1}{2}[/latex]. Записываем это в две различные матрицы с результатом и выводим их на экран.

Код на Java

 

e-olymp 5073. Проверка на наличие параллельных ребер (ОГ)

Ориентированный граф задан списком ребер.

Проверьте, содержит ли он параллельные ребра.

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

Входной файл содержит числа [latex]n(1\leq n\leq 100)[/latex] — число вершин в графе и [latex]m(1\leq m\leq 10000)[/latex]  — число ребер. Затем следует [latex]m[/latex] пар чисел — ребра графа.

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

Выведите в выходной файл YES если граф содержит параллельные ребра и NO в противном случае.

Задача на e-olimp. Ссылка на засчитанное решение.

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

Код задачи:

Ссылка на ideone.

Алгоритм решения:

Сначала, добавим пару вершин в разные массивы так, чтоб нулевой элемент массива [latex]v[i][/latex] был началом ребра, а нулевой элемент массива [latex]g[i][/latex] — концом ребра и т.д. После этого в цикле будем сравнивать поочередно пары вершин до тех пор, пока не узнаем, что такая пара вершин уже встречалась, в таком случае выводим YES и завершаем цикл. В противном случае, если наше условие не выполнилось ни разу (т.е. переменная [latex]k[/latex] как была нулем в начале программы, так и осталась) выводим NO.

Код на Java

 

AA6

Задача

В заданной строке  дописать после каждого символа «!» символ «?».

Решение. 

Проверяем каждый символ строки до тех пор пока не встретится «!», после чего добавляем после него «?».

 

Input Output
Hello, world! Hello, world!?
 Why are we here?? Why are we here??
 !!!It’s ! a ! problem ! ! !?!?!?It’s !? a !? problem !? !?

Код на Java

 

Ю 4.37

Задача

Автостоп-2. Из пункта А в пункт В, между которыми [latex]s[/latex] км, выехал велосипедист с постоянной скоростью [latex]v_{0}[/latex] км/ч. Навстречу ему — из пункта В — другой путешественник решил добраться «автостопом» — на разных видах попутного транспорта. Перед каждым участком он [latex]\tau _{i}[/latex] минут «голосует», ожидая попутного транспорта, затем движется [latex]t _{i}[/latex]  часов со скоростью [latex]v _{i}[/latex] км/час ( величины [latex]\tau _{i}, t _{i}, v _{i}, i=1,2,\ldots,n[/latex]  заданы в соответствующих массивах). Через какое время после старта и на каком расстоянии от пункта А путники встретятся?

Тесты

s [latex]v_{0}[/latex] n [latex]\tau _{i}[/latex] [latex]t _{i}[/latex] [latex]v _{i}[/latex] place, км  time, ч Комментарий
100.0 30.0  1 60.0 1.0 40.0 60.0 2.0 Пройден
100.0 10.0 1 0.0 1.0 40.0 Путники не доехали до места встречи Не пройден
130.0 15.0 2 0.0 3.0 1.0 2.6 40.0 33.3 2.587267 38.809006 Пройден

 

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

Вначале программы вводим во входной поток и считываем данные. Далее, в цикле, проверяем несколько условий, таких как:

  1. Пока второй ждал — первый уже проехал весь путь.
  2. Если после i-ого этапа (т.е. после ожидания транспортного средства, поездки на нем) сумма пройденного пути второго и первого путника больше, чем весь путь.

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

Код на Java

 

Ю11.13

Задача

Метод Рунге-Кутта. Найти приближенное решение обыкновенного дифференциального уравнения  [latex]y^\prime=f(x,y), y(a)=y_{0}[/latex] методом Рунге-Кутта пятого порядка на отрезке [latex][a,b][/latex] с заданным шагом [latex]h[/latex]. Значения функции [latex]y(x)[/latex] в узловых точках вычисляется по формуле: [latex]y_{i+1}=y_{i}+\frac{h}{6}(k_{1}+2k_{2}+2k_{3}+k_{4}), i=0,1,2,\cdots[/latex], где [latex]k_{1}=f(x_{i},y_{i}); k_{2}=f(x_{i}+\frac{h}{2},y_{i}+\frac{h}{2}k_{1});[/latex][latex]k_{3}=f(x_{i}+\frac{h}{2},y_{i}+\frac{h}{2}k_{2}); k_{4}=f(x_{i}+h,y_{i}+hk_{3})[/latex].

Решим дифференциальное уравнение такого вида: [latex]y^\prime=x+y[/latex] при начальном условии [latex]y(0)=1[/latex] на отрезке [latex][0, 0.5][/latex] с шагом интегрирования [latex]h=0.1[/latex]

Screenshot_1

Screenshot_2

 

Screenshot_3

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

Для решения примера введем данные во входной поток в таком порядке: [latex]0.0[/latex], [latex]0.5[/latex], [latex]0.1[/latex], [latex]1.0[/latex], где первое и второе число — начало и конец отрезка интегрирования соответственно, третье — шаг интегрирования и четвертое — значение [latex]y[/latex] в точке [latex]a[/latex] (в начале отрезка), т.е. [latex]y(a)=y(0)[/latex].

В программе присутствует функция, которой мы передаем параметры [latex]x, y[/latex] и которая возвращает само дифференциальное уравнение. Далее, в цикле высчитываем значения [latex]k_{1},k_{2},k_{3},k_{4}[/latex], передавая каждый раз параметры в функцию с шагом [latex]h[/latex] до тех пор пока не дойдем до конца промежутка. После завершения цикла выводим значение [latex]y_{0}[/latex].