Страница: << 1 2 3 4 5 6 7 >> Отображать по:

#2899

Вычеркивание двух

Темы: [Комбинаторика]

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

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

Входной файл содержит строку S, записанную в первой и единственной строке файла. Длина строки S от 2 до 100000 символов включительно. Строка S содержит только маленькие буквы латинского алфавита.

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

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

Примеры

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

abbccc

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

#111405

Ацтекская пирамида

Темы: [Формула]

Император ацтеков Куитлауак собирается построить пирамиду в свою честь. Эта пирамида должна быть выше, чем все предыдущие.

Ацтекская пирамида состоит из каменных блоков. Каждый блок это куб размерами 1 × 1 × 1. Куитлауак располагает первый блок на земле в процессе церемонии закладки пирамиды. Каждый следующий блок должен иметь общую грань с каким-нибудь из предыдущих блоков.

Правильные расположения блоков: $\text{[math]}$ $\text{[math]}$ Неправильные расположения блоков: $\text{[math]}$ $\text{[math]}$ $\text{[math]}$

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

Устойчивые блоки: $\text{[math]}$ $\text{[math]}$ $\text{[math]}$ Неустойчивые блоки: $\text{[math]}$ $\text{[math]}$

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

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

Единственная строка входного файла содержит одно целое число n — количество имеющихся в наличии блоков, считая заложенный императором (1 ≤ n ≤ 10⁹).

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

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

Примеры тестов

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

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

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

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

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

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

#111406

Морской бой

Темы: [Двумерные массивы] [Конструктив]

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

Тест основан на игре «Морской бой». Эта игра проводится на клетчатом поле размером 10 × 10 клеток. Перед началом игры вы должны разместить десять кораблей на этом поле. Каждый корабль задается числом последовательных клеток, расположенных горизонтально или вертикально. Вы должны разместить один четырехклеточный корабль, два трехклеточных, три двухклеточных и четыре одноклеточных корабля. Никакие два корабля не могут иметь общую или соседние по стороне или углу клетки.

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

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

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

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

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

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

Выведите какое-нибудь оптимальное расположение кораблей для данного порядка стрельбы. Пустые клетки должны быть обозначены точкой ('.'), занятые клетки должны быть обозначены решёткой ('#').

Примеры тестов

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

1 2 3 4 5 6 7 8 9 10
36 37 38 39 40 41 42 43 44 11
35 64 65 66 67 68 69 70 45 12
34 63 84 85 86 87 88 71 46 13
33 62 83 96 97 98 89 72 47 14
32 61 82 95 100 99 90 73 48 15
31 60 81 94 93 92 91 74 49 16
30 59 80 79 78 77 76 75 50 17
29 58 57 56 55 54 53 52 51 18
28 27 26 25 24 23 22 21 20 19

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

...####...
..........
#....##...
#.#.....#.
........#.
...###....
.#........
........#.
..#.....#.
.....#..#.

#111410

Результаты гонки

Темы: [Разбор случаев]

Формула TheByte это самое известное гоночное соревнование в Байтландии. Соревнование уже завершено и каждый из n гонщиков заработал какое-то целое неотрицательное количество очков. Гонщик, у которого больше очков, займет более высокое место.

Окончательные результаты еще не объявлены, но уже известно, что сумма все зарабонных гонщиками очков равна p, и среди лучших k гонщиков есть только d различных результатов.

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

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

Единственная строка входного файла содержит четыре целых числа: n — количество гонщиков, p — суммарное количество очков, k и d — количество различных результатов среди k лучших гонщиков (1 ≤ k ≤ n ≤ 1000; 0 ≤ p ≤ 1 000 000; 1 ≤ d ≤ k).

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

Выведите возможные результаты, которые соответствуют данным n, p, k и d.

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

Если не существует возможных результатов, удовлетворяющих данной информации, выведите одну строку "Wrong information".

Примеры тестов

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

3 4 2 2

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

2
1
1

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

3 5 2 2

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

3
2
0

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

2 5 2 1

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

Wrong information

Решения, работающие в случае, если P не превосходит 2000, будут набирать не менее 30 баллов.

#111411

Сетка

Темы: [Конструктив] [Разбор случаев] [Элементарная геометрия]

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

Пока Геральд отдыхал от трудов, его брат Майк пришел и нарисовал прямую линию на листе бумаги. Геральд разозлился и приказал Майку стереть все лишнее с бумаги.

$\text{[math]}$

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

Помогите Геральду восстановить параметры исходной сетки.

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

Первая строка входного файла содержит одно целое число n — количество точек пересечения (3 ≤ n ≤ 100 000).

Каждая из следующих n строк содержит два целых числа x_i, y_i — координаты одной из точек пересечения. Координаты не превосходят 10⁹ по абсолютной величине.

Все точки пересечения различны. Других общих точек, кроме описанных выше, у сетки и прямой Майка нет.

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

Выведите шесть целых чисел x₁, x₂, d_x, y₁, y₂ и d_y. Первые три числа описывают набор вертикальных прямых: минимальная x-координата вертикальной прямой, максимальная x-координата вертикальной прямой и расстояние между соседними вертикальными линиями ( - 10⁹ ≤ x₁ ≤ x₂ ≤ 10⁹; 0 < d_x ≤ 2·10⁹). Следующие три числа аналогично описывают набор горизонтальных линий ( - 10⁹ ≤ y₁ ≤ y₂ ≤ 10⁹; 0 < d_y ≤ 2·10⁹).

Гарантируется, что хотя бы одно решение существует.

Примеры тестов

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

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

1 9 4 2 5 3

Страница: << 1 2 3 4 5 6 7 >> Отображать по:

Выбрано

Отменить

Добавить в контест