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

Задача

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

  • push_front Добавить (положить) в начало дека новый элемент. Программа должна вывести ok.
  • push_back Добавить (положить) в конец дека новый элемент. Программа должна вывести ok.
  • pop_front Извлечь из дека первый элемент. Программа должна вывести его значение.
  • pop_back Извлечь из дека последний элемент. Программа должна вывести его значение.
  • front Узнать значение первого элемента (не удаляя его). Программа должна вывести его значение.
  • back Узнать значение последнего элемента (не удаляя его). Программа должна вывести его значение.
  • size Вывести количество элементов в деке.
  • clear Очистить дек (удалить из него все элементы) и вывести ok.
  • exit Программа должна вывести bye и завершить работу.

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

pop_front,
pop_back,
front,
back
всегда корректны.

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

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

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

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

Тесты

Входные данные Выходные данные
push_back 3
push_front 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

Код программы на C++

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

Решение

Создадим массив [latex]folder[/latex] и целочисленные переменные [latex]start[/latex] и [latex]end[/latex] в качестве указателей на начало и конец нашего дека.

  • push_front  — сдвигаем указатель [latex]start[/latex] на [latex]1[/latex] назад, кладем значение в наш дек и выводим ok;
  • push_back  — кладем значение в наш дек, сдвигаем указатель [latex]end[/latex] на [latex]1[/latex] вперед и выводим ok;
  • pop_front  — выводим значение начала дека и перемещаем [latex]start[/latex] вперед на [latex]1[/latex];
  • pop_back  — перемещаем [latex]end[/latex] назад на [latex]1[/latex] и выводим значение конца дека;
  • front  — выводим значение начала дека;
  • back  — выводим значение перед [latex]end[/latex];
  • size  — отнимем от переменной [latex]end[/latex] переменную [latex]start[/latex];
  • clear  — приводим [latex]start[/latex] и [latex]end[/latex] к изначальным позициям;
  • exit  — выводим «bye» и заканчиваем программу.

Ссылки

Ideone C++
Ideone Java
решение e-olymp C++
решение e-olymp Java

Related Images:

e-olymp 1075. Умножение многочленов

Задача с сайта e-olymp.com.
Засчитанное решение. (C++)
Засчитанное решение. (Java)

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

Вводится в символьной форме два многочлена от [latex]x[/latex] с целыми коэффициентами. Вывести их произведение в порядке убывания степеней — также в символьной форме. Степень исходных многочленов не более [latex]10[/latex], коэффициенты исходных многочленов по модулю не более [latex]{ 10 }^{ 4 }[/latex].

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

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

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

В единственной строке выводится многочлен.

Тесты

Входные данные Выходные данные
1 0
0
0
2 x+1
x-1
x^2-1
3 -5
x^2+x+x-2x^3
10x^3-5x^2-10x
3 x^10+2x^9+3x^8
-1
-x^10-2x^9-3x^8
4 x^10+2x^9+3x^8
0
0
5 x^10+5x^2
x^3-4x
x^13-4x^11+5x^5-20x^3

Решение с использованием класса string

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

Нажмите, чтобы выполнить его на ideone.com.

Описание

Сначала в функции main объявляются две строки a и b. В них водятся исходные два многочлена. Но в форме строк, особенно учитывая, что подобные слагаемые не всегда приведены, умножать многочлены не удобно. Потому объявляются три вектора: a_decomposed, b_decomposed и c_decomposed. Первые два имеют размер [latex]11[/latex], поскольку в условии сказано, что многочлены могут быть от нулевой до десятой степени включительно. В них элемент с индексом [latex]i[/latex] равняется коэффициенту при слагаемом многочлена, в котором [latex]x[/latex] имеет степень [latex]i[/latex]. Они заполняются при помощи функции decompose. В ней при помощи функции analyze отдельно анализируется каждое слагаемое многочлена, и результат заносится в вектор. c_decomposed хранит коэффициенты многочлена, полученного умножением двух исходных. Значения его элементов вычисляются при помощи функции multiplicate. После в ходе работы функции compose многочлен в требуемой форме записывается в строку c. Далее, если её первым символом является [latex]+[/latex], он удаляется из строки. Наконец, если c — непустая строка, она выводится. Иначе выводится [latex]0[/latex].

Решение с использованием c-string

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

Нажмите, чтобы выполнить его на ideone.com.

Описание

Алгоритм решения тот же. Следует отметить: поскольку объекты типа char* «не знают» свою длину, и в силу других причин, в некоторых местах программы используются «магические числа». Однако они не взяты случайно, а продиктованы условием задачи (к примеру, тем, что максимальная степень исходных многочленов — [latex]10[/latex] и т.п.). Только подходящее значение переменной max_number_of_symbols было найдено эмпирически.

Решение на Java

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

Нажмите, чтобы выполнить его на ideone.com.

Related Images:

ASCII ART

Task

In stations and airports you often see this type of screen:

Have you ever asked yourself how it might be possible to simulate this display on a good old terminal? We have: with ASCII art!

Your mission is to write a program that can display a line of text in ASCII art in a style you are given as input.

Input

Line 1: the width L of a letter represented in ASCII art. All letters are the same width.
Line 2: the height H of a letter represented in ASCII art. All letters are the same height.
Line 3: the line of text T, composed of N ASCII characters.
Following H lines: the string of characters ABCDEFGHIJKLMNOPQRSTUVWXYZ? Represented in ASCII art.

[latex]0 < [/latex] L[latex] < 30[/latex] [latex]0 < [/latex] H[latex] < 30[/latex] [latex]0 < [/latex] N[latex] < 200[/latex]

Output

The text T in ASCII art.
The characters a to z are shown in ASCII art by their equivalent in upper case.
The characters that are not in the intervals [a-z] or [A-Z] will be shown as a question mark in ASCII art.

Tests

Input Output
1
1
Encoding using ASCII? Hah!
?ZYXWVUTSRQPONMLKJIHGFEDCBA
WNYMXSNUAGISNUA?IYSSAAT?TA

Codes of the program

Solution of the task

After saving the string, we can convert the task to «semi-stream processing». After we read and save the first line of ASCII characters into alphabet array, we start to print the tops of the ASCII letters. Then the same procedure is repeated on the following lines, and new parts of ASCII letters are read over the old ones into alphabet.

Links

Related Images:

There is no Spoon — Episode 1

Task

The Goal

The game is played on a rectangular grid with a given size. Some cells contain power nodes. The rest of the cells are empty.

The goal is to find, when they exist, the horizontal and vertical neighbors of each node.

Rules

To do this, you must find each [latex]\left( x1, y1 \right)[/latex] coordinates containing a node, and display the [latex]\left(x2, y2\right)[/latex] coordinates of the next node to the right, and the [latex]\left(x3, y3\right)[/latex] coordinates of the next node to the bottom within the grid.

If neighbor does not exist, you must output the coordinates [latex]\left(-1, -1\right)[/latex] instead of [latex]\left(x2, y2\right)[/latex] and/or [latex]\left(x3, y3\right)[/latex].

You lose if:

  • You give an incorrect neighbor for a node.
  • You give the neighbors for an empty cell.
  • You compute the same node twice.
  • You forget to compute the neighbors of a node.

Game input

The program must first read the initialization data from standard input. Then, provide to the standard output one line per instruction.

Initialization input

Line 1: one integer width for the number of cells along the x axis.

Line 2: one integer height for the number of cells along the y axis.

Next height lines: A string line containing width characters. A dot . represents an empty cell. A zero 0 represents a cell containing a node.

[latex]0 <[/latex] width[latex]\le 30[/latex]
[latex]0 <[/latex] height[latex]\le 30[/latex]

Output for one game turn

One line per node. Six integers on each line: x1 y1 x2 y2 x3 y3 Where:

  • ( x1, y1) the coordinates of a node.
  • ( x2, y2) the coordinates the closest neighbor on the right of the node.
  • ( x3, y3) the coordinates the closest bottom neighbor.
[latex]0 \le[/latex] x1[latex]<[/latex] width
[latex]0 \le[/latex] y2[latex]<[/latex] height
[latex]-1 \le[/latex] x2, x3[latex]<[/latex] width
[latex]-1 \le[/latex] y2, y3[latex]<[/latex] height
Alloted response time to first output line [latex]\le 1[/latex]s.
Response time between two output lines [latex]\le 100[/latex]ms.

Tests

Input Output
2 2
00
0.
0 0 1 0 0 1
1 0 -1 -1 -1 -1
0 1 -1 -1 -1 -1
4 4
.0..
.000
000.
..0.
1 0 -1 -1 1 1
1 1 2 1 1 2
2 1 3 1 2 2
3 1 -1 -1 -1 -1
0 2 1 2 -1 -1
1 2 2 2 -1 -1
2 2 -1 -1 2 3
2 3 -1 -1 -1 -1

The code of the program

Solution of the task

First of all, we must pay attention, that we have to find the closest neighbor. It doesn’t mean, that if there is no neighbor on adjacent cells, then the answer will be negative, because the neighbor may be further. This leads to the fact, that the task can not be completed without memorization of the whole list of cells.

After storing every string in array, the task becomes simple: we go using the cycle through every cell, and if the cell contains a node, then we launch two cycles from it in two directions (to the right and to the bottom), and assume there are no neighbors with assigning value -1 to both variables ansX and ansY. If there will be no nodes found, the value will remain the same, otherwise variables will take values of the node coordinates. In any case, the result will be correct.

This process is optimized by usage of the following: the [latex]x[/latex] coordinate of the closest right neighbor (or the value of width) is saved in a variable x2. Whether we find a neighbor or no, we can start the further horizontal search right from the coordinate x2, because empty cells must be skipped anyway.

Links

Related Images:

Код Хаффмана

Задача

Дана строка, после которой следует символ перехода на следующую строку (далее — endl. Вывести:

  1. Код графа на языке DOT, иллюстрирующий кодирование символов строки;
  2. Символы строки и соответствующие им коды Хаффмана;
  3. Закодированную строку.

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

Некоторая последовательность символов и endl.

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

  1. Код графа на языке DOT, иллюстрирующий кодирование символов строки;
  2. Символы строки и соответствующие им коды Хаффмана;
  3. Закодированная строка.

Тест

Входные данные Выходные данные
MOLOKO KIPIT digraph G {
"'MLO KITP', 12, code: ''" -> "'MLO', 5, code: '0'" [ label = "0" ];
"'MLO KITP', 12, code: ''" -> "' KITP', 7, code: '1'" [ label = "1" ];
"'MLO', 5, code: '0'" -> "'ML', 2, code: '00'" [ label = "0" ];
"'MLO', 5, code: '0'" -> "'O', 3, code: '01'" [ label = "1" ];
"'ML', 2, code: '00'" -> "'M', 1, code: '000'" [ label = "0" ];
"'ML', 2, code: '00'" -> "'L', 1, code: '001'" [ label = "1" ];
"' KITP', 7, code: '1'" -> "' K', 3, code: '10'" [ label = "0" ];
"' KITP', 7, code: '1'" -> "'ITP', 4, code: '11'" [ label = "1" ];
"' K', 3, code: '10'" -> "' ', 1, code: '100'" [ label = "0" ];
"' K', 3, code: '10'" -> "'K', 2, code: '101'" [ label = "1" ];
"'ITP', 4, code: '11'" -> "'I', 2, code: '110'" [ label = "0" ];
"'ITP', 4, code: '11'" -> "'TP', 2, code: '111'" [ label = "1" ];
"'TP', 2, code: '111'" -> "'T', 1, code: '1110'" [ label = "0" ];
"'TP', 2, code: '111'" -> "'P', 1, code: '1111'" [ label = "1" ];
}

Codes of letters:
'O'(01) 'K'(101) 'I'(110) 'T'(1110) 'P'(1111) 'M'(000) 'L'(001) ' '(100)

Encoded string:
00001001011010110010111011111101110

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

Решение задачи

Для начала считываем посимвольно строку и запоминаем её, параллельно запоминая частоты появлений символов в ней в массиве count. Останавливаем считывание, когда встречается endl. После этого отсортировуем массив count в порядке убывания частот.

После этого элементы массива count, которые имеют ненулевую частоту, преобразовываем в элементы вектора tree (при этом символы конвертируются в строки), который после сортируется в порядке возрастания частот. Затем обрабатываем массив по алгортиму Хаффмана, объединяя элементы вектора с номерами [latex]j[/latex], [latex]j+1[/latex] в новый (который будет представлять собой структуру из конкатенации строк ранее упомянутых элементов и суммы их частот, а так же номеров его «предков»). После этого вектор вновь сортируется по частотам/суммам частот в порядке возрастания начиная с номера[latex]j+2[/latex], при этом элементы, которые имеют больший размер строк будут иметь меньший приоритет.

Такой алгоритм приводит к тому, что элементы с меньшей частотой/суммой частот не затрагиваются при добавлении новых, и система индексов (условных указателей на «предков») не нарушается.

После этого, используя поиск в глубину, кодируем элементы массива tree, начиная с последнего (строка которого в результате использования алгоритма всегда оказывается объединением всех символов). Остальная часть решения поставленной задачи — вопрос техники.

Ссылки

Related Images:

MS 7. Средняя зарплата

Задача

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

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

Фамилия работника ([latex]name[/latex]) и величина его зарплаты ([latex]sal[/latex]).

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

Средняя зарплата по компании.

Тесты

Входные данные Выходные данные
[latex]name[/latex] [latex]sal[/latex]
Ivanov 200 200
Ivanov

Smirnov

Popov

Sokolov

100

150

200

150

150

Код программы на C++

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

Решение

В переменную [latex]total[/latex] которая изначально равна [latex]0[/latex] прибавляем зарплату каждого сотрудника, а [latex]sum[/latex] показывает количество сотрудников. Выводим зарплату всех сотрудников деленную на их количество.

Ссылки

Ideone C++
Ideone Java

Related Images:

AL6

Задача AL6

Условие

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

Тесты

Входные данные Выходные данные
1 ( NO
2 )) NO
3 [} NO
4 {} YES
5 (){}[] YES
6 ({[]}{}) YES
7 [({}())[] NO

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

Решение

Арифметическое выражение является правильным если каждой открывающей скобке соответствует единственная закрывающая. Что бы убедится в правильности выражения необходимо создать структуру [latex]stack[/latex], в которую поочередно записываются открывающиеся скобки. Если встречается закрывающая скобка того же типа, что и последняя открывающая, то они обе удаляются, так как не влияют на правильность выражения. Если же закрывающая скобка не соответствует типу последней открывающей, то такое арифметическое выражение не является правильным. Если после обработки всей последовательности в стеке не осталось элементов, то такое выражение является правильным. В случае отсутствия скобок выражение также правильное.

Ссылки

Код программы на ideone.com

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

Related Images:

e-olymp 185. Орки будущего

Условие

Задача взята с сайта e-olymp. Полное условие можно прочитать здесь.

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

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

Из условия:

«…теперь в их алфавите в качестве гласных использовались только буквы «а», «o», «e», «u».»

«…орки иногда устраивали состязания в красноречии. При этом расходы их энергии были тем больше, чем меньше отношение количества слогов к количеству слов в произнесенной речи.»

«Самым «Годистым» орком считался тот из них, у кого это отношение было наименьшим, а в случае равенства этого показателя тот, у кого в произнесенной речи было больше сказано слов. Ваша задача – определить Орка года по заданному критерию.»

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

Единственное число – номер Орка, признанного Орком Года. В случае, если однозначно определить победителя невозможно, вывести   "O-o-o-rks...".

Решение

Напишем 2 функции: int countSyllables(char* speech), которая будет считать гласные (т.к. кол-во слогов всегда равно кол-ву гласных), и int countWords(char* speech), считающую кол-во слов. Для написания первой воспользуемся стандартной функцией strpbrk(), для второй — функцией strtok(). Для каждой считанной строки будем по очереди вызывать эти 2 функции и заносить полученные значения в соответствующие массивы syllables и words (вызывать будем именно в таком порядке, т.к. функция strtok() делает строку непригодной к дальнейшему использованию).

Далее, чтобы избежать работы с вещественными числами (что может привести к потере точности) будем сравнивать полученные результаты согласно требованиям, но вместо деления воспользуемся соотношением пропорции. Заведем переменную-флаг ambiguous, показывающую, однозначен ли победитель. В зависимости от ее значения, выведем номер победителя (переменная winner, по умолчанию победитель — первый орк) или строку "O-o-o-rks..."

Тесты

Входные данные Выходные данные
1 2
Hello, World!
Ok.
2
2  3
Ooh, hey there 😀
Hello, World of me!
Will be ambiguous???
 O-o-o-rks…
3  4
Some people like C!
Some say Java is better.
Heh, or maybe Python?
Who knows for sure?
 O-o-o-rks…
4  5
A Lannister always pays his debts.
Winter is coming…
Hear me roar!
King of the North!
Sherlock?
 1
5  8
O-o-o-rks…
Is not the same as…
O-o-o-rks!
or
O-o-orks…
…trust me,…
…when writing code, one must be extremely careful!
…beware!
 O-o-o-rks…

Код

Ссылки

Код на ideaone.

Засчитанное решение на e-olymp.

Related Images:

e-olymp 1073. Статическая сложность

Условие

Задача взята с сайта e-olymp, полное условие можно прочитать здесь.

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

В первой строке находится целое число [latex]k[/latex] — число программ во входном файле. Затем идут [latex]k[/latex] программ, удовлетворяющих приведенной грамматике. Пробелы и переводы строк могут встречаться везде в программе, но не в ключевых словах [latex]BEGIN[/latex],  [latex]END[/latex], [latex]LOOP[/latex] и [latex]OP[/latex], нет их и в целых числах.

Вложенность операторов [latex]LOOP[/latex] не превышает [latex]10[/latex], размер входного файла не более [latex]2[/latex] Кбайт, коэффициенты многочлена в ответе не превышают [latex]50000[/latex].

(Примечание: то, что представляет из себя программа, можно прочитать по ссылке выше.)

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

Для каждой программы сначала идет строка с номером программы. В следующей строке записывается время работы программы в терминах [latex]n[/latex] — многочлен степени не более [latex]10[/latex]. Многочлен должен быть записан обычным способом, то есть подобные слагаемые должны быть приведены, слагаемое большей степени должно предшествовать слагаемому меньшей степени, слагаемые с коэффициентом [latex]0[/latex] не записываются, множители [latex]1[/latex] не записываются. Общий вид второй строки [latex]Runtime = a*n^{10}+b*n^9+\ldots+i*n^2+j*n+k[/latex]. Если время выполнения нулевое, нужно вывести [latex]Runtime = 0[/latex]. За строкой с многочленом должна следовать пустая строка, кроме последнего тестового случая.

Решение

Создадим массив коэффициентов [latex]coefficients[/latex] на 11 элементов (нулевой элемент — свободный член, 10-й — десятая (максимальная) степень). В цикле для каждой программы будем:

  1. Обнулять массив [latex]coefficients[/latex].
  2. Заполнять его новыми данными с помощью функции  void getCoefficients(int* coefficients);
  3. Строить на основании полученных коэффициентов требуемую строку-многочлен, за это отвечает функция string toString(int* coefficients);
  4. Выводить требуемую информацию.

Рассмотрим процесс заполнения массива. Создадим вектор для строк [latex]params[/latex], где будем хранить кол-ва повторений для всех открытых циклах, от внешнего к внутреннему, и переменную-счетчик [latex]keywords[/latex]. Функция будет завершать свою работу при значении [latex]keywords[/latex] равном [latex]0[/latex]. Изначально присвоим [latex]keywords = 1[/latex] (оператор [latex]BEGIN[/latex]). Далее, в цикле будем, в зависимости от прочитанного оператора:

  • [latex]END[/latex]: уменьшаем значение [latex]keywords[/latex] на [latex]1[/latex], удаляем последний элемент из [latex]params[/latex] (чтобы не было проблем с последним оператором [latex]END[/latex] (пустой вектор), положим в него перед циклом строку «[latex]1[/latex]»). Если [latex]keywords[/latex] равно нулю — завершаем работу.
  • [latex]LOOP[/latex]: увеличиваем значение [latex]keywords[/latex] на [latex]1[/latex], считываем следующую строку и добавляем ее в конец [latex]params[/latex].
  • [latex]OP[/latex]: Считываем следующую строку, преобразовываем ее к числу (кол-ву операций) стандартной функцией stoi(). Далее, проходя по строкам из [latex]params[/latex], если строка равна [latex]n[/latex], увеличиваем степень (номер ячейки массива, куда прибавим результат) на [latex]1[/latex], иначе — преобразовываем к числу и домножаем на кол-во операций. Прибавляем полученный результат к числу в соответствующей ячейке массива.

Функция toString() реализована достаточно просто (см. код). Пробегаем по элементам массива с конца, и если элемент [latex]n[/latex] не равен нулю, прибавляем к строке-многочлену  соответствующий набор символов (отдельно учитывая случаи при [latex]n = 1[/latex], [latex]n=-1[/latex], первой и нулевой степени и т.д.). Если в итоге строка пустая, возвращаем «[latex]0[/latex]».

Тесты

Ввод Вывод
1 2
BEGIN
LOOP n
OP 4
LOOP 3
LOOP n
OP 1
END
OP 2
END
OP 1
END
OP 17
END

BEGIN
OP 1997 LOOP n LOOP n OP 1 END END
END
Program #1
Runtime = 3*n^2+11*n+17

Program #2
Runtime = n^2+1997

2 3
BEGIN
END

BEGIN
LOOP n LOOP n LOOP n OP 1
LOOP n LOOP n LOOP n OP 1
LOOP n LOOP n LOOP n OP 1
END END END OP 3
END END END OP 3
END END END OP 3
END

BEGIN OP 42
LOOP n LOOP 5 LOOP n
OP 7 END OP 2 END OP 1 END
OP 1 END
Program #1
Runtime = 0

Program #2
Runtime = n^9+4*n^6+4*n^3+3

Program #3
Runtime = 35*n^2+11*n+43

Код

 

Ссылки

Засчитанное решение на e-olymp.

Рабочий код на ideaone.

Related Images:

e-olymp 1072. Химические реакции

Условие

Задача взята с сайта e-olymp, полное условие можно прочитать здесь.

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

В первой строке находится формула — левая часть уравнения, во второй- одно число [latex]N (1 \leq N \leq 10)[/latex] — количество рассматриваемых правых частей, в каждой из последующих [latex]N[/latex] строк — одна формула — предполагаемая правая часть уравнения.

Длина формулы не превосходит [latex]100[/latex] символов, каждый отдельный химический элемент встречается всего не более [latex]10000[/latex] раз в каждой формуле.

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

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

Для каждой из [latex]N[/latex] заданных строк вывести одну строку вида

формула левой части==формула правой части

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

формула левой части!=формула правой части

Здесь формула левой части должна быть заменена посимвольной копией формулы левой части, как она дана в первой строке входного файла, а формула правой части — замещена точной копией формулы правой части, как она дана во входном файле. В строках не должно быть пробелов.

Решение (вспомогательные функции)

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

  1. Определяет, является ли символ цифрой.
  2. Определяет, является ли символ буквой в верхнем регистре.
  3. Определяет, является ли символ буквой в нижнем регистре.
  4. Будем хранить содержимое формулы используя структуру map (карта), ключами будут выступать названия элементов (строки), значениями — количества их вхождений. Если элемента в карте нет, добавляем пару <элемент, кол-во>, иначе — прибавляем к старом числу вхождений новое. За это отвечает следующая функция.
  5. Для простоты разобьем формулу на подформулы (по знаку [latex]+[/latex], если он встречается), и будем работать с каждой формулой по отдельности. Функция разбивает строку на подстроки по знаку [latex]+[/latex] и заполняет ими вектор [latex]storage[/latex] (так как мы не знаем кол-во подформул заранее, вектор предпочтительнее массива).
  6. По условию, перед каждой подформулой может идти множитель, относящейся ко всей подформуле. Функция возвращает множитель ( [latex]1[/latex], если множитель не записан явно).
  7. Основная функция. Добавляет в карту [latex]content[/latex] содержимое подформулы.
  8. Обрабатывает формулу. Просто вызывает функции №[latex]6[/latex] и №[latex]7[/latex] по очереди для каждой из подформул (элементов из [latex]subformulas[/latex]).

Решение (основной алгоритм)

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

Тут:

  1. [latex]formula[/latex] — подформула обрабатываемой формулы (без общего множителя);
  2. [latex]multiplier[/latex] — множитель, определяется предыдущей функцией, перед вызовом данной;
  3. [latex]content[/latex] — карта, куда записываются элементы всех подформул текущей формулы (доступ осуществляется по адресу).

Алгоритм разделяется на 2 случая, в зависимости от наличия скобок. Предположим, скобок в подформуле (далее — просто формуле) нет. Заведем переменные [latex]name[/latex] (название элемента. тип string) и [latex]coefficient[/latex] (задний коэффициент, тип string). Тогда, проходя по порядку по символам формулы, будем выполнять следующие действия в зависимости от текущего символа([latex]c[/latex]):

  1. [latex]c[/latex] — цифра: добавляем его в конец строки [latex]coefficient[/latex];
  2. [latex]c[/latex] — буква в нижнем регистре: добавляем его в конец строки [latex]name[/latex];
  3. [latex]c[/latex] —  буква в верхнем регистре: если строка [latex]name[/latex] — пустая (первый элемент в формуле), то добавляем его в конец строки [latex]name[/latex]. Иначе, сперва обнуляем [latex]name[/latex], потом добавляем. Тогда, если строка [latex]coefficient[/latex] — пустая, присваиваем [latex]coefficient=[/latex]»[latex]1[/latex]». Получаем количество вхождений элемента как [latex]multiplier*stoi(coefficient)[/latex], где stoi() — стандартная функция, преобразующая число к строке. Затем добавляем в карту элемент и полученное кол-во вхождений.

(Примечание: пункт [latex]3[/latex] для последнего элемента (кроме обновления значения [latex]name[/latex]) придется повторить отдельно.)

Если же в формуле имеются скобки, то:

  1. Находим первую открывающую скобку.
  2. Находим соответствующую ей закрывающую скобку.
  3. Для выражения в скобках вычисляем задний коэффициент (см. код), заносим в переменную [latex]newMultiplier[/latex] значение множителя для выражения внутри скобок.
  4. Рекурсивно вызываем функцию getContent() для:
    1. Выражения перед открывающей скобкой, если формула не начинается с нее.
      ([latex]begin[/latex] — номер первого символа внутри скобок.)
    2. Выражения внутри скобок.
      ([latex]end[/latex] — номер закрывающей скобки.)
    3. Выражения после закрывающей скобки или заднего коэффициента, если присутствует (если только скобка/коэффициент не является концом формулы).
      ([latex]afterEnd[/latex] — следующий после скобки/коэффициента символ.)

Этот алгоритм фактически является решением задачи. Теперь в методе [latex]main[/latex] надо всего лишь обработать главную формулу, а затем для каждого случая в цикле — сравниваемую с ней формулу, сравнив после содержимое их карт (сравнение осуществляется просто используя оператор сравнения ==). Обработка подразумевает последовательный вызов функций  split() и  process().

Тесты

Ввод Вывод
1 C2H5OH+3O2+3(SiO2)
6
2CO2+3H2O+3SiO2
2C+6H+13O+3Si
99C2H5OH+3SiO2
3SiO4+C2H5OH
C2H5OH+3O2+3(SiO2)+Ge
3(Si(O)2)+2CO+3H2O+O2
C2H5OH+3O2+3(SiO2)==2CO2+3H2O+3SiO2
C2H5OH+3O2+3(SiO2)==2C+6H+13O+3Si
C2H5OH+3O2+3(SiO2)!=99C2H5OH+3SiO2
C2H5OH+3O2+3(SiO2)==3SiO4+C2H5OH
C2H5OH+3O2+3(SiO2)!=C2H5OH+3O2+3(SiO2)+Ge
C2H5OH+3O2+3(SiO2)==3(Si(O)2)+2CO+3H2O+O2
2 2H2O
5
HHOHHO
2H+H2+(O(O))
2((H2)O)
HOHHOHe
H4O
2H2O==HHOHHO
2H2O==2H+H2+(O(O))
2H2O==2((H2)O)
2H2O!=HOHHOHe
2H2O!=H4O
3 8Zn+Ar4+Ne
3
Ne(Ar2(Zn)4)2
2Ne(Ar2(Zn)4)
Ne+2Zn2(((((Ar)))))2Zn2
8Zn+Ar4+Ne==Ne(Ar2(Zn)4)2
8Zn+Ar4+Ne!=2Ne(Ar2(Zn)4)
8Zn+Ar4+Ne==Ne+2Zn2(((((Ar)))))2Zn2

Код

Ссылки

Засчитанное решение на e-olymp.

Код на ideaone.

Related Images:

e-olymp 1077. Java против C++

Задача. Сторонники языков Java и C++ часто спорят о том, какой язык лучше для решения олимпиадных задач. Одни говорят, что в Java есть масса полезных библиотек для работы со строками, хорошо реализованы механизмы чтения и вывода данных, а так же радует встроенные возможности для реализации длинной арифметики. С другой стороны, С++ является классическим языком, скорость выполнения программ благодаря существующим компиляторам (например, Intel Compiler 10.0) гораздо выше, чем у Java.

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

В языке Java принято первое слово, входящее в название переменной записывать с маленькой латинской буквы, следующее слово идет с большой буквы (только первая буква слова большая), слова не имеют разделителей и состоят только из латинских букв. Например, правильные записи переменных в Java могут выглядеть следующим образом: javaIdentifier, longAndMnemonicIdentifier, name,nEERC.

В языке C++ для описания переменных используются только маленькие латинские символы и символ «_», который отделяет непустые слова друг от друга. Примеры: java_identifier, long_and_mnemonic_identifier, name, n_e_e_r_c.

Вам требуется написать программу, которая преобразует переменную, записанную на одном языке в формат другого языка.

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

Во входном файле задано наименование переменной длиной не более [latex]100[/latex] символов.

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

В выходной файл требуется вывести аналог имени переменной в другом языке. Т.е. если переменная представлена в формате Java, то следует перевести в формат C++ и наоборот. В том случае, когда имя переменной не соответствует ни одному из вышеописанных языков, следует вывести «Error!«.

Задача взята с сайта e-olymp.

Тесты

Test Input Output
1 java_word javaWord
2 cppWorD cpp_wor_d
3 simpleword simpleword
4 two__underscores Error!
5 _underscore_in_the_beginning Error!
6 underscore_in_the_end_ Error!
7 UppercaseInTheBeginning Error!
8 mixed_Style Error!

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

 

Алгоритм

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

Для удобства я изобразила этот алгоритм в виде схемы:

MMMMEWWWWWW

*круговая стрелочка означает, что мы остаемся в этом же состоянии.

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

Когда мы считываем очередной символ, мы переходим в другое состояние либо остаемся в предыдущем. В состояние Error(отмечено красным) мы переходим, если считаем какую-любо последовательность символов, не подходящую ни под один из стандартов.

Отдельно следует поговорить о состоянии CPP delimeter. Оно используется для контроля количества подчеркиваний. Если в нашей предполагаемой С++ переменной встречается подчеркивание, ей сразу же присваивается данное состояние, чтобы, при наличии второго подчеркивания сразу же перевести ее в состояние Error in CPP.

Финальные состояния отмечены зеленым цветом. В них мы переходим только после окончания строки непосредственно из предыдущего состояния.  Переход в состояние Universal означает, что исходная строка состоит исключительно из маленьких букв и подходит как для языка Java, так и для C++.

Определив стандарт, к которому принадлежит переменная, мы вызываем блок перевода. Результат всегда записываем в отдельную переменную. В случае Java мы снова последовательно перебираем все символы строки и заменяем каждую встретившуюся большую букву на подчеркивание и эту же букву в маленьком регистре. Размер строки в этом случае увеличивается на количество больших букв в ее исходном варианте.  В случае же С++ мы удаляем каждое подчеркивание, сдвигая все последующие символы, а первый из них переводим в большой регистр. Очевидно, что размер строки в этом случае будет уменьшен на количество подчеркиваний.

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

Засчитаное решение на сайте e-olymp

Related Images:

e-olymp 2165. Лишние пробелы

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

  • он находится в самом начале строки, до самого первого слова;
  • он находится в конце строки, после самого последнего слова;
  • несколько пробелов расположены между двумя словами (проще говоря, если слова разделены более чем одним пробелом, тогда все пробелы кроме одного — лишние).

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

Дана строка [latex]s[/latex] (0 ≤ |S| ≤ 255). Строка содержит только латинские буквы и пробелы.

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

Требуется вывести строку без лишних пробелов.

Код

Код

Тесты

Ivanov     Maxim
Scott      Fitzgerald
Gertruda      Stal
John      Green

Решение

Первый код написан на string. Вводим строку [latex]s[/latex], которая содержит латинские буквы и пробелы. В цикле рассматриваем все символы строки от начала до конца. В условии после каждого следующего символа ставим пробелы, используем функцию erase, которая удаляет из строки лишние пробелы. Выводим строку.

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

Ideone.com

Ideone.com

 

Related Images:

А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] выводим индекс массива (т.е. слово) и значение (его количество в тексте).

Ссылка на код

Related Images:

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 можно найти здесь.

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

 

Related Images:

e-olymp 2459. Юбилей Винни-Пуха

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

Вот и наступил долгожданный Юбилей Винни-Пуха. В волшебный лес на праздник собралось множество гостей. В том числе Винни-Пух пригласил к себе друзей из других галактик. К сожалению, когда он посылал приглашения, он совсем забыл, что на планете, где живут его друзья инопланетяне, все читают не слева направо, а справа налево. Винни-Пух понимает, что к Юбилею они уже не прилетят, но медвежонок не унывает. Он хочет проверить, правда ли, что дата его Юбилея, прочитанная справа налево, тоже существует, и инопланетяне прилетят в другой день. Помогите Винни-Пуху определить, ждать ли ему в гости инопланетных друзей.

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

Входной файл содержит дату Юбилея Винни-Пуха в формате dd.mm.gggg. Гарантируется, что дата корректна.

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

В выходной файл нужно вывести YES, если дата, читающаяся справа налево корректна, и NO в противном случае.

 

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

Тесты

Входные данные Выходные данные
23.02.2002 YES
20.02.2023 NO
20.12.2015 NO
20.12.2051 YES

Решение

Как только получили строку из стандартного ввода, воспользуемся функцией reverse(). Эта функция записывает нашу строку «задом наперед», в это же время удаляя символ ‘.’ из строки. Так как я точно знаю, что строка из ввода записана верно, то я могу не проверять остальные символы. Пользуясь этим же фактом я завел три переменные целочисленного типа: day, month, year. В новой строке присутствуют только цифры, поэтому я присваиваю каждой новой переменной соответствующие подстроки, после приведения типа string к типу int с помощью функции stoi(). В выводе проверяется соответствуют ли значения дня и месяца требованиям. День проверяется с помощью функции get_days(). Она позволяет получить количество дней в зависимости от месяца и года. В самой функции get_days() используется функция is_leap(), которая проверяет год на високосность и возвращается булевское значение. В зависимости от этого значения, изменяется значение количества дней в феврале — 28 или 29 соответственно. Когда наши числа прошли все проверки, то мы получаем на вывод «YES», если новая дата является корректной или «NO» в ином случае.

 

Код на ideone.com

Засчитанная задача на e-olymp.com

Related Images:

e-olymp 1308. Наибольшая грань подстроки

Условие

Гранью (border, verge, brink) [latex]br[/latex] строки [latex]S[/latex] называется любой собственный префикс этой строки, равный суффиксу [latex]S[/latex].

Строка [latex]S = abaababaabaab[/latex] имеет две грани (не пустые): [latex]ab[/latex] и [latex]abaab[/latex]. Строка [latex]S = abaabaab[/latex] также имеет две грани: [latex]ab[/latex] и [latex]abaab[/latex], но вторая грань — перекрывающаяся. Строка длины [latex]n[/latex] из повторяющегося символа, например [latex]aaaaaaaa[/latex] (или [latex]a^8[/latex]), имеет [latex]n — 1[/latex] грань. Для [latex]S = a^8[/latex] это грани: [latex]a[/latex], [latex]aa[/latex], [latex]aaa[/latex], [latex]aaaa[/latex], [latex]aaaaa[/latex], [latex]aaaaaa[/latex], [latex]aaaaaaa[/latex].

Понятие «собственный префикс» исключает грань, совпадающую с самой строкой.

Длина грани — это количество символов в ней.

Сделаем обобщение задачи. Пусть необходимо вычислить значения наибольших граней для всех подстрок [latex]S[1..i][/latex] ([latex]i = 1..n[/latex])  и сохранить их в массиве [latex]br[1..n][/latex].

Найдите наибольшее значение грани в массиве наибольших граней [latex]br[/latex] для всех подстрок [latex]S[/latex].

Тестирование

Входные данные Выходные данные Комментарий
1 abaabaab 5 abaab в исходной строке
2 abaababaabaab 6 abaaba в подстроке abaababaabaab
3 aaaaaaaa 7 aaaaaaa в исходной строке
4 YM 0 Грань отсутствует, т.к. префикс и суффикс не могут совпадать с самой строкой, а кроме Y в качестве префикса и M в качестве суффикса вариантов выбора нет
5 &#%*%#& 1 & в исходной строке
6 15015105 2 15 в подстроке 15015105
7 f0A+.f0A+.f0A.+.A0f 8 f0A+.f0A в подстроке f0A+.f0A+.f0A.+.A0f

Код

Решение

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

В основе программы лежит алгоритм, идея которого заключается не в переборе подстрок с последующим поиском граней в них (так как это было бы очень ресурсозатратно), а в переборе смещений префикса и суффикса друг относительно друга и вычислении максимальной грани, которую можно получить в каждом из таких смещений. Цикл перебора выглядит следующим образом:

  1. Так как по условию грань не может совпадать со строкой, перебор начнем со случая, когда первый символ суффикса находится на второй позиции в строке, а первый символ префикса — на первой позиции. В каждой следующей итерации первый символ суффикса будет смещаться на одну позицию вправо, но первый символ префикса будет неизменно оставаться на первой позиции. Цикл продолжается до тех пор, пока не дойдем до случая, когда первый символ суффикса будет последним символом строки, и пока количество символов от начала суффикса до конца строки будет больше длины максимальной найденной на данный момент грани (это условие необязательно, но оно ускоряет работу программы, отбрасывая варианты, когда получить более длинную грань уже никаким образом не получится):
  2. Начнем параллельно «двигаться» вправо по строке, проверяя на совпадение соответствующие символы префикса и суффикса и продолжая до тех пор, пока не наткнемся на различные символы или пока не дойдем до конца строки. При этом будем попутно накапливать значение длины текущей грани, пока пары символов совпадают. К примеру, если в очередной итерации первые символы префикса и суффикса — это первый и третий символы строки соответственно, то сначала проверим на совпадение символы на позициях 1 и 3, затем 2 и 4, 3 и 5 и т. д.
    В виду того, что нумерация символов в строке начинается с нуля, переменная j выполняет здесь одновременно роль первого символа префикса и длины текущей грани.
  3. Сравним длину текущей грани с длиной максимальной грани и, если необходимо, обновим значение максимальной.

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

Ссылки

Условие задачи на E-Olymp;

Код программы на Ideone.com;

Подтверждение решения на E-Olymp.

Related Images:

e-olymp 329. Количество слов

Условие

Есть некоторое предложение на неизвестном языке. Посчитать количество слов в нем. Буквами алфавита в неизвестном языке являются буквы латинского алфавита и арабские цифры. Гарантируется, что других символов, кроме пробелов и знаков препинания в предложении нет.

Тестирование

Входные данные Выходные данные
1 Hello, world! 2
2 War is Peace. Freedom is Slavery. Ignorance is Strength. 9
3 — «4», «8», <15>; (16), {23}, [42]!? 6
4  A flock of sparrows – some of them juveniles – alighted and sang.  11
5 A mean Earth solar day is approximately 24 hours, whereas a mean Martian ‘sol’ is 24 hours, 39 minutes, and 35.244 seconds. 22
6 Lorem ipsum dolor sit amet, consectetur adipisicing elit, sed do eiusmod tempor incididunt ut labore et dolore magna aliqua. 19

Код

Реализация с помощью посимвольного считывания

Реализация с помощью строк c-string

Решение

Так как предложение задается на неизвестном языке, максимально обобщим определение слова. Будем считать его последовательностью символов, которая удовлетворяет следующим двум условиям:

  • Слева и справа она ограничена пробелами, началом предложения или концом предложения. При этом знаки препинания, стоящие непосредственно после слова или перед ним, также будут считаться его частью, однако на подсчет количества слов это никак не повлияет.
  • Последовательность содержит хотя бы один символ, входящий в алфавит. Такое ограничение отсеет знаки препинания, отбивающиеся с двух сторон пробелами (такие как тире), но при этом позволит учитывать слова, содержащие в себе неалфавитные символы, к примеру, дефис или апостроф.

Теперь перейдем к практическому решению задачи.

Реализация с помощью посимвольного считывания

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

Для решения задачи этим методом воспользуемся функцией bool AllowedSign(char x), возвращающей значение true, если переданный ей символ принадлежит алфавиту неизвестного языка, и объявим логическую переменную wordBegin, определяющую, будет ли следующий считанный символ алфавита началом нового слова, и присвоим ей до начала выполнения цикла посимвольного считывания значение true. Сам цикл будет выполняться до тех пор, пока не будет прочитан весь входной поток:

При этом на каждой его итерации будут возможны, в зависимости от текущего символа и значения переменной wordBegin, следующие два варианта действий. Если считанный символ принадлежит алфавиту и при этом ожидается новое слово ( wordBegin = true), инкрементируем счетчик слов count и присваиваем wordBegin значение false. С этого момента и до тех пор, пока не будет достигнут конец слова, все последующие считываемые символы алфавита не будут влиять на счетчик:

Если же считанный символ — пробел, присваиваем wordBegin значение true. Достигнут конец текущего слова, и теперь следующий алфавитный символ, если он встретится в потоке, приведет к инкрементированию счетчика слов, так как будет принадлежать уже другому слову:

Как видно, неалфавитные символы (знаки препинания) игнорируются и на подсчет слов никак не влияют. Наконец, после того, как будет прочитан весь входной поток, выводится значение счетчика слов count, что и есть ответом на поставленный вопрос задачи:

Реализация с помощью строк c-string

Как и в предыдущем варианте решения, воспользуемся функцией AllowedSign, определяющей принадлежность символа алфавиту, а также объявим переменную bool isWord, отвечающую за то, является ли проверяемая последовательность символов словом неизвестного языка. Тогда суть метода будет заключаться в считывании из входного потока последовательностей символов и проверке того, являются ли они словами. В основе метода лежит цикл, считывающий из входного потока «потенциальные слова» до тех пор, пока это возможно:

После считывания последовательности символов присваиваем переменной isWord значение false, изначально считая, что эта последовательность словом не является:

Затем поочередно проверяем символы последовательности до тех пор, пока isWord сохраняет значение false, или пока не дойдем до конца этой последовательности. Если в процессе проверки окажется, что очередной проверяемый символ принадлежит алфавиту, инкрементируем счетчик слов count и указываем, что последовательность является словом, переходя таким образом к проверке следующего «потенциального слова» в предложении, если таковые имеются:

Наконец, как и в первом случае, выводим количество найденных слов:

Ссылки

Условие задачи на E-Olymp;

Коды программ на Ideone.com: посимвольное считывание, строки c-string;

Подтверждение решения на E-Olymp.

Related Images:

e-olymp 331. Предложение — чемпион

Условие

Задан некоторый абзац текста на неизвестном языке. Назовем предложение чемпионом, если количество палиндромов в нем максимально. Если таких предложение несколько, то чемпионом является то предложение, которое встретилось первым. Буквами алфавита в неизвестном языке являются буквы латинского алфавита и арабские цифры. Гарантируется, что других символов, кроме пробелов и знаков препинания в предложениях нет.

Замечание

В процессе прохождения тестов на сайте e-olymp эмпирически было выяснено, что в случае отсутствия палиндромов во всех предложения, необходимо вывести ноль.

Тесты

Входные данные Номер предложения
No palindrom here. Here it is: abcba! Seriously, I just hate orks… 2
Some random text ahead: AaA o-O-o I. 1 22 333. Result will be 1. 1
Some random text ahead: AaA o-O-o I. 1 22 333 4444. Now result will be 2! 2
Some random text ahead: AaA o-O-o I. 1 — 22 — 333. Result will be 1. 1
No. Palindrom. at. ALL?! 0

Решение

Заведем переменную [latex]currentSentence[/latex], хранящую номер текущего предложения, будем считывать по слову и увеличивать ее значение на 1, если текущее слово заканчивается на точку, восклицательный или вопросительный знак. Далее, поочередно удаляем с конца лишние символы, заменяя их терминальным, пока не встретится первая буква. Затем переводим слово в нижний регистр и проверяем его на палиндромность, если да — увеличиваем на 1 переменную-счетчик кол-ва палиндромов в текущем предложении  [latex]palCount[/latex]. Если слово было последним в предложении (за это отвечает флаг [latex]endOfSentence[/latex]) — сравниваем предложение с предыдущим чемпионом, после обнуляем значение [latex]palCount[/latex].

Код

Ссылки

Рабочий код на Ideaone.

Засчитанное решение на E-olymp.

Related Images:

e-olymp 332. Детская железная дорога

Витэк не прекращает своих игр с кубиками. А тут еще папа подарил ему детскую железную дорогу. Витэк расставляет какое-то количество кубиков по одному на вагончик и перед тем как закончить игру, решает перестроить состав таким образом, чтобы получившееся слово было лексикографически наименьшим из всех возможных, но так как он уже наигрался, поэтому может только один раз отцепить какое-то количество кубиков и паровозиком перевезти их в хвост своего состава.

Какое слово получится у Витэка?

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

Первая и единственная строка содержит исходное слово. Кубики у Витэка только из заглавных букв латинского алфавита и их количество не превышает [latex]500000[/latex].

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

Слово, которое образовал Витэк.

Задача взята с сайта e-olymp.

Тесты

Входные данные Выходные данные
CBABC ABCCB
XXXXX XXXXX
ABEABFABBABC ABBABCABEABF
RATOBCQATOBC ATOBCQATOBCR
OROOXOOSTO OOROOXOOST
 LBDEAFAARDEABBAF AARDEABBAFLBDEAF

Алгоритм

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

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

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

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

Рассмотрим на произвольно выбранном примере:

                                                               LBDEAFAARDEABBAF                                                                                   

Тогда следует сравнить такие подслова:

AFAARDEABBA
     AARDEABBA
        ARDEABBA
                   ABBAF
                           A

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

Реализуем описанный выше алгоритм на практике с некоторыми особенностями.

  1. Прочитаем слово.
  2. Найдем минимальный символ в данном слове.
  3. Создадим вектор для хранения индексов вхождения минимального символа (indicesOfMinSymbol) и будем добавлять в него значение только в том случае, если текущий символ является минимальным, а предыдущий нет. (Обратившись к предоставленному примеру, можно заметить, что не имеет смысла отдельно проводить сравнение подслов AARDEABBAF  и ARDEABBAF, так как первое из них явно «выгоднее». Также мы сможем упростить ситуацию и избавиться от большого количества лишних проверок, когда на вход поступает слово состоящее из всех одинаковых символов (например, XXXXX), в котором не нужно выполнять ни единого сравнения и как-либо изменять слово).
  4. Объявим индекс начала текущего наименьшего лексикографического подслова (indexOfMinLexicSubstr) и для каждого значения из заполненного ранее вектора будем сравнивать от иднекса начала текущего наименьшего лексикографического подслова столько символов, сколько осталось до конца строки от текущего индекса вхождения минимального символа, с подстрокой, начинающейся с этого индекса и заканчивающейся в конце слова, с помощью функции compare. (Рассмотрим произвольные подслова из заданного примера: AFAARDEABBAF  и AARDEABBAF. Тогда исходя из пункта 4 следует сравнить подслова AFААRDEABB и AARDEABBAF. Мы имеем полное право выполнить такое упрощение, так как отсутствие следующего символа меньше, чем наличие любого другого символа, и если будет выбрано первое подслово, то второе подслово, стоящее справа от него, автоматически также будет сдвинуто в начало.
    Однако существует немаловажное исключение при построении такого алгоритма. Его удобно рассмотреть на каком-либо конкретном случае, например, OROOXOOSTO. Когда мы дойдем до сравнения подслов OOSTO (на данный момент будет являться минимальным) и О, исходя из выше описанного алгоритма, мы получим равенство подстрок и не изменим индекс начала минимальной строки, тогда ложно будет построена как наименьшая лексикографическая строка из данной OOSTOOROOX. Исправить эту проблему можно дополнительной проверкой того, что выйдет при сдвиге второй (более короткой) подстроки в начало заданного слова. То есть для данного примера, можно заметить, что подслово OROO лексикографически меньше чем OSTO (сравниваем такое же количество символов в начале строки, сколько оставалось до конца у текущей наименьшей лексикографической подстроки).
    Примечание: следует отметить, что даже без  выполнения второй проверки алгоритм проходил все тесты к данной задаче на сайте e-olymp, что может говорить лишь о неполноте тестов.).
  5. И только в том случае, если функция compare в пункте 4 вернула значение больше чем [latex]0[/latex], то есть правое подслово меньше, или же меньше подслово получаемое при сдвиге правой строки в сравнении с текущим наименьшим лексикографическим, тогда изменяем значение индекса минимального лексикографического подслова на текущий индекс вхождения минимального символа.
  6. После прохождения всего вектора, выполняем сдвиг найденного минимального лексикографического подслова в начало, благодаря встроенной функции rotate, и выполняем вывод полученного слова.

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

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

Засчитанное решение

Related Images:

MLoops2

Задача

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

-*-*-*-*-*-*-*-*-*-*-*-*-
*-*-*-*-*-*-*-*-*-*-*-*-*
-*-*-*-*-*-*-*-*-*-*-*-*-
*-*-*-*-*-*-*-*-*-*-*-*-*
-*-*-*-*-*-*-*-*-*-*-*-*-
*-*-*-*-*-*-*-*-*-*-*-*-*
-*-*-*-*-*-*-*-*-*-*-*-*-
*-*-*-*-*-*-*-*-*-*-*-*-*

Решение

Для того, чтобы решить поставленную задачу, нужно сначала понять закономерность чередования символов — и * в таблице. Каждый символ имеет свой номер строки([latex]m[/latex]) и столбца([latex]n[/latex]), а чтобы определить их номера зададим счетчики [latex]i[/latex] и [latex]j[/latex]. Задача состоит из того, что нужно определить закономерность появления символа [latex]-[/latex], в остальных случаях нужно выводить символ [latex]*[/latex]. Символ [latex]-[/latex] чередуется с символом [latex]*[/latex],  и поэтому можно увидеть, что этот символ [latex]-[/latex] ставится на место, при котором сумма номеров столбцов и строк делится нацело на 2. Решить данную задачу можно с помощью тернарной операции.

Код

Тесты

Входные данные 10 10 8 5 25 8
Выходные данные -*-*-*-*-*
*-*-*-*-*-
-*-*-*-*-*
*-*-*-*-*-
-*-*-*-*-*
*-*-*-*-*-
-*-*-*-*-*
*-*-*-*-*-
-*-*-*-*-*
*-*-*-*-*-
-*-*-*-*
*-*-*-*-
-*-*-*-*
*-*-*-*-
-*-*-*-*
-*-*-*-*-*-*-*-*-*-*-*-*-
*-*-*-*-*-*-*-*-*-*-*-*-*
-*-*-*-*-*-*-*-*-*-*-*-*-
*-*-*-*-*-*-*-*-*-*-*-*-*
-*-*-*-*-*-*-*-*-*-*-*-*-
*-*-*-*-*-*-*-*-*-*-*-*-*
-*-*-*-*-*-*-*-*-*-*-*-*-
*-*-*-*-*-*-*-*-*-*-*-*-*

Задача взята отсюда.

Код программы на ideone.com.

Related Images: