e-olymp 1776. Рельсы

Ссылка на условие задачи: http://www.e-olymp.com/ru/problems/1776.

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

В городе PopPush находится известная железнодорожная станция. Страна, в котором находится город, невероятно холмистая. Станция была построена в прошлом веке. К сожалению, в то время средства для постройки были крайне ограничены, поэтому удалось построить только одну железнодорожную колею. Более того, выяснилось, что станция может быть только тупиковой (см. рисунок), и из-за отсутствия свободного места может иметь только одну колею.

Иллюстрация

Местная традиция гласит, что каждый поезд приходящий со стороны A продолжает свое движение в направлении B, при этом его вагоны перестанавливаются в некотором порядке. Предположим, что каждый поезд, приходящий из направления A, имеет n1000 вагонов, пронумерованных в возрастающем порядке 1, 2, …, n. Ответственный за реорганизацию вагонов должен знать, возможно ли перевезти их в направлении B в порядке a1, a2, …, an. Помогите ему написать программу, которая определит возможна ли такая перестановка вагонов. Вагоны можно отсоединять от поезда до того как они попадут на станцию и можно их отдельно передвигать пока все они не буду находиться в направлении B. На станции в любой момент времени может находиться любое количество вагонов. Но если вагон зашел на станцию, он уже не может вернуться на колею в направлении A, а также если он уже выехал в направлении B, то уже не может вернуться на станцию.

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

Состоит из нескольких тестов. Каждый тест кроме последнего описывает один поезд и возможно несколько требований для его реорганизации. Первая строка теста содержит целое число n. Каждая из следующих строк теста содержит перестановку 1, 2, …, n. Последняя строка блока содержит 0.
Последний тест состоит из единственной строки, содержащей 0.

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

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

Решение

Для решения данной задачи нам нужна переменная number, которая будет реализовывать нумерацию вагонов, иными словами, он будет считывать из потока ввода номер который нам нужно вывезти из тупика первым.
Пока введенное число не равняется нулю (что указывает на конец ввода) мы считываем количество вагонов в следующих поездах.
Мы сразу считываем последовательность поездов которую нужно получить в строку, если данная строка не является нулевой (обратное указывает на что количество поездов с таким количеством вагонов закончилась), то мы помещаем эту строку в строковой поток и считываем первый вагон что мы должны найти и вывезти из тупика.
Логично, что все вагоны отличные от данного помещаются в тупик (у нас это вектор, который используется как стек), если мы нашли вагон с нужным нам номером, то пока вагоны в тупике идут так как нам нужно (для того чтобы это определить, мы после каждого выведенного вагона считываем новый number), мы выводим их из тупика.
Если случается так, что мы поместили все вагоны в тупик, и при этом не нашли следующий number, то это означает, что следующий number был введен перед предшествующим ему вагоном, что и указывает на невозможность выполнения данной перестановки, по средством тупиковой станции.

Код программы: http://ideone.com/2p9seU.

А702а

Дана квадратная матрица порядка [latex]n[/latex].
Получить вектор [latex]Ab[/latex], где [latex]b[/latex]-вектор, элементы которого вычисляются по формуле: [latex]{b}_{i}={\frac{1}{{i}^{2}+2}}[/latex], где [latex]i=1,2,\dots,n[/latex].

2
1 2
3 4
0.666667 1.66667
Пройдено
2
5 6
7 8
2.66667 3.66667
Пройдено

При рассмотрении ряда квадратов чисел [latex](1, 4 , 9, \dots)[/latex], заметно, что числа следующей степени увеличиваются на четные числа, при этом модификатор предыдущего элемента на [latex]2[/latex] меньше чем следующего.
Все что нам остается сделать, это добавить генерацию вектора [latex]b[/latex], через модифицирующий элемент (преимущества которого состоят в частности, в том, что мы намного ускоряем вычисления квадратов, используя уже имеющиеся нас данные), в первый цикл (цикл ввода матрицы [latex]a[/latex]), а во втором цикле уже организовать вывод и вычисление собственно результирующего вектора.

Код программы: http://ideone.com/bl2iJE.

М4. НАМ

Написать исполнитель нормальных алгоритмов Маркова для заданного алфавита.

Ввод Вывод Комментарий
abbbcaa
aa->a
bb->b
cc->c
abca Пройдено
x
*x->xx*
*=>
->*
xx Пройдено
cbabca
ba->ab
cb->bc
ca->ac
aabbcc Пройдено

Прочитав строку и команды нам нужно разделить каждую команду на три элемента: ключ, значение, boolean-переменная (отвечает на вопрос: «Конечная ли команда?»). Последняя переменная нужна для того чтобы определить производится ли окончание операций после данной команды.
После этого я использовал небольшой аналог рекурсии. Дело в том, что я использовал бесконечный вызов функции до того момента, когда сама функция не передаст циклу команду остановиться.
В самой же функции идет поиск каждой команды в заданной строке, вначале по первому символу, а потом, если символ совпал, проверяется идентична ли найденная часть строки одной из наших команд.
Если никакая команда не нашла соответствие, функция возвращает 0 и программа выходит из цикла.
Если же совпадение было найдено, то мы заменяем найденный в строке ключ на соответствующее ему значение и возвращаем boolean-переменную (опять же соответствующую заданному ключу), таким образом если это конечная операция, то будет произведен выход из функции, иначе — будет произведен повторный вызов функции.
Так же следует учитывать и то что пустой ключ указывает на то что значение должно добавиться к началу строки, учтем это при написании кода.

Опробовать код можно здесь: http://ideone.com/QobpUI

A393a

Задача. Даны натуральное число [latex]n[/latex], целочисленная квадратная матрица порядка [latex]n[/latex]. Получить [latex]{b}_{1}[/latex],…,[latex]{b}_{n}[/latex], где [latex]{b}_{i}[/latex] — это наименьшее из значений, элементов находящихся в начале i-й строки матрицы до элемента, принадлежащего главной диагонали, включительно.

4
4 3 2 1
4 3 2 1
4 3 2 1
4 3 2 1
4 3 2 1
Пройдено
4
1 2 3 4
1 2 3 4
1 2 3 4
1 2 3 4
1 1 1 1
Пройдено

Считываем матрицу и проходим в цикле по каждой строке ведя поиск минимального элемента, но есть одно «Но», из-за которого эта задача по интереснее чем просто задача о простом нахождении минимума: и это тот факт что поиск ведется под главной диагональю матрицы.
У всех элементов находящихся под главной диагональю матрицы, включительно, индекс строк больше или равен индексу столбцов заданной матрицы. Учтем это при составлении программы.
На этом все интересное заканчивается осталось только написать код с учетом вышеперечисленных особенностей задачи.

Проверить можно здесь: http://ideone.com/6yjlQQ

Ю4.19

Задача. Многочлен [latex]{P}_{n}(x)[/latex] задан массивом своих коэффициентов [latex]A(n+1)[/latex]. Найти массив коэффициентов производной этого многочлена.

[latex]n[/latex] [latex]{a}_{2}[/latex] [latex]{a}_{1}[/latex] [latex]{a}_{0}[/latex] [latex]{b}_{2}[/latex] [latex]{b}_{1}[/latex] [latex]{b}_{0}[/latex]
2 0 0 0 0 0 0
2 17 2 3 34 2 0
2 0 -4 1 0 -4 0

Давайте вначале распишем сам многочлен [latex]{P}_{n}(x)[/latex]:
[latex]{P}_{n}(x)={a}_{n}{x}^{n} + {a}_{n-1}{x}^{n-1} + … + {a}_{0}{x}^{0}[/latex].

А его производная соответственно равна:
[latex]{P}_{n}^{(1)}(x)=n{a}_{n}{x}^{n-1} + (n-1){a}_{n-1}{x}^{n-2} + … + 0*{a}_{0}{x}^{-1}[/latex]

Давайте посмотрим как изменился массив [latex]A(n+1)[/latex]:

[latex]{P}_{n}(x)[/latex] [latex]{a}_{n}[/latex] [latex]{a}_{n-1}[/latex] [latex]{a}_{0}[/latex]
[latex]{P}_{n}^{(1)}(x)[/latex] [latex]n*{a}_{n}[/latex] [latex](n-1)*{a}_{n-1}[/latex] [latex]0*{a}_{0}[/latex]

Иными словами каждый элемент умножается на свой же номер в массиве, так что мы можем при считывании сразу же умножать полученные элементы на их номера. Осталось только написать программу.

Код программы: http://ideone.com/JHXOTa.

A119е

Задача. Вычислить бесконечную сумму с заданной точностью [latex]\varepsilon[/latex]([latex]\varepsilon[/latex]>0). Считать что требуемая точность достигнута, если несколько первых слагаемых и очередное слагаемое оказалось по модулю меньше, чем [latex]\varepsilon [/latex], это и все последующие слагаемые можно уже не учитывать.
Вычислить:
[latex]\sum _{ i=0 }^{ \infty }{ \frac { 1 }{ { 4 }^{ i }+{ 5 }^{ i+2 } } }[/latex]

[latex]\varepsilon[/latex] [latex]r[/latex]
0.09 0
0.02 0.0384615
0.000 7 0.0477735
0.000 056 0.0481501
0.000 000 4 0.0481658

Давайте сразу же упростим заданную сумму:
[latex]\sum _{ i=0 }^{ \infty }{ \frac { 1 }{ { 4 }^{ i }+{ 5 }^{ i+2 } } } = \sum _{ i=0 }^{ \infty }{ \frac { 1 }{ { 4 }^{ i }+{ 5 }^{ i }*25 } }[/latex]

Из выше описанного следует что если обозначить слагаемые в знаменателе как [latex]a[/latex] и [latex]b[/latex] соответственно, то изначально их нужно инициализировать как [latex]a=1[/latex], a [latex]b=25[/latex], то следует каждый раз умножать [latex]a[/latex] на четыре, а [latex]b[/latex] на пять, чтобы получить нужную нам последовательность. Осталось только сделать цикл который будет находить каждый элемент последовательности и прибавлять его к переменной [latex]r[/latex] в которой мы будем хранить результат, при этом цикл будет работать только пока текущий элемент последовательности больше заданного нам числа [latex]\varepsilon[/latex]. После нарушения условия цикла мы выводим полученную сумму последовательности которая хранится у нас в переменной [latex]r[/latex].

Код программы: http://ideone.com/9nYtod.