Author Archives: Куленюк Денис Віталійович

e-olymp 1776. Рельсы

by

1

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

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

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

Иллюстрация

Местная традиция гласит, что каждый поезд приходящий со стороны A продолжает свое движение в направлении B, при этом его вагоны перестанавливаются в некотором порядке. Предположим, что каждый поезд, приходящий из направления A, имеет n ≤ 1000 вагонов, пронумерованных в возрастающем порядке 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.

Related Images:

А702а

by

0

Дана квадратная матрица порядка [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.

Related Images:

М4. НАМ

by

1

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

Ввод Вывод Комментарий
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

Related Images:

A393a

by

1

Задача. Даны натуральное число [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

Related Images:

Ю4.19

by

4

Задача. Многочлен [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.

Related Images:

A119е

by

3

Задача. Вычислить бесконечную сумму с заданной точностью [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.

Related Images:

A153

by

4

Даны натуральное число [latex]n[/latex], действительный числа [latex]x[/latex], [latex]a_{n}, a_{n-1}, \ldots, a_{0}[/latex]. Вычислить используя схему Горнера, значение [latex]a_{n}{x}^{n} + a_{n-1}{x}^{n-1} + \cdots + a_{0}.[/latex] [latex]a_{n}{x}^{n} + a_{n-1}{x}^{n-1} + \cdots + a_{0} = \left( \ldots \left(a_{n}{x} + a_{n-1}\right)x + \cdots + a_{1}\right)x + a_{0}.[/latex]

[latex]n[/latex] [latex]x[/latex] [latex]{a}_{n}[/latex] [latex]{a}_{n-1}[/latex] [latex]{a}_{n-2}[/latex] [latex]{a}_{n-3}[/latex] [latex]s[/latex]
3 2 5 4 3 2 64
2 1 3 4 7 _ 14
3 0 3 4 12 8 8
3 5 0 10 12 8 318
1 5 2 1 _ _ 11

Начинаем с коэффициента с рядом с [latex]X[/latex]-ом c максимальной степенью, у нас это элемент [latex]{a}_{n}[/latex], мы последовательно умножаем его (коэффициент) на [latex]X[/latex], а потом прибавляем следующий считанный коэффициент и сохраняем полученное значение в переменной.
Это был пример решения для [latex]n=2[/latex], если же [latex]n>2[/latex], то мы должны выполнить алгоритм для [latex]n=2[/latex], после чего [latex]n-2[/latex] раз умножать полученное в переменной значение на [latex]X[/latex] и прибавлять последующий элемент.

Осталось только написать программу: http://ideone.com/ScO3aw.

Related Images:

WoW 3. Идем к ним?

by

6

Задача:
https://cpp.mazurok.com/word-of-the-week/идём-к-ним/

Изначально я решил написать программу в которой будут соединенны два решения: для задачи в которой можно сесть не более половины зерен, а так же для той задаче в которой максимальное съеденное число зерен задавалось пользователем. Я реализовал это достаточно просто: если m равна нулю во-второй задаче, то задача просто не имеет решения(как и смысла вообщем-то), именно поэтому я решил использовать нулевое m как показатель того что заданы параметры или для первой задачи.

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

Число зерен Сколько нужно отнять зерен Комментарий Число зерен Сколько нужно отнять зерен Комментарий
1 0 П 9 2 В
2 1 В 10 3 В
3 0 П 11 4 В
4 1 В 12 5 В
5 2 В 13 6 В
6 3 В 14 7 В
7 0 П 15 0 П
8 1 В …

В — Выигрышный вариант существует
П — Нет выигрышного варианта

Исходя из выше описанной таблицы вполне ясно виден алгоритм, так как выигрышный вариант отсутствовал только в случаях, где число зерен соответсвовало данной формуле: [latex]{ 2 }^{ n }-1[/latex]. тогда все что от нас требуется это найти найти такое число по этой формуле при котором количество зерен будет равно или меньше данного числа.

Если изначальное число зерен будет меньше полученного числа, то выигрышный вариант существует и все что от нас требуется, так это найти предыдущее число ( иными словами нужно найти [latex]{ 2 }^{ n-1 }-1[/latex]) и узнать сколько же зерен нужно отнять чтобы сделать выигрышный ход:

Это все что касается первой задачи, но как оказалось вторая задача была совершенно аналогична:
Решение задачи я опять начал с расписывания нескольких вариантов, на этот раз если максимум съеденных зерен равен двум и соответственно трем:

2 3
Число зерен Сколько нужно отнять зерен Комментарий Число зерен Сколько нужно отнять зерен Комментарий
1 0 П 1 0 П
2 1 В 2 1 В
3 2 В 3 2 В
4 0 П 4 3 В
5 1 В 5 0 П
6 2 В 6 1 В
7 0 П 7 2 В
… …

Как вы могли уже заметить здесь тоже можно заметить очевидную тенденцию, в которой выигрышного варианта нет в тех случаях, когда число зерне соответствует этой формуле [latex]1+i(m+1)[/latex], а это значит что нам нужно всего лишь видоизменить алгоритм решения первой задачи просто подставив эту формулу вместо предыдущей.

Related Images:

Ю3.13

by

3

Задача. Проверить численно первый замечательный предел [latex]\lim _{ x\xrightarrow [ ]{ } 0 }{ \frac { \sin { x } }{ x } } =1[/latex], задавая [latex]x[/latex] значения [latex]1[/latex]; [latex]\frac {1} {2}[/latex]; [latex]\frac {1} {4}[/latex]; [latex]\frac {1} {8}[/latex];… до тех пор, пока левая часть равенства не будет отличаться от правой менее чем на заданную погрешность [latex]\varepsilon[/latex].

[latex]\varepsilon[/latex] Ответ
0.5 Проверка пройдена при x ==1
0.09 Проверка пройдена при x ==1/2
0.009 Проверка пройдена при x ==1/8
0.000 9 Проверка пройдена при x ==1/16
0.000 09 Проверка пройдена при x ==1/64
0.000 009 Проверка пройдена при x ==1/256
0.000 000 9 Проверка пройдена при x ==1/512
0.000 000 09 Проверка пройдена при x ==1/2048
0.000 000 009 Проверка пройдена при x ==1/8192
0.000 000 0009 Проверка пройдена при x ==1/16384

Из условия задачи можно сразу определить что здесь придется воспользоваться циклом который будет изменять [latex]x[/latex] и подставлять в функцию:
[latex]y=\frac { \sin { x } }{ x }[/latex]

Главная задача которая стоит перед программистом в таких случаях — это сохранение максимально возможной точности вычислений. Из условия видно что [latex]0<x<=1[/latex], при этом он будет постоянно делиться на двойку, так что если обозначить знаменатель [latex]x[/latex] как [latex]a[/latex] (числитель всегда будет единицей), то справедливо что:
[latex]y=\frac { \sin { x } }{ x }=\frac{ \sin{ \frac {1}{a} } }{\frac {1}{a}}=a*\sin{ \frac {1}{a} } [/latex]

где [latex]a={2}^{i}[/latex], [latex]i>=0[/latex] (то есть переменная [latex]i[/latex] пробегает все значения от нуля и до плюс бесконечности).
Иными словами переменная [latex]a[/latex] инициализируется единицей и с каждой итерацией умножается на двойку.
Нам осталось только сделать цикл который будет подставлять нужный [latex]x[/latex] в формулу пока модуль разности значения правой половины равенства и левой не будет меньше (либо равен) заданному [latex]\varepsilon[/latex]

Сам код программы: http://ideone.com/N9p5sQ.

Related Images:

А60в

by

6

4

рис.1

Задача. Даны действительные числа [latex]x[/latex] и [latex]y[/latex]. Найти [latex]u[/latex], если
4

где [latex]D[/latex] — заштрихованная область на (рис.1)

[latex]x[/latex] [latex]y[/latex] [latex]u[/latex] Комментарий
5 3 22 Точка не входит в D
0.5 0.5 0 Точка входит в D
0 0 0 Тoчка лежит на границе D

Посмотрев на условие задачи нетрудно заметить что сложность может возникнуть только в определении положения точки относительно заштрихованной области. Нам заданы уравнения окружности и параболы, причем заштрихованная область лежит между вершиной параболы и нижней половиной окружности.

Вот те самые вышеупомянутые уравнения:
1)[latex]y=1-{ x }^{ 2 }[/latex]
2)[latex]{ x }^{ 2 }+{ (y-1) }^{ 2 }=1[/latex]

Второе уравнение можно привести к виду:
[latex]y=1\pm\sqrt{1-{x}^{2}} [/latex] Заметим что указанная формула работает только при: [latex]{ x }\le 1[/latex](Важно не забыть упомянуть об этом в местах в участках кода которых мы будем её использовать).
Исходя из выше наведенного графика: нас интересует нижняя часть окружности, тогда на месте [latex]\pm[/latex] нужно поставить [latex]-[/latex]
Также график показывает нам что координата [latex]y[/latex] заданной нам точки должна быть:
[latex]1-\sqrt { 1-{ x }^{ 2 } }<y<1-{ x }^{ 2 }[/latex]

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

Сам код программы: http://ideone.com/SMyaWK

Related Images:

e-olymp 3. Спичечная модель

by

3

Спичечная модель

Спичечная модель с http://www.e-olimp.com.ua/problems/3


Условие задачи:
http://www.e-olimp.com.ua/problems/3
Прохождение тестов данной программой:
http://www.e-olimp.com.ua/
solutions/1591163

Я разделил задачу на три подэтапа: построение боковой, верхней и задней стен.

Ввод Вывод Комментарий Вердикт
0 0 Проверка на нуль: Пройдено
3 28 Тот же пример что и в условии к задаче: Сходится Проверка пройдена
9 62 1 этап Пройдено
13 83 2 этап Пройдено
19 112 3 этап Пройдено
2Е9 6.00953Е9 Проверка на переполнение максимальным возможным числом: Пройдено

Вначале увидев эту задачу я понял что самое главное в этой задаче это понять какую фигуру лучше строить и как строить. С фигурой все было очевидно: в данном случае самая экономичная фигура это куб, а это значит что нам нужно найти как лучше всего его строить, а если быть более точным как из кубов с величиной стены [latex]I[/latex] построить куб с величиной стены [latex]I+1[/latex]. Я решил что нужно последовательно наращивать стены: вначале боковую, потом верхнюю и напоследок заднюю. Здесь было замечено что количество кубов входящих в нашу фигуру можно найти просто возведя сторону в кубическую степень, с этого и пошли эти строчки:

Вот таким незамысловатым способом мы нашли величину стены у куба если он закончен. Что ж давайте теперь найдем в каком этапе находится строительство куба:

Первый этап(строительство боковой стены):

Второй этап(строительство верхней стены):

Или третий(строительство задней стены):

И мы сразу приступаем к делу: я вывел формулу зависимости количества спичек от фигуры, вот она:
[latex]3xyz+2xy+2xz+2yz+x+y+z[/latex] и из неё я уже вывел эти формулы:
1) Если все стороны равны: [latex]3n(n+1)^2[/latex];

2) Если две стороны равны, а третья на единицу больше: [latex]3n^3 + 9n^2 + 7n + 1[/latex];

3) Если две стороны равны, а третья на единицу меньше: [latex]3n^3 + 3n^2 -n-1[/latex].

Зачем? Первая формула пригодится нам для первого этапа, когда к уже готовому кубу добавляются еще кубы. Вторая: когда после первого этапа одна сторона стала больше чем остальные. И конечно же третья: которая соответственно строится когда две стороны больше третьей.
Теперь нам осталось только достроить недостающие кубы, для этого вначале нужно узнать сколько кубов нужно достроить:
1)Для первого этапа:

2)Для второго:

3)И конечно же для третьего:

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

Зачем нам это нужно? Просто, я заметил что достройка идет по такому принципу(начиная с левого нижнего угла):

3 3 3 5
3 3 5 3
3 5 3 3
8 5 5 5

и в таком порядке:

16 15 14 13
9 8 7 12
4 3 6 11
1 2 5 10

Как вы видите +8 мы видим только на первом кубе, а +5 на первом кубе треугольного и в середине треугольного . Осталось только описать это и мы получаем:

Related Images:

Ю1.19

by

3

Задача Ю1.19. Найти координаты вершины параболы [latex]y = a{ x }^{ 2 }+bx+c[/latex]

[latex]a[/latex] [latex]b[/latex] [latex]c[/latex] [latex]x[/latex] [latex]y[/latex] Комментарий
 1 -2  -3 1 -4 Пройден.
0 2 2 — — Не пройден
так график y(x)
не является параболой и программа оповещает об ошибке
1 0 4 0 4 Пройден.
2 1 3 -0.25 2.875 Пройден.

Мы знаем координаты вершины параболы вычисляются по формулам:
1)[latex]{ x }_{ 0 }=-\frac { b }{ 2a } [/latex]

2)[latex]{ y }_{ 0 }=a{ x }_{ 0 }^{ 2 }+b{ x }_{ 0 }+c[/latex]

(Для простоты в программе [latex]{ x }_{ 0 }[/latex] и [latex]{ y }_{ 0 }[/latex] заменены на [latex]{ x }[/latex] и [latex]{ y }[/latex] соответственно)

Теперь учтем ситуации в проработке которых могут возникнуть сложности:
Если [latex]{ a }=0[/latex], то график [latex]y(x)[/latex] не является параболой,
о чем на должен проинформировать компилятор.
Это все проблемы связанные с графиком.

Теперь проанализируем же может вызвать противоречия или ошибки,
для этого проанализируем элементы С++ которые могут вызвать ошибки или неточности:
Наиболее рационально использовать тип double, но у этого типа есть некоторая неточность, а именно (-0) — может быть принята за вполне нормальное число со знаком и компилятор безо всяких угрызений совести выведет «-0», а не 0 ( было бы логичнее ). Именно по этой причине мы вначале выполним [latex]{ x }_{ 0 }=\frac { b }{ 2a } [/latex], а потом уже, если [latex]{ x }[/latex] окажется не равным нулю, то мы умножим его на [latex]-1[/latex].
Это все сложности которые могут повстречаться на на пути реализации данной программы, так ничего не мешает нам написать данную программу.

Related Images: