e-olymp 6125. Простая очередь

Задача

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

  • push n — Добавить в очередь число n (значение n задается после команды). Программа должна вывести ok.
  • pop — Удалить из очереди первый элемент. Программа должна вывести его значение.
  • front — Программа должна вывести значение первого элемента, не удаляя его из очереди.
  • size — Программа должна вывести количество элементов в очереди.
  • clear — Программа должна очистить очередь и вывести ok.
  • exit — Программа должна вывести bye и завершить работу.

Гарантируется, что набор входных команд удовлетворяет следующим требованиям: максимальное количество элементов в очереди в любой момент не превосходит 100, все команды pop и front корректны, то есть при их исполнении в очереди содержится хотя бы один элемент.

Данную задачу также можно найти здесь.

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

Описаны в условии. Смотрите также тесты, расположенные ниже.

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

Описаны в условии. Смотрите также тесты, расположенные ниже.

Тесты

Входные данные Выходные данные
1 push 123
size
push -5
pop
exit
ok
1
ok
123
bye
2 push 1
push 2
front
push 42
pop
exit
ok
ok
1
ok
1
bye
3 push 1
push 2
pop
pop
size
exit
ok
ok
1
2
0
bye

Код

Ход решения

Реализуем абстрактный тип данных очередь, который отвечает принципу FIFO («первый вошёл – первый вышел») с помощью массива. Очередь имеет начало и конец, на которые указывают соответственно start и finish. Изначально очередь является пустой, поэтому start = 0, finish = 0. При добавлении нового элемента в очередь записываем его в конец. finish при этом увеличиваем на единицу. Извлекаемый же элемент берём в начале очереди, после чего start++. Если необходимо получить значение начала очереди, не извлекая его, воспользуемся функцией front(), возвращающей значение первого элемента. Для получения размера очереди используем функцию size(), которая возвращает разницу между концом и началом очереди. Если очередь нужно очистить, то приравниваем finish и start к нулю.

 

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

Код на сайте ideone.com находится здесь.

А282б

Условия задачи

Даны действительные числа [latex]a_{1}[/latex], [latex]a_{2}[/latex], [latex]\ldots[/latex], [latex]a_{2n}[/latex]. Получить [latex]a_{1}[/latex], [latex]a_{2n}[/latex], [latex]a_{2}[/latex], [latex]a_{2n-1}[/latex], [latex]a_{3}[/latex], [latex]\ldots[/latex], [latex]a_{n}[/latex], [latex]a_{n+1}[/latex].

Данную задачу можно найти здесь.

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

Последовательность действительных чисел [latex]a_{1}[/latex], [latex]a_{2}[/latex], [latex]\ldots[/latex], [latex]a_{2n}[/latex].

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

Последовательность действительных чисел [latex]a_{1}[/latex], [latex]a_{2n}[/latex], [latex]a_{2}[/latex], [latex]a_{2n-1}[/latex], [latex]a_{3}[/latex], [latex]\ldots[/latex], [latex]a_{n}[/latex], [latex]a_{n+1}[/latex] .

Тесты

Входные данные Выходные данные
1 1 2 3 4 5 6 1 6 2 5 3 4
2 0 0 0 0 0 1 0 1 0 0 0 0
3 3 12 42 -6 15 0 0 0 501 20 20 20 3 20 12 20 42 20 -6 501 15 0 0 0
4 42 0 17 -2.6 -54 41888 0.25 13 1.3333 -284.73 42 -284.73 0 1.3333 17 13 -2.6 0.25 -54 41888
5 0 1 -1 0 1 -1 97 113 -7.777 0 48 -69 0 -69 1 48 -1 0 0 -7.777 1 113 -1 97

Код

Код на ideone можно найти здесь.

Ход решения

Считываем все числа из входного потока и записываем их в вектор исходной последовательности sequence. Результатом работы нашей программы должна быть новая последовательность действительных чисел result_sequence, которая задаётся по следующему правилу: первый член новой последовательности совпадает с первым членом исходной, второй член новой последовательности является последним членом исходной, третий – второй член исходной и так далее до исчерпания чисел. Иными словами, новая последовательность из [latex]2n[/latex] чисел на нечётных номерах имеет члены исходной последовательности (от первого и до [latex]n[/latex]-го включительно), чётным же номерам новой последовательности соответствуют члены исходной с номерами от [latex]n+1[/latex] до [latex]2n[/latex] включительно, записанные в обратном порядке.

e-olymp 1080. Анаграмматическое расстояние

Условия задачи

Два слова называются анаграмматически одинаковыми, если из букв одного слова можно получить другое слово. Например, occurs является анаграммой для слова succor; и наоборот, dear не является анаграммой слова dared (так как буква d встречается дважды в dared, и только один раз в dear). Наиболее известной английской анаграммой являются слова dog и god.

Анаграмматическим расстоянием двух слов называется минимальное количество букв, которые нужно удалить, чтобы в результате два слова стали анаграмматически одинаковыми. Например, для слов sleep и leap, нужно удалить как минимум три буквы — две из sleep и одну из leap — чтобы остались анаграмматически одинаковые слова (в указанном случае lep). А для слов dog и cat, в которых нет одинаковых букв, анаграмматическое расстояние равно [latex]6[/latex], так как нужно удалить все буквы (любое слово, в том числе и пустая строка, являются анаграммой само к себе).

Ваша задача найти анаграмматическое расстояние для заданных двух слов.

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

В первой строке задано положительное целое число [latex]N[/latex] (не превышающее [latex]60000[/latex]), указывающее количество тестовых примеров. Каждый тестовый пример состоит из двух слов, возможно пустых, каждое из которых записано в отдельной строке (всего [latex]2N[/latex]последующих строк).

Все слова, имеющие не нулевую длину, сформированы из строчных букв английского алфавита (abcdefghijklmnopqrstuvwxyz). Самым длинным словом является pneumonoultramicroscopicsilicovolcanoconiosis.

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

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

Ссылка на задачу находится здесь.

Тесты

Входные данные Выходные данные
1 4
crocus
succor
dares
seared
empty

smell
lemon

Case #1:  0
Case #2:  1
Case #3:  5
Case #4:  4
2 1

 

Case #1:  0
3 5
lol
lolipop
primate
mathematics
kangaroo
kilimanjaro
sister
sisters
android
andromeda
Case #1:  4
Case #2:  8
Case #3:  7
Case #4:  1
Case #5:  4

Код (cstring)

Код на ideone можно найти здесь.

Ход решения

Наша задача состоит в определении количества символов в двух строках, которые необходимо удалить для того, чтобы слова считались анаграммами. Используем  после ввода числа примеров [latex]n[/latex] функцию cin.ignore(), для игнорирования перехода на новую строку, а затем считываем по парам слова. Последовательно проходим все буквы слова в первой строке с помощью цикла for. Если находим эту букву в слове второй строки, увеличиваем счётчик совпадающих букв. Совпадающую букву во второй строке заменяем на символ #, дабы избежать повторных проверок одной и той же буквы в случае её неоднократного появления в первой строке. Общее количество букв в двух строках равняется сумме длин первой и второй строк. Таким образом, чтобы получить анаграмматическое расстояние необходимо вывести:

Умножение matchingLetters на [latex]2[/latex] возникает вследствие того, что (по факту) нужно зачёркивать символы в двух строках.

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

Код на ideone можно найти здесь.

Код (string)

В случае решения данной задачи с помощью класса string используем функцию find() для поиска заданного символа в строке.

Код на ideone можно найти здесь.

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

 

MLoop19

Условие задачи

Вычислите с заданной точностью [latex]\varepsilon[/latex]сумму ряда [latex]\sum\limits_{i=1}^{\infty}{\frac{\sqrt{i+1}}{ie^i}} [/latex].

Задачу также можно найти здесь.

Тесты

Точность [latex]\varepsilon[/latex] Сумма ряда
1 0.1 0.637464
2 0.001 0.685288
3 0.0001 0.685782
4 0.000001 0.685848

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

Поскольку в данной задаче использование рекуррентной формулы приведет только к накоплению погрешности, будем считать каждое слагаемое суммы непосредственно, пока не достигнем заданной точности. Для этого зададим начальное значение переменной exponent = M_E для [latex]i=1[/latex] , а также для первого члена ряда а = sqrt(2)/ exponent. Тогда для каждого значения счетчика нам нужного всего лишь накапливать степень экспоненты и вычислять текущий член ряда по формуле [latex]\frac{\sqrt{i+1}}{i\cdot{e}^{i}} [/latex] , накапливая сумму, пока не достигнем заданной точности эпсилон.

Проверить правильность найденной суммы можно с помощью сайта WolframAlpha.

 

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

Код программы на сайте ideone.

e-olymp 141. Минимальная сумма цифр

Условие задачи:

Сколько натуральных чисел из промежутка [latex][M,N][/latex] имеют наименьшую сумму цифр ?

Задачу также можно найти здесь.

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

Во входном файле два числа [latex]M[/latex] и [latex]N[/latex] ( [latex]1\le M\le N\le 1000000[/latex] ) .

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

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

Тесты

M N Вывод
1 1 100 3
2 2 17 1
3 32 1024 2
4 1 1000000 7
5 10 10 1

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

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

Для решения данной задачи зададим функцию, которая возвращает сумму чисел вводимого нами числа. После ввода границ необходимого промежутка присваиваем минимальную сумму (sumMin) сумме цифр первого числа [latex] M [/latex]. Теперь задаём цикл со счётчиком [latex] i [/latex] от [latex] M + 1 [/latex] до [latex]\le N[/latex]. В случае, когда сумма чисел счётчика меньше сумме цифр числа [latex] M [/latex], присваиваем ей (сумме цифр счётчика i) минимальную сумму цифр и выводим единицу. В противном случае увеличиваем счётчик на единицу и выводим полученный результат. Выводимое число и будет количеством натуральных чисел на промежутке, имеющих наименьшую сумму цифр.

Код программы можно найти здесь.

Ссылка на полностью засчитанное решение на сайте e-olymp.

Mloops 5

Условие задачи

Найдите закономерность и напишите программу, которая выводит аналогичную таблицу для любых чисел [latex] n>0 [/latex] (количество столбцов) и [latex] m>0 [/latex] (количество строк): +++++*+++++*+++++*+++++*+++++*+++++*+++++*+++++*+++++*+++++*+++++*+++++*+++++*+++++*+++++*+++++*+++++*+++++*+++++*+++++*+++++*+++++*+++++*+++++*+++++*+++++*+++++*+++++*+++++*+++++*+++++*+++++*+++++*++ .

Задача находится здесь.

Тесты

n m Таблица
1 25 8 +++++*+++++*+++++*+++++*+
++++*+++++*+++++*+++++*++
+++*+++++*+++++*+++++*+++
++*+++++*+++++*+++++*++++
+*+++++*+++++*+++++*+++++
*+++++*+++++*+++++*+++++*
+++++*+++++*+++++*+++++*+
++++*+++++*+++++*+++++*++
2 6 6 +++++*
++++*+
+++*++
++*+++
+*++++
*+++++
3 2 5 ++
++
++
++
+*

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

Таблица, которую необходимо вывести на экран представляет собой определённую последовательность. Каждый символ таблицы имеет номера столбца и строки (нумерация от 0 до n или m не включительно). Для этого задаём счётчики [latex] i [/latex] и [latex] j [/latex] .  Наша задача — определить закономерность появления символа [latex] \ast [/latex] в данной таблице, поскольку в иных случаях необходимо вывести символ [latex] + [/latex]. В первой строке «звёздочка» встречается в данной таблице в [latex] 6,12,18,24[/latex] столбцах. Во второй строке «звёздочка» находится в [latex] 5,11,17,23[/latex] столбцах. В последующих строках ситуация аналогичная. Можно заметить, что символ [latex] \ast [/latex] стоит на позициях, при которых сумма номера строки и номера столбца делится нацело на 6. Проверяем это условие с помощью тернарной операции:

от суммы номеров столбца и строки отнимаем число [latex] 5 [/latex], поскольку нам необходимо, чтобы первыми пятью символами последовательности были плюсы.

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

Ссылка на рабочий код программы находится здесь.