e-olymp 6128. Простой дек

Задача. Простой дек

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

push_front

Добавить (положить) в начало дека новый элемент. Программа должна вывести ok.

push_back

Добавить (положить) в конец дека новый элемент. Программа должна вывести ok.

pop_front
Извлечь из дека первый элемент. Программа должна вывести его значение.

pop_back

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

front

Узнать значение первого элемента (не удаляя его). Программа должна вывести его значение.

back 

Узнать значение последнего элемента (не удаляя его). Программа должна вывести его значение.

size

Вывести количество элементов в деке.

clear

Очистить дек (удалить из него все элементы) и вывести ok.

exit

Программа должна вывести bye и завершить работу.

Гарантируется, что количество элементов в деке в любой момент не превосходит 100. Все операции:

  • pop_front
  • pop_back
  • front
  • back

всегда корректны.

Объяснение: Количество элементов во всех структурах данных не превышает 10000, если это не указано особо.

Тесты

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

 push_back 3

push_back 14

size

clear

push_front 1

back

push_back 2

front

pop_back

size

pop_front

size

exit

 ok

ok

2

ok

ok

1

ok

1

2

1

1

0

bye

 2  size

push_back 8

push_front 4

size

front

back

push_back 3

pop_front

front

pop_back

back

exit

0

ok

ok

2

4

8

ok

4

8

3

8

bye

Решение

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

Реализация двусторонней очереди идет посредством векторов [latex]box1[/latex] и [latex]box2[/latex], поэтому нет необходимости делать проверку на переполнение. Команды [latex]push_front[/latex] и [latex]push_back[/latex] соответственно добавляют в концы векторов [latex]box1[/latex] и [latex]box2[/latex] элементы и увеличивают размер дека box_size (на единицу за каждый добавленный элемент). Рассмотрим команду [latex]front[/latex]. Проверяя присутствие элементов в [latex]box1[/latex] мы выводим последний элемент вектора, так как добавляли элемент с помощью [latex]push_front[/latex] в конец вектора [latex]box1[/latex]. Если же вектор [latex]box1[/latex] пуст, то выводим первый элемент вектора [latex]box2[/latex], который в случае пустого вектора [latex]box1[/latex] является первым элементом дека. Команда [latex]back[/latex] относительно [latex]front[/latex] с векторами работает инверсивно. Т.е. Проверяя присутствие элементов в [latex]box2[/latex] выводим последний элемент данного вектора. Если же вектор [latex]box2[/latex] пуст, то выводим первый элемент вектора [latex]box1[/latex] , который в случае пустого вектора [latex]box2[/latex] является последним элементом дека. С командами [latex]pop_front[/latex] и [latex]pop_back[/latex] работают идентично [latex]front[/latex] и [latex]back[/latex]. Отличие лишь в том, что команды [latex]pop[/latex] в дополнении к выводу элемента удаляют его, уменьшая размер дека [latex]box_size[/latex] (на единицу за каждый удаленный элемент). Команда [latex]size[/latex] выводит размер дека [latex]box_size[/latex]. Команда clear удаляет все элементы векторов [latex]box1[/latex], [latex]box2[/latex] и обнуляет размер дека. Команда [latex]exit[/latex] выводит «bye» и завершает работу программы. Команды принимаются из потока ввода посредством строки s.

Ссылка на код.

e-olymp.

 

А290

Задача. Даны действительные числа [latex]x_{1},\ldots,x_{n}[/latex], [latex]y_{1},\ldots,y_{n}[/latex]. Получить [latex]x’_{1},\ldots,x’_{n}[/latex],[latex]y’_{1},\ldots,y’_{n}[/latex], преобразовав для получения [latex]x’_{i},y’_{i}[/latex] члены [latex]x_{i},y_{i}[/latex] по правилу: если они оба отрицательны, то каждый из них увеличить на 0.5; если отрицательно только одно число, то отрицательное число заменить его квадратом; если оба числа неотрицательны, то каждое из них заменить на среднее арифметическое исходных значений.

Тесты

n [latex]x_{1},\ldots,x_{n}[/latex] [latex]y_{1},\ldots,y_{n}[/latex] [latex]x’_{1},\ldots,x’_{n}[/latex][latex]y’_{1},\ldots,y’_{n}[/latex] Комментарий
4 1 4 -3 8

3 -2 -4 2

2 4 -2.5 5

2 4 -3.5 5

Пройдено
5 0 -0.5 4 -9 0.35

0 -0.5 11 0.247 1.650

0 0 7.5 81 1

0 0 7.5 0.247 1

Пройдено
3 0 3 -0.14942

-3 0 793

0 1.5 0.0223263

9 1.5 793

Пройдено

Реализация (массив структур)

Алгоритм решения (массив структур)
Для выполнения данной задачи, воспользуемся массивом структур. Каждый [latex]i[/latex]-ый элемент такого массива заполняем двумя действительными числами [latex]x_{i}[/latex] и [latex]y_{i}[/latex]. После этого мы выполняем проверку и преобразование этих чисел по заданным в условии правилам. Затем их выводим.

Реализация (класс vector)

Алгоритм решения (класс vector)
Данный способ реализации помогает решить задачу преобразования чисел [latex]x_{1},\ldots,x_{n}[/latex], [latex]y_{1},\ldots, y_{n}[/latex] для неизвестного значения [latex]n[/latex] — количества элементов [latex]x_{i}[/latex] и [latex]y_{i}[/latex]. Их количество будет зависить от количества введенных элементов. Программа считывает элементы [latex]x_{i}[/latex] и [latex]y_{i}[/latex] поочередно, т.е. [latex]x_{1}\rightarrow y_{1}\rightarrow x_{2} \rightarrow y_{2} \rightarrow\ldots\rightarrow x_{n}\rightarrow y_{n}[/latex]. В остальном алгоритм такой же как с массивом структур.

Ссылка на код (массив структур)
Ссылка на код (класс vector)

A271

Задача.
Даны действительные числа [latex]a_{1},\ldots,a_{k}[/latex]. Получить [latex]\sqrt{\frac{\sum\limits_{i=1}^{k}(a_{i}-\tilde{a})^{2}}{k-1}},[/latex] где [latex]\tilde{a}=\frac{1}{k}\sum\limits_{i=1}^{k}a_{i}.[/latex]

Тесты

input [latex]\tilde{a}[/latex] [latex]\sqrt{\frac{\sum\limits_{i=1}^{k}(a_{i}-\tilde{a})^{2}}{k-1}}[/latex] Комментарий
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 8  

4.4712

 

Пройдено
2 8 3 4 5 6 7 9 11 15 17 12 19 7 5 1 7 9 19 14 9  

6.35834659

Пройдено
3 3 3 3 3 0 0 0 5 5 5 15 15 15 15 6 5.8554 Пройдено

Решение

  1. Заполняем вектор действительными числами
  2. Считаем их сумму (с помощью цикла прибавляем каждый элемент вектора).
  3. Находим значение [latex]\tilde{a}[/latex].
  4. Находим сумму под корнем второй формулы через цикл (аналогично п.2)
  5. Производим необходимые арифметические операции для нахождения значения второй формулы.
  6. Вывод значений.
    Ссылка на код

Ю3.25

Задача.

Для заданных [latex]m[/latex] и [latex]n[/latex] вычислить число сочетаний [latex]C_m^n[/latex] непосредственно: [latex]C_m^n=\frac{m!}{n!(m-n)!}[/latex] и по рекуррентным формулам:

• [latex]C_m^n=\frac{m-n+1}{n}\cdot C_m^{n-1}, C_m^1=m;[/latex]

• [latex]C_m^n=C_{m-1}^{n-1}+C_{m-1}^n;C_m^1=m,C_m^m=1.[/latex]

Сравнить время вычислений(или число операций) по каждой формуле.

Тесты:

[latex]m[/latex] [latex]n[/latex] [latex]C_m^n[/latex] Комментарий
122 12  

По первой формуле равно: 1.29803e+16

По второй формуле равно: 1.29803e+16

По третьей формуле равно: 12980291311103116

Первая формула сработала за(в милисек):0.056

Вторая формула сработала за(в милисек):0.009

Третья формула сработала за(в милисек):0.021

 

Пройдено
14 5  

По первой формуле  равно: 2002

По второй формуле равно: 2002

По третьей формуле равно: 2002

Первая формула сработала за(в милисек):0.064

Вторая формула сработала за(в милисек): 0.009

Третья формула сработала за(в милисек):  0.012

Пройдено
16 7 По первой формуле  равно: 11440

По второй формуле равно: 11440

По третьей формуле равно: 11440

Первая формула сработала за(в милисек):0.067

Вторая формула сработала за(в милисек): 0.009

Третья формула сработала за(в милисек):  0.012

Пройдено

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

Ход решения:

1.С помощью цикла [latex]for[/latex] и функции [latex]clock[/latex] я нахожу число сочетаний и время вычислений.

Чтобы посчитать время вычислений по второй рекуррентной формуле я воспользовался Треугольником Паскаля.

Треугольник Паскаля хранится в двумерном массиве и заполняется по указанной в условии формуле начиная с верхнего левого угла.

2.Вывожу число сочетаний

3.С помощью условного оператора [latex]if[/latex] я сравниваю время вычислений.

Ссылка на код

 

 

А808а

Задача.
Дан текст. Группы символов, разделенные пробелами(одним или несколькими) и не содержащие пробелов внутри себя, будем называть, как и прежде, словами.

Для каждого из слов указать, сколько раз оно встречается среди всех слов, образованных символами данного текста.

Тесты

Input Output Комментарий
123 321 1441 123 456 831 1441

123 — 2

1441 -2

321 — 1

456 — 1

831 — 1

 Пройдено
iW@910 b10r l4e iW@910 10o b11 a mU611211a9

10o — 1

a — 1

b10r — 1

b11 — 1

iW@910 — 2

l4e — 1

mU611211a9 — 1

 Пройдено
№!4%» ^&*() +|\/., №!4%» _-=~`;? +|\/., — 1

^&*() — 1

_-=~`;? — 1

№!4%» — 2

Пройдено
Hey Jude, don’t make it bad.
Take a sad song and make it better.
Hey — 1

Jude, — 1

Take — 1

a — 1

and — 1

bad. — 1

better. — 1

don’t — 1

it — 2

make — 2

sad — 1

song — 1

Пройдено

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

 

Ход решения:

Применяя функцию [latex]map[/latex], запишем в индекс массива [latex]m[/latex] слово и увеличим элемент массива данного индекса на единицу. Используя цикл [latex]while[/latex] мы проделаем это для каждого слова введенного с клавиатуры. Если слово повторится , то элемент снова увеличится на единицу. Таким образом получаем количество слов в данном тексте.

С помощью цикла [latex]for[/latex] выводим индекс массива (т.е. слово) и значение (его количество в тексте).

Ссылка на код

А406

Задача

С помощью [latex]x_{ij}, i=1,2; j=1,\ldots,n.[/latex] — действительной матрицы на плоскости задано n точек так, что [latex]x_{1j}, x_{2j}[/latex] — координаты [latex]j[/latex] — точки. Точки попарно соединены отрезками. Найти длину наибольшего отрезка.

Тест

n Матрица [latex]x_{ij}, i=1,2.[/latex] Длина наибольшего отрезка  Комментарий
3  

2 8 4

9 1 5

10 Пройдено
4  

6 14 2 1

9 3 8 0

13.3417 Пройдено
5  

1 8 4 3 7

2 9 5 0 11

11.7047 Пройдено

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

Ход решения:

  1. Вводим матрицу построчно (не очень удобно).
  2. Находим длину наибольшего отрезка.
    С помощью вложенных циклов мы находим длины всех отрезков по формуле
    [latex] AB=\sqrt{(x_{2}-x_{1})^{2}+(y_{2}-y_{1})^{2}}, A(x_{1},y_{1}), B(x_{2},y_{2}). [/latex]
  3. По алгоритму нахождения максимума находим длину наибольшего отрезка.
  4. Выводим матрицу.
  5. Выводим длину наибольшего отрезка.
    Ссылка на код