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

Задача

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

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

Сколько всего разных слов может быть в таком необычном «английском» словаре Витэка?

Тесты

Входные данные
Выходные данные
ALPHABET 35
AAAA 4
UNIVERSITY

54
ABABABABC

24

Код

Решение

Казалось бы, задачу можно решить простым циклом. Ведь в 6-буквенном слове: 6 однобуквенных слов, 5 двубуквенных и т.д. Однако очевидной становится проблема повторения,причем не только повторений букв, но и повторений подстрок, что изрядно усложняет наше решение. Создадим вектор, состоящий из строк, куда мы будем добавлять все подстроки строки из входного потока. Отсортируем полученный вектор. Это нужно для того чтобы одинаковые элементы шли рядом с друг другом. Тогда мы можем использовать функцию unique(), которая удалит из вектора все повторяющиеся элементы, кроме одного. Для того, чтобы провести resize() вектора нам понадобится итератор, который мы приравняем к функции unique(). После resize() останется только вывести размер вектора и прибавить к нему единицу, так как само слово не является подстрокой.

Ссылки

1.Код на ideone

2.Условие на e-olymp

Chuck Norris

A task from codingame.com

Task

Binary with 0 and 1 is good, but binary with only 0, or almost, is even better! Originally, this is a concept designed by Chuck Norris to send so called unary messages.

Write a program that takes an incoming message as input and displays as output the message encoded using Chuck Norris’ method.

Here is the encoding principle:

  • The input message consists of ASCII characters (7-bit)
  • The encoded output message consists of blocks of 0
  • A block is separated from another block by a space
  • Two consecutive blocks are used to produce a series of same value bits (only 1 or 0 values):
    — First block: it is always 0 or 00. If it is 0, then the series contains 1, if not, it contains 0
    — Second block: the number of 0 in this block is the number of bits in the series

Input

Line 1: the message consisting of N ASCII characters (without carriage return)

Output

The encoded message

Tests

Input
Output
C 0 0 00 0000 0 00
CC 0 0 00 0000 0 000 00 0000 0 00
%

00 0 0 0 00 00 0 0 00 0 0 0
Hello

0 0 00 00 0 0 00 000 0 00 00 00 0 0 00 0 0 000 00 0 0 00 00 00 0 00 00 0 0 00 00 00 0 00 00 0 0 0000

Code

Solution

First, we create a so called mask, which takes the symbol, transform it to a binary 7-bit number and return string. Then we add this string to another one, while transforming every symbol in the cin.  Then we create a loop, where we check either symbol is 0 or 1 and add them to another string in the right order according to the encoding principle. In order to escape mistakes with ‘1’ in the first loop, we create another loop, where we change all ‘1’ to ‘0’.

 

А282(а)

Задача

Даны действительные числа [latex]a_1,a_2, …,a_{2n}[/latex]. Получить:
[latex]a_1,a_{n+1},a_2,a_{n+2}, …,a_n,a_{2n}[/latex]

Тесты

Ввод
Вывод
1 2 3 4 5 6 7 8 9 10 1 6 2 7 3 8 4 9 5 10
8 25 3 7 8 3 25 7
5.5 6.025 2.387 1.0986 7.762 3.5958

5.5 1.0986 6.025 7.762 2.387 3.5958

Хороший код

Решение

Считываем действительные числа в первый вектор и узнаем [latex]n[/latex]. Затем поочередно вписываем элементы и элементы с измененным индексом в другой вектор, пока счетчик не будет равен [latex]n[/latex] и выводим полученный вектор, он и будет ответом.

Лучший код

 

Решение

В первом способе мы задавали два вектора, чем естественно увеличивали занимаемую память. C помощью функции insert() мы можем вставлять элементы в вектор, не используя дополнительных средств. Однако мы сталкиваемся с тем, что функция по определению вставляет в вектор константу из-за чего наш цикл не будет правильно работать. Чтобы изменять параметр вводимого элемента, заводим отдельный счетчик. Теперь каждый [latex]2*i+1[/latex]-ый шаг мы вставляем [latex]n+b+i[/latex]-ый элемент вектора. Проведем resize() вектора чтобы убрать лишние элементы и получим готовый результат.

Ссылки

  1. Хорошее решение на ideone
  2. Лучшее решение на ideone
  3. Условие в задачнике Абрамова(стр.120)

Монстр

Задача 787A с сайта codeforces.com.

Задача

Монстр гонится за Риком и Морти на другой планете. Они настолько напуганы, что иногда кричат. Точнее, Рик кричит в моменты времени b, b + a, b + 2a, b + 3a, …, а Морти кричит в моменты времени d, d + c, d + 2c, d + 3c, ….

Монстр поймает их, если в какой-то момент времени они закричат одновременно. Так что он хочет знать, когда он поймает их (первый момент времени, когда они закричат одновременно) или они никогда не закричат одновременно.

Ввод

Первая строка входных данных содержит два целых числа a и b (1 ≤ a, b ≤ 100).

Вторая строка входных данных содержит два целых числа c и d (1 ≤ c, d ≤ 100).

Вывод

Выведите первый момент времени, когда Рик и Морти закричат одновременно, или  - 1, если они никогда не закричат одновременно.

Тесты

Ввод
Вывод
20 2
9 19
82
2 1
16 12
-1

Код

Решение

В этих моментах времени, заданных прогрессиями, изменяется только коэффициент при и c. Создадим для них 2 цикла. Так как равных моментов времени может быть много, а нам нужен только первый, создаем вектор и ,когда моменты равны, добавляем в него этот момент. Затем, уже вне цикла, проверяем пустой ли вектор, и в таком случаем выводим -1, так как моменты на данном промежутке не были равны ни разу. Если же вектор непустой, выходим первый элемент вектора. Он и будет искомым первым одновременным криком.

Душевая кабина

Разбор задачи F с 1/8 ACM ICPC по украинскому региону 25 марта 2017.

Задача

Степан приобрел душевую кабину, которую решил установить в дачном домике. Дачный домик представляет собой прямоугольник [latex]N \times M[/latex], разбитый на одинарные квадратики. Степан знает, что душевая кабина занимает ровно две клетки с общей стороной. Также Степану известно, что некоторые клетки дома заняты разными вещами. Помогите Степану узнать сколькими способами он может разместить душевую кабину в дачном домике.

 

Ввод

В первом ряду входных данных находятся два целых числа  [latex] N,M(1<=N,M<=1000)[/latex] — размеры дачного домика Степана. Каждый из следующих [latex] N[/latex] рядов содержит по  [latex] M[/latex] символов — описание дачного домика Степана. Символ «#» означает, что соответствующая клетка уже чем-то занята, а символ «.» — что она свободна и может стать одной из двух, занятых душевой кабиной.

Вывод

Одно число — количество способов расположить душевую кабину в дачном домике.

Тесты

Код

Решение

Считываем символы в массив . Размер такого массива всегда будет [latex]n \times m[/latex]. Зная это, заводим цикл, в котором проверяем наличие точки(‘.’). Затем проверяем первое условие: если следующий символ тоже точка и если мы не перешли на новую строку, увеличиваем счетчик. Зная количество символов в каждой строке, проверяем символ «под» точкой и если они совпадают опять же увеличиваем счетчик.

MS1.Количество чисел в потоке

Задание

Сосчитайте количество чисел во входном потоке.

Тесты

Вход Выход
20 16 11 3
17 22.4 41.9 74.5 4
122 347 1567 21 40 5
13 28 17 8 2 5

Код на C++

Код на Java

 

Решение

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