Темы --> Информатика
    Язык программирования(952 задач)
    Алгоритмы(1657 задач)
    Структуры данных(279 задач)
    Интерактивные задачи(17 задач)
    Другое(54 задач)
---> 2656 задач <---
Источники
    Личные олимпиады(938 задач)
    Командные олимпиады(684 задач)
Страница: << 108 109 110 111 112 113 114 >> Отображать по:
#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
#601
Забор
  
Темы: [Формула]
ограничение по времени на тест
0.5 second;
ограничение по памяти на тест
64 megabytes

Том Сойер получил важное задание по покраске забора. Забор состоит из n досок. Он когда-то был покрашен, однако с некоторых участков забора краска облупилась. Эти доски Тому и необходимо покрасить. Так как забор большой, пришлось подвезти к забору целую цистерну с краской. Цистерна была помещена у края забора и не может перемещаться. У Тома есть ведерко, набрав краски в которое, Том может покрасить \(k\) досок забора. При этом Том может в любой момент вернуться за краской к цистерне.

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

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

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

Первая строка входного файла содержит количество досок в заборе \(n\) (1 ≤ \(n\) ≤ \(10^9\)) и вместимость ведерка \(k\) (1 ≤ \(k\) ≤ 100). Во второй строке содержится количество неокрашенных отрезков забора \(m\) (1 ≤ \(m\) ≤ 50). Далее следуют \(m\) строк, в каждой из которых описан один неокрашенный отрезок. Отрезок описывается своей левой границей \(l_i\) и правой границей \(r_i\) (1 ≤ \(l_i\) ≤ \(r_i\) ≤ \(n\)). Такое описание означает, что не покрашены \(l_i\)-я, (\(l_i\)+1)-я, …, (\(r_i\)–1)-я, \(r_i\)-я доски забора (доски нумеруются от 1 до \(n\)). Гарантируется, что неокрашенные отрезки, заданные во входном файле, не пересекаются.

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

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

Примеры
Входные данные
5 2
2
1 2
5 5
Выходные данные
12
#604
Дополнение - 1
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

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

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

В первой строке входных данных содержится одно целое число \(N\) (1 ≤ \(N\) ≤ 50) – количество вершин в исходном графе. Далее в \(N\) строках записано по \(N\) положительных целых чисел в каждой ( \(j\) -е число в \(i\) -й строке соответствует стоимости добавления ребра, соединяющего вершины \(i\) и \(j\) ), числа не превышают 100. В следующих \(N\) строках записаны по \(N\) чисел, каждое из которых является единицей или нулем (1, если вершины соединены, и 0, если не соединены). Обе матрицы симметричны.

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

Вывести единственное число – минимально возможную стоимость дополнения данного графа до связного.

Примеры
Входные данные
3
0 1 20
1 0 10
20 10 0
0 1 0
1 0 0
0 0 0
Выходные данные
10
#605
Связанное множество
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

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

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

В первой строке входных данных содержится одно целое число \(N\) (1 ≤ \(N\) ≤ 50) – количество точек. Далее в \(N\) строках записано по 2 натуральных числа – координаты точек (координаты не превышают 100). Все точки различны. Далее дано число \(M\) – количество уже существующих отрезков. В следующих \(M\) строках записаны по 2 числа – номера начала и конца соответствующего отрезка.

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

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

Примеры
Входные данные
3
1 1
1 2
10 1
1
2 1
Выходные данные
9.0
Страница: << 108 109 110 111 112 113 114 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест