Темы --> Информатика
    Язык программирования(952 задач)
    Алгоритмы(1657 задач)
    Структуры данных(279 задач)
    Интерактивные задачи(17 задач)
    Другое(54 задач)
---> 2656 задач <---
Источники
    Личные олимпиады(938 задач)
    Командные олимпиады(684 задач)
Страница: << 335 336 337 338 339 340 341 >> Отображать по:
#3381
Коровники
  

В селе Максоярославке коровы обычно пасутся на лужайках, соединенных дорожками, на каждой лужайке пасется хотя бы одна корова. При этом для каждой пары лужаек есть ровно один способ пройти от одной лужайки до другой. По каждой дорожке можно двигаться в обоих направлениях. Считается, что все дорожки имеют одинаковую длину.
Главный фермер села хочет построить на лужайках \(k\) коровников для своих коров. Ясно, что каждая корова вечером будет возвращаться именно в тот коровник, который ближе к ее лужайке (если расстояние до коровников одинаково, то в любой из них). Поэтому возникает задача определения такого расположения коровников, при котором наибольшее из расстояний, проходимых коровами, было бы минимально.

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

В первой строке входного файла содержатся два числа \(n\) и \(k\) (\(2 \le n \le 50\;000\), \(1 \le k \le n\)) --- количество лужаек и планируемое число коровников, соответственно. Следующие \(n - 1\) строк содержат описания дорожек. Каждая дорожка задается парой целых положительных чисел (\(a, \, b\)), где \(a\) и \(b\) --- номера лужаек, которые соединяет данная дорожка. Лужайки нумеруются с единицы.

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

В первой строке входного файла выведите \(l\) --- максимальное количество дорожек, по которым придется пройти корове, чтобы попасть в коровник. Во второй строке выведите \(k\) различных целых чисел --- номера лужаек, на которых следует построить коровники. Если оптимальных решений несколько, разрешается вывести любое из них.

Примеры
Входные данные
7 2
5 4
4 3
1 3
2 3
4 6
6 7
Выходные данные
2
1 4
#3382
Корень
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
256 megabytes

В этой задаче вам надо найти все корни \(k\)-ой степени из числа \(x\). Единственная проблема - это надо сделать по простому модулю \(p\). Другими словами, найдите все такие числа \(0 < y < p\), что \(y^k ~mod ~p = x\).

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

В единственной строке входного файла записаны \(3\) целых числа - \(p\), \(x\) и \(k\) (\(3 \leq p \leq 10^9\), \(0 < x < p\), \(1 \leq k \leq min(20,p-1)\), \(p\) простое).

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

В первой строке выведите количество различных корней \(m\). Во второй выведите \(m\) различных целых чисел в порядке возрастания - корни из \(x\). Обратите внимание на то, что корней может не быть (в этом случае вторая строка должна остаться пустой).

Примеры
Входные данные
43 25 2
Выходные данные
2
5 38
Входные данные
43 26 2
Выходные данные
0
#3383
Король
  
Быстрое преобразование Фурье

В некотором царстве жил-был король. У него была дочка – принцесса невиданной красоты. И настала пора её замуж отдать. В богатом королевстве неподалеку жил принц. И собрался король отвести принцессу, да не знает, какой маршрут выбрать. На тех землях ещё издревле было множество дорог – горизонтальных и вертикальных, и образовывали они клетчатую сетку на земле той. На перекрёстках располагались города. Город принцессы имеет координаты \((0, 0)\), а принца – \((n, m)\), уравнения дорог имеют вид \(x = x_0\) или \(y = y_0\), где \(x_0\), \(y_0\) целые. Король хочет проехать по как можно меньшему числу дорог, потому что он грабителей боится да вернуться хочет поскорей. Вам, как придворному математику, нужно посчитать, сколькими способами это можно сделать.

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

Во входном файле заданы неотрицательные целые числа \(n\) и \(m\), не превосходящие 400000.

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

Выведите ответ на задачу в десятичной системе счисления без ведущих нулей.

Примеры
Входные данные
7 7
Выходные данные
3432
Входные данные
4 1
Выходные данные
5
#3384
Ситха джедай против
  
#3385
Министерство правды
  
Страница: << 335 336 337 338 339 340 341 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест