Темы --> Информатика --> Алгоритмы
    Задачи на моделирование(78 задач)
    Арифметические алгоритмы(240 задач)
    Алгоритмы поиска(155 задач)
    Алгоритмы сортировки(194 задач)
    Динамическое программирование(355 задач)
    Алгоритмы на графах(319 задач)
    Перебор(154 задач)
    Игры и выигрышные стратегии(33 задач)
    Вычислительная геометрия(216 задач)
    Эвристические методы(30 задач)
    Алгоритмы на строках(45 задач)
    Пересечение множеств(10 задач)
    Жадный алгоритм(71 задач)
    Теория расписаний(5 задач)
    Обработка текста(31 задач)
    Дата и время(14 задач)
---> 405 задач <---
Источники --> Личные олимпиады
    Олимпиады сайта(17 задач)
    Школьная личная олимпиада ФМШ №2007 г. Москвы(7 задач)
    Золотая середина (Новосибирск)(10 задач)
    Нижегородская олимпиада школьников(42 задач)
    Московская олимпиада школьников(168 задач)
    Индивидуальная олимпиада по информатике и программированию (ИОИП)(22 задач)
    Открытая олимпиада школьников(173 задач)
    Украинские олимпиады(61 задач)
    Республиканская олимпиада школьников (Беларусь)(6 задач)
    Жаутыковские олимпиады(8 задач)
    Всероссийская олимпиада школьников(304 задач)
    Международные олимпиады(32 задач)
    Central European Olympiad in Informatics (4 задач)
    Интернет-олимпиады(2 задач)
    COCI(36 задач)
    Турнир Архимеда(36 задач)
    Baltic Olympiad in Informatics(10 задач)
Страница: << 7 8 9 10 11 12 13 >> Отображать по:
#599
Дом оригинальности и гармонии
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

Строительная компания хочет построить дом, в котором будет \(n\) квадратных комнат. Каждая комната характеризуется своим размером — длиной стены. Обозначим размеры комнат в новом доме как \(a_1\), \(a_2\), …, \(a_n\).

При этом для того, чтобы квартиры в доме активнее распродавались, компания объявила его «Домом оригинальности и гармонии». Оригинальность означает, что размер любой комнаты не должен делиться на размер никакой другой комнаты. Свойство гармонии требует, чтобы площадь любой комнаты делилась на размер каждой из комнат. Иначе говоря, для любых различных \(i\) и \(j\) должны выполняться условия: \(a_i\) не делится на \(a_j\), а \(a_i\)2 делится на \(a_j\).

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

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

Входной файл содержит число \(n\) (1 ≤ \(n\) ≤ 1000).

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

Выведите в выходной файл размеры комнат — \(n\) положительных целых чисел, не превосходящих 263 – 1. Разделяйте числа пробелами.

Примеры
Входные данные
2
Выходные данные
6523157998489532400
5519595229491142800
#600
Цепочка слов
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

Будем называть цепочкой слов длины n последовательность слов \(w_1\), \(w_2\), …, \(w_n\), такую, что для всех \(i\) от 1 до \(n\) – 1 слово \(w_i\) является собственным префиксом слова \(w_i\)+1.

Слово \(u\) длины \(k\) называется собственным префиксом слова \(v\) длины \(l\), если \(l\) > \(k\) и первые \(k\) букв слова \(v\) совпадают со словом \(u\). Например, «program» является собственным префиксом слова «programmer».

Задано множество слов \(S\) = {\(s_1\), \(s_2\), …, \(s_m\)} и последовательность чисел \(x\)[1], \(x\)[2], …, \(x\)[\(k\)]. Требуется найти такие числа \(l\) и \(r\) (\(l\) ≤ \(r\)), что \(s_x\)[\(l\)], \(s_x\)[\(l\) + 1], …, \(s_x\)[\(r\) – 1], \(s_x\)[\(r\)] является цепочкой слов, и количество слов в цепочке (число \(r\) – \(l\) + 1) максимально.

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

Первая строка входного файла содержит целое число \(m\) (1 ≤ \(m\) ≤ 250 000). Каждая из следующих \(m\) строк содержит по одному слову из множества \(S\).

Все слова не пусты, имеют длину, не превосходящую 250 000 символов, и состоят только из строчных букв латинского алфавита. Суммарная длина всех слов не превосходит 250 000.

Следующая строка содержит число \(k\) (1 ≤ \(k\) ≤ 250 000). Последняя строка входного файла содержит \(k\) чисел — последовательность чисел \(x\)[1], \(x\)[2], …, \(x\)[\(k\)] (для всех \(i\) выполнено 1 ≤ \(x\)[\(i\)] ≤ \(m\)).

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

Выведите в первой строке выходного файла два числа: \(l\) и \(r\). Если оптимальных ответов несколько, выведите любой из них. Разделяйте числа пробелом.

Примеры
Входные данные
3
zngs
rjzr
zng
3
3 1 1
Выходные данные
1 2
Входные данные
6
gjnuitvaowpy
gjnuitvaowpym
gjnuitvaowp
rjzrociinzeco
tgbotnzepnvm
aigqbzpnerv
9
2 3 1 2 3 1 2 3 1
Выходные данные
2 4
#608
Витрина
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

Зал супермаркета имеет форму прямоугольника размером \(M\) x \(N\), в котором расставлены витрины размером 1 x 1. Стороны витрин параллельны стенам супермаркета, а расстояния от витрин до стен – целые числа.

В супермаркет привезли новую супервитрину размером \(K\) x 1 и выгрузили в одном из углов супермаркета. Требуется передвинуть ее в противоположный угол супермаркета. При этом ее нельзя поворачивать, а можно лишь передвигать параллельно стенам супермаркета. Напишите программу, которая по плану супермаркета поможет определить, какое наименьшее количество витрин нужно убрать, чтобы передвинуть супервитрину.

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

В первой строке вводятся три натуральных числа \(M\), \(N\) и \(K\) (\(M\), \(N\) ≤ 100, \(K\) ≤ \(M\)). Начальное и конечное расположение супервитрины такие, как указано на верхнем рисунке. В следующей строке записано целое неотрицательно число \(V\) – количество витрин (0 ≤ \(V\) ≤ \(N\)*\(M\)). В следующих \(V\) строках входных данных содержатся различные пары целых неотрицательных чисел, характеризующие положения витрин. Первое число (от 0 до \(M\)–1) – расстояние от левой стены супермаркета до витрины, второе (от 0 до \(N\)–1) – расстояние от нижней стены до витрины (см. нижний рисунок). Гарантируется, что там, где изначально поставили супервитрину, других витрин нет.

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

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

U – на 1 вверх,
D – на 1 вниз,
L – на 1 влево,
R – на 1 вправо.
Количество символов в строке не должно превышать \(N\) x \(M\).

Если возможных маршрутов несколько, то выведите любой из них.

Примеры
Входные данные
10 10 5
0
Выходные данные
0
RUURUURUURUURU
Входные данные
9 3 2
4
2 0
5 1
5 2
8 2
Выходные данные
1
URRRDRRRRUU
#610
Ломаные
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

На окружности отметили \(N\) точек и пронумеровали их последовательно числами от 1 до \(N\). Требуется найти количество различных простых ломаных с вершинами в некоторых из отмеченных точек и с концами в точках с номерами \(i\) и \(j\).

Ломаная называется простой, если она не проходит дважды через одну точку (и не содержит самокасаний и самопересечений).

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

Вводятся три натуральных числа \(N\), \(i\), \(j\) (2 ≤ \(N\) ≤ 2 000, 1 ≤ \(i\) < \(j\) ≤ \(N\)).

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

Требуется вывести остаток от деления количества ломаных на \(10^9\).

Примеры
Входные данные
4 1 3
Выходные данные
5
Входные данные
5 1 4
Выходные данные
12
#712
Сортировка таблицы
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes
Задан порядок применения сортировок по столбцам в электронной таблице. Требуется минимизировать количество применений сортировки, чтобы окончательный результат не изменился.

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

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

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

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

В первой строке вводится одно число N – количество сортировок, которые сделал Вася (1 ≤ N ≤ 106).  Во второй строке содержатся N натуральных чисел, не превосходящих 105 – номера столбцов, по которым осуществлялась сортировка, в том порядке, в котором Вася это делал. Среди чисел могут быть равные.

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

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

Примеры
Входные данные
3
2 1 2
Выходные данные
2
1 2
Входные данные
4
1 1 1 1
Выходные данные
1
1
Страница: << 7 8 9 10 11 12 13 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест