2020-08-05
285
ограничение времени на тест: 2 сек.
ограничение памяти на тест: 32768 KB.
ввод: input.txt
вывод: output.txt
Перестановка P0, P1,..., PN-1 чисел от 0 до N-1 называется антиарифметической, если не существует такой тройки индексов 0 <= i < j < k < N, что тройка Pi, Pj, Pk образует три последовательных члена некоторой арифметической прогрессии. Например, перестановка 3, 1, 0, 4, 2 - антиарифметическая, а 0, 4, 5, 3, 1, 2 - нет (0, 1, 2 - арифметическая прогрессия). Ваша задача по заданному значению N построить любую антиарифметическую перестановку.
Входные данные
Входной файл содержит целое число N (3 <= N <= 50000).
Выходные данные
Выведите любую антиарифметическую перестановку длины N или -1, если такой нет.
Пример
Ввод
5
Вывод
3 1 0 4 2
Минимальный цикл
ограничение времени на тест: 2 сек.
ограничение памяти на тест: 32768 KB.
ввод: input.txt
вывод: output.txt
Задан неориентированный невзвешенный граф. Ваша задача найти длину кратчайшего простого цикла в нем. Цикл называется простым, если все входящие в него вершины различны.
|
|
|
Входные данные
Входной файл состоит из одного или нескольких наборов входных данных. Каждый набор начинается строкой, в которой записана пара целых чисел N, M (1 <= N <= 1000; 0 <= M <= 20000), где N - количество вершин в графе, а M - количество ребер. Далее в M строках перечислены сами ребра парами номеров соединяемых вершин. Вершины занумерованы от 1 до N. Суммы значений N, M по всем наборам в тесте не превосходят 1000 и 50000 соответственно.
Выходные данные
Для каждого набора выведите длину кратчайшего простого цикла в нем на отдельной строке. Если цикла не существует, выведите -1.
Пример
Ввод
Test #1
4 4
1 2
1 3
2 3
3 4
2 1
1 2
Test #2
8 9
1 2
2 3
3 4
5 6
6 7
7 8
1 5
6 2
4 8
Вывод
Test #1
3 -1
Test #2
4
URL Validator
ограничение времени на тест: 2 сек.
ограничение памяти на тест: 32768 KB.
ввод: input.txt
вывод: output.txt
Для идентификации ресурсов в сети Internet используются URL (Uniform Resource Locator). URL состоит из нескольких элементов: протокол, хост, порт, путь и файл. Некоторые элементы URL могут быть опущены. Рассмотрим упрощенный формат URL:
[http://]host[:port][/path][/file]
Заключенные в квадратные скобки элементы могут быть опущены, то есть, например, можно не указать протокол или файл.
Элемент host представляет собой либо IP-адрес -- четыре целых числа без лидирующих нулей от 0 до 255, разделенные точкой (например, 212.193.39.146), либо строковое имя ресурса. Во втором случае имя имеет вид prefix.domain, либо это просто имя компьютера. В первом случае prefix -- это последовательность одного или более слов, разделенных точкой, а domain -- слово из латинских букв длиной 2 или 3 символа. А в случае, если host является просто именем компьютера, то host -- это одно слово.
Элемент port - это целое число от 0 до 65535 без лидирующих нулей.
Элемент path - это последовательность одного или более слов, разделенных символом "/" (код 47).
Элемент file - это нуль или более слов, разделенных символом точка "." (код 46).
Слово - это последовательность из одного или более символов. Если не оговорено специально, то допустимыми символами слова считаются латинские буквы произвольного регистра, цифры и символ подчеркивание (код 95).
|
|
|
Входные данные
Проверьте каждую строку входного файла, является ли она корректным URL (с точки зрения описанных правил). Все строки содержат символы с кодами от 33 до 127 включительно. Длина каждой строки не превосходит 1000 символов. Размер файла не превосходит 500Кб. Количество строк не превосходит 10000. Помните, что любой тест (как и любой корректный тестовый файл) заканчивается парой символов #13#10.
Выходные данные
Выведите YES, если строка является URL, и NO в противном случае.
Пример
Ввод
Test #1
http://acm.sgu.ru/index.html
212.193.39/index.jsp
http://acm.sgu.ru/01/index.php
212.193.39.146/start/index.jsp
Test #2
Yandex.ru
Gmail.com
Abracadabra.start
Вывод
Test #1
YES
NO
YES
YES
Test #2
YES
YES
NO
Доминошки
ограничение времени на тест: 2 сек.
ограничение памяти на тест: 32768 KB.
ввод: input.txt
вывод: output.txt
Вам задан набор разноцветных доминошек. Каждая доминошка состоит из двух половинок, каждая из которых окрашена в некоторый цвет. Перекраска в любой цвет одной половинки любой доминошки занимает одну секунду. Найдите минимальное необходимое время для такой перекраски, после которой все доминошки станут одинаковы. При сравнении доминошки разрешается поворачивать.
Входные данные
Первая строка входного файла содержит положительное целое число N (1 <= N <= 5000) - количество доминошек. В следующих N строках заданы описания доминошек по одному в строке. Каждое описание -- это номера цветов половинок доминошки. Цвета нумеруются от 0 до 9999.
Выходные данные
Выведите наименьшее время, необходимое для перекраски.
Пример
Ввод
Test #1
6
0 0
1 1
0 0
1 2
0 2
1 2
Test #2
2
1 2
2 3
Вывод
Test #1
6
Test #2
1
