e-olymp 1453. Форд-Беллман

Условие

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

Сначала записано количество вершин графа [latex]n[/latex] ([latex]1 \leq n \leq 100[/latex]), за которым идет количество ребер [latex]m[/latex] ([latex]1 \leq m \leq 10000[/latex]) Следующие [latex]m[/latex] троек чисел описывают ребра: начало ребра, конец ребра и его вес (вес — целое число от [latex]-100[/latex] до [latex]100[/latex]).

Выведите [latex]n[/latex] чисел — расстояния от вершины номер [latex]1[/latex] до всех вершин графа. Если пути до соответствующей вершины не существует, вместо длины пути выведите число [latex]30000[/latex].

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

Входные данные Выходные данные
1 4 5
1 2 10
2 3 10
1 3 100
3 1 -10
2 3 1
0 10 11 30000

Код

Решение

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

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

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

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

Ссылки

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

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

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

A297

Условие

Даны целые числа [latex]a_1, \ldots , a_{100}[/latex]. Получить новую последовательность из 100 целых чисел, заменяя [latex]a_i[/latex] нулями, если [latex]|a_i|[/latex] не равно [latex]\text{max} (a_1, \ldots , a_{100})[/latex], и заменяя [latex]a_i[/latex] единицей в противном случае ([latex]i = 1, \ldots , 100[/latex]).

Ниже приведено решение для общего случая, когда количество чисел произвольно.

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

Входные данные Выходные данные
1 0 1
2 1 0 -1 1 0 1
3 -1 0 -1 0 1 0
4 -1 -1 -1 0 0 0
5 4 4 4 4 1 1 1 1
6 10 5 -1 -10 -20 0 1 2 3 1 0 0 1 0 0 0 0 0

Код

Решение

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

Так как последовательность состоит из целых чисел и ее длина неизвестна, воспользуемся классом vector типа int:

Затем отдельно считаем первый элемент последовательности и возьмем его в качестве максимума, после чего поместим в вектор:

Заполним вектор оставшимися числами, попутно обновляя переменную max , если встретим число, большее хранимого максимума:

Теперь обработаем последовательность согласно условию задачи, то есть заменим каждое число либо нулем, если его абсолютное значение не равно максимуму, либо единицей в противном случае:

Наконец, выведем ответ на задачу — полученную последовательность из нулей и единиц:

Ссылки

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

Условие задачи в сборнике задач по программированию (С. А. Абрамов).

AL13

Условие

Имеется [latex]n[/latex] черных и белых карточек, сложенных в стопку. Карточки раскладываются на стол в одну линию следующим образом: первая кладется на стол, вторая — под низ стопки, третья — на стол, четвертая — под низ стопки и т.д., пока все карточки не будут выложены на стол. Каким должно быть исходное расположение карточек в стопке, чтобы разложенные на столе карточки чередовались по цвету: белая, черная, белая, черная и т.д.?

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

Входные данные Выходные данные
1 1 1
2 2 01
3 5 10011
4 12 101100010011
5 20 00111001101100010011

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

Код

Решение

Алгоритм разбора стопки можно описать следующим образом:

  1. Выкладываем на стол верхнюю карточку.
  2. Пока в стопке есть карты, выполняем действия:
    1. перекладываем под низ стопки верхнюю карточку;
    2. выкладываем на стол верхнюю карточку.

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

  1. Пока на столе не останется одна карточка, выполняем действия:
    1. добавляем карточку, выложенную на стол последней из имеющихся, на верх стопки;
    2. перекладываем карточку из-под стопки наверх.
  2. Добавляем карточку наверх.

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

Для решения задачи удобнее всего будет воспользоваться очередью, поскольку при построении стопки мы добавляем карточки только в один ее конец, а изымаем при перекладывании всегда из противоположного. Более того, в данном случае структуру можно значительно облегчить, оставив из методов только push() и pop(), причем из последнего можно за ненадобностью удалить проверку исключительной ситуации при попытке изъять карточку из пустой стопки, так как по алгоритму прямо перед изъятием всегда выполняется добавление карточки. Карточки могут быть только двух цветов, поэтому узлы очереди будут хранить значения типа bool.

Перейдем к практическому решению. Прежде всего получим количество карточек в требуемой стопке и объявим очередь:

Затем объявим переменную для цвета текущей карточки и инициализируем ее таким образом, чтобы последняя добавляемая карточка была белой. Так как при четном числе карточек в стопке последняя выкладываемая (она же — первая добавляемая) будет черной, а при нечетном — белой, то при кодировании черных и белых цветов как [latex]0[/latex] и [latex]1[/latex] соответственно инициализируется она следующим значением:

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

Наконец, разбираем стопку, начиная с условного низа, и выводим ее как ответ на поставленную задачу:

Ссылки

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

Список задач по структурам данных на Algolist.manual.ru.

e-olymp 2820. Перемещение коня

Условие

Ваш друг проводит научные исследования по проблеме Конского Минимального Путешествия (КМП), которая состоит в том, чтобы найти кратчайший замкнутый тур ходов конём, который посещает каждую клетку заданного набора из [latex]n[/latex] клеток на шахматной доске ровно один раз. Он считает, что самая трудная часть задачи состоит в определении наименьшего числа ходов для перемещения коня между двумя заданными клетками и что, как только вы поможете ему решить эту подзадачу, то ему решить всю задачу будет намного легче. Вы, конечно, знаете, что дело обстоит как раз наоборот. Таким образом, вы в свою очередь решили предложить ему самому написать программу, которая решает «трудную» часть.

Ваша задача состоит в том, чтобы написать программу, которая принимает координаты двух клеток [latex]a[/latex] и [latex]b[/latex] в качестве входных данных, а затем определяет количество ходов конем кратчайшим путём из [latex]a[/latex] в [latex]b[/latex].

Входные данные будут содержать один или более тестов. Каждый тест состоит из одной строки, содержащей координаты двух клеток, разделенные одним пробелом. Координаты клетки являются двумя символами, первый из которых буква ([latex]\text{a}[/latex]–[latex]\text{h}[/latex]), задающая столбец и второй – цифра ([latex]1[/latex]–[latex]8[/latex]), задающая строку на шахматной доске.

Для каждого теста вывести одну строку следующего содержания: «To get from [latex]\text{xx}[/latex] to [latex]\text{yy}[/latex] takes [latex]n[/latex] knight moves.»

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

Входные данные Выходные данные
1 1 -1
2 0.25 -0.75
3 0.1 -0.861111
4 0.01 -0.827962
5 0.0000001 -0.822467

Код

Решение

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

Прежде всего найдем зависимость [latex]a_{n+1}[/latex] от [latex]a_n[/latex] и выведем рекуррентную формулу для очередного члена:

[latex]a_{n+1} = a_n \cdot \frac {a_{n+1}}{a_n} = a_n \cdot \frac {\frac {(-1)^{i+1}}{(i+1)^2}}{\frac {(-1)^i}{i^2}} = a_n \cdot -(\frac {i}{i+1})^2[/latex]

Для вычислений мы используем рекуррентное соотношение, поэтому до выполнения цикла, накапливающего сумму, переменным члена ряда a и суммы sum потребуется присвоить значение [latex]a_1 = \frac {(-1)^1}{1^2} = -1[/latex]:

Теперь опишем, каким образом будет работать цикл:

  • Цикл будет начинаться со счетчиком [latex]i = 1[/latex], который будет инкрементироваться в конце каждой итерации.
  • Цикл будет выполняться до тех пор, пока абсолютное значение очередного члена ряда [latex]a_i[/latex] будет не меньше, чем заданная точность [latex]\varepsilon[/latex].
  • В каждой итерации цикла значение суммы будет увеличиваться на [latex]a_i[/latex].

Реализуем описанный алгоритм с помощью цикла for. Чтобы сократить количество операций в теле цикла до одной, вычислять очередной член ряда будем при проверке выполнения условия продолжения. При присвоении переменной a нового значения воспользуемся кастингом (double) ; в противном случае уже второй член ряда будет обнуляться из-за умножения на дробь с целой частью [latex]0[/latex]:

Наконец, выведем требуемое значение — сумму ряда:

Ссылки

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

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

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

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.

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.