Алгоритмы

2 310 задачвместе с подтемами
Число у задачи — рейтинг сложности, слово рядом — насколько она трудна по сравнению с другими задачами такого же типа. Шкалы задач с ответом и задач с кодом между собой не сравниваются. Рядом — счётчики попыток: ✓ успешные, ✗ неуспешные.
РейтингЛюбойдо 800800–11991200–15991600+Без рейтинга
СначалаПодходящиеНовыеПопулярныеПростыеСложные
Квадраты и кубы#33122
В лаборатории теории чисел одного университета изучают связь между
распределением квадратов и кубов натуральных чисел.
Пусть задано целое неотрицательное число k. Рассмотрим множество натуральных
чисел от a до b, включительно. Будем называть k-плотностью этого множества количество
пар натуральных чисел x и y, таких, что a ≤ x2 ≤ b, a ≤ y3 ≤ b, причем |x2– y3| ≤ k.
Например, 2-плотность множества натуральных чисел от 1 до 30 равна 3, так как
подходят следующие пары:

 x = 1, y = 1, |x2– y3| = |1 – 1| = 0;
 x = 3, y = 2, |x2– y3| = |9 – 8| = 1;
 x = 5, y = 3, |x2– y3| = |25 – 27| = 2.
 
Требуется написать программу, которая по заданным натуральным числам a и b, а
также целому неотрицательному числу k, определяет k-плотность множества натуральных
чисел от a до b, включительно.
Формат входных данных
Входные данные содержат три строки. Первая строка содержит натуральное число a,
вторая строка содержит натуральное число b, третья строка содержит целое неотрицательное
число k (1 ≤ a ≤ b ≤ 1018, 0 ≤ k ≤ 1018).
Формат выходных данных
Выходные данные должны содержать одно целое число: искомую k-плотность
множества натуральных чисел от a до b, включительно.
 
Ввод Вывод
1
30
2		 3
Арифметические алгоритмы (Теория чисел)Вещественные числаЛинейный поиск
✓ 6✗ 751 100средняяВойти и решать
вес Деда Мороза#33112
Дед Мороз очень любит раздавать «подарочки» и если он долго их не раздаёт, то начинает грустить и поедать печеньки (не факт, что печеньки не олени). И он начинает толстеть, но когда он дарит хотя бы один подарочек, то возвращается к начальному весу (Т-Т ©Маша). На какой максимальный вес потолстеет Дед Мороз, если на одном отрезке он дарит по 1 подарку на каждый целый индекс, а всего он обойдёт m домов. Даны n отрезков пути для Деда Мороза на его траектории раздачи подарочков и сами отрезки. Также дано количество домов, которое он обойдёт.
Изначальный вес Деда Мороза 227 ± 1 кг.

Ввод Вывод
3 12
2 6
3 9
3 4
 3
(с) Манаев В., Кашукова М., 2018 г.
Задачи на моделированиеОтрезки
✓ 0✗ 21 200средняяВойти и решать
Сложность двоичного поиска#33009
Вася загадал число от 1 до N. За какое наименьшее количество вопросов (на которые Вася отвечает "да" или "нет") Петя может угадать Васино число?
 
Входные данные
Вводится одно число N
 
Выходные данные
Выведите наименьшее количество вопросов, которого гарантированно хватит Пете, чтобы угадать Васино число.
 
Ввод Вывод
5 3
Бинарный поискБинарный поиск в массиве
✓ 369✗ 547400лёгкаяВойти и решать
Лифт в бизнес-центре#32974
Рабочий день закончился, и сотрудники бизнес-центра собрались по домам. Бизнесцентр представляет собой N-этажное здание, этажи пронумерованы от 1 до N снизу вверх. Все сотрудники хотят спуститься на парковку, которая расположена в подвальном помещении на один этаж ниже первого. Бизнес-центр оборудован лифтом, который может перевозить не более K человек одновременно. Лифт перемещается вверх или вниз на один этаж за одну секунду, посадка и высадка пассажиров происходят мгновенно. Изначально лифт расположен на уровне парковки. Известно, сколько людей хотят спуститься на парковку с каждого
из N этажей. Определите, какое минимальное время потребуется, чтобы перевезти на парковку всех сотрудников бизнес-центра.
 
Первая строка входных данных содержит наибольшее возможное число людей в лифте K, 1 ≤ K ≤ 109
Вторая строка содержит число этажей в бизнес-центре N, 1 ≤ N ≤ 105
 
Следующие N строк содержат целые неотрицательные числа – число людей, ожидающих лифт на 1, 2, … , N-м этаже соответственно, эти числа не превосходят 109  каждое. В здании находится хотя бы один человек. 

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

Ввод Вывод Примечание
2
3
3
0
1		 8 Лифт перевозит 2 человек, в здании 3 этажа. Лифт поднимается на первый этаж за 1 с, забирает 2 человек и за 1 с спускается на парковку, затем лифт поднимается на первый этаж, забирает 1 человека, вместе с ним поднимается на третий этаж, забирает 1 человека и спускается на парковку. Подъём на третий этаж занимает 3 с, спуск – ещё 3 с.

Жадный алгоритмЗадачи на моделированиереализация
✓ 36✗ 1731 000средняяВойти и решать
Лучшее место#32967
В зале ожидания на вокзале стоят N рядов из M кресел. Чтобы ожидающие не скучали, вместо некоторых кресел установлено K мощных Wi-Fi роутеров. Ожидающие стараются занять места ближе к роутерам, так как тогда они смогут смотреть ролики с Youtube или VK с более высоким разрешением, без задержек. Если пассажир сидит на месте с номером c в ряде r, а i-й роутер расположен на месте Ci в ряде Ri, то расстояние до i-го роутера вычисляется как max(|r−Ri|,|c−Ci|), где |x| – абсолютное значение x. Креслам в зале ожидания был присвоен приоритет от 1 до N⋅M−K, меньшие номера получили кресла с меньшим расстоянием до ближайшего роутера, среди кресел с одинаковым расстоянием до роутеров более удобными считаются кресла, стоящие в ряду с меньшим номером, а среди них — с меньшим номером места в ряду. На рисунке показан приоритет кресел в зале ожидания с 4 рядами из 7 кресел, в котором установлены 2 роутера (их позиции помечены черным цветом). Темно-серым цветом выделены кресла, стоящие на расстоянии 1 от роутеров, светло-серым — на расстоянии 2, белым — 3.
 

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

Первая строка ввода содержит четыре целых чисел — количество рядов N (2 ≤ N ≤ 109) и мест в ряду M (2 ≤ M ≤ 109), количество роутеров K (1 ≤ K ≤ 100, K < N⋅M), количество запросов Q (1 ≤ Q ≤ 100). Далее следует K строк, содержащих два целых числа — местонахождение роутеров: номер ряда Ri (1 ≤ Ri ≤ N) и номер места в ряду Ci (1 ≤ Сi ≤ M). Среди них нет совпадающих. Далее следует строка, содержащая Q целых чисел в диапазоне от 1 до N⋅M−K – приоритеты кресел.

Вывести для каждого запроса на отдельной строке одно целое число — расстояние до ближайшего роутера от кресла с заданным приоритетом.
 
Ввод Вывод
4 7 2 4
2 5
4 4
1 6 16 26
1
1
2
3
Бинарный поискСканирующая прямая
✓ 1✗ 131 300средняяВойти и решать
RSA: Расшифровка#31923
Даны два простых числа p и q. Надо расшифровать сообщение состоящее из последовательности чисел, оканчивающееся нулем, с помощью алгоритма RSA.

Входные данные
В первой строке вводятся p и q (\(3<=p,q<10\)), далее вводится сообщение состоящее из натуральных чисел, каждое не превышающее 100. Сообщение заканчивается нулем.

Выходные данные
Выведите расшифрованное сообщение.
 

 

Примеры
№ Входные данные Выходные данные
1 3 7
1 11 12 0		 123
Быстрое возведение в степеньМЦКО-10. RSAРасширенный алгоритм Евклида
✓ 6✗ 351 200средняяВойти и решать
RSA. Расшифровать небольшое сообщение.#31918
Даны два простых числа p и q. Надо расшифровать сообщение длинной N с помощью алгоритма RSA.

Входные данные
В первой строке вводятся p и q (3<=p,q<10), далее вводится длина N (N<10) и сообщение состоящее из натральных чисел не превышающее 10.

Ввод Вывод
3 7
3
1 11 12		 1 2 3

Быстрое возведение в степеньМЦКО-10. RSAОстатки
✓ 0✗ 381 400средняяВойти и решать
RSA. Зашифровать небольшое сообщение.#31917
Даны два простых числа p и q. Надо зашифровать сообщение длинной N с помощью алгоритма RSA.

Входные данные
В первой строке вводятся p и q (3<=p,q<10), далее вводится длина N (N<10) и сообщение состоящее из натральных чисел не превышающее 10.

Ввод Вывод
3 7
3
1 2 3		 1 11 12

Быстрое возведение в степеньМЦКО-10. RSAОстатки
✓ 18✗ 46800средняяВойти и решать
Несократимые дроби#31849
Дробь \({m \over n}\) называется правильной несократимой, если \(0 < m < n\) и \(НОД (m, n) = 1\). Найдите количество правильных несократимых дробей со знаменателем n.
 
Входные данные 
В первой строке задается число знаменателей для которых надо найти количество правильных несократимых дробей N (\(N <=100\)). Каждая последующая строка число n (\(n < 10^9\)). 
 
Выходные данные 
Для каждого n в отдельной строке вывести ответ на поставленную задачу.
 

 

Примеры
№ Входные данные Выходные данные
1
4
23
23456
7
17
 
 22
11712
6
16
Арифметические алгоритмы (Теория чисел)Функция Эйлера
✓ 216✗ 234600лёгкаяВойти и решать
Небоскреб#31785
В небоскребе n этажей. Известно, что если уронить стеклянный шарик с этажа номер p, и шарик разобьется, то если уронить шарик с этажа номер p+1, то он тоже разобьется. Также известно, что при броске с последнего этажа шарик всегда разбивается.
 
Вы хотите определить минимальный номер этажа, при падении с которого шарик разбивается. Для проведения экспериментов у вас есть два шарика. Вы можете разбить их все, но в результате вы должны абсолютно точно определить этот номер.
 
Определите, какого числа бросков достаточно, чтобы заведомо решить эту задачу.
 
Входные данные
Программа получает на вход количество этажей в небоскребе n.
 
Выходные данные
Требуется вывести наименьшее число бросков, при котором можно всегда решить задачу.
 
Примечание
Комментарий к первому примеру. Нужно бросить шарик со 2-го этажа. Если он разобьется, то бросим второй шарик с 1-го этажа, а если не разобьется - то бросим шарик с 3-го этажа.
 
Подсказки
1. Как следует действовать, если шарик был бы только один?
2. Пусть шариков два и мы бросили один шарик с этажа номер k. Как мы будем действовать в зависимости от того, разобьется ли шарик или нет?
3. Пусть f(n) - это минимальное число бросков, за которое можно определить искомый этаж, если бы в небоскребе было n этажей. Выразите f(n) через значения f(a) для меньших значений a.
 
Примеры
№ Входные данные Выходные данные
1 4 2
2 7 3
Динамическое программирование: один параметрРекуррентные последовательности
✓ 70✗ 156700средняяВойти и решать
Игра с пешкой#31781
В левой нижней клетке шахматной доски размера N×N стоит пешка. Двое игроков по очереди двигают её, причём каждый может подвинуть её на одну клетку вверх или на одну клетку вправо. На диагонали доски написаны числа a1, a2, …, aN. Когда пешка попадает на диагональ, игра кончается и выигрыш первого игрока равен значению числа, написанного в клетке с остановившейся пешкой. Напишите программу определения гарантированного выигрыша первого игрока.

3              
  1            
    4          
      1        
        5      
          9    
            2  
              6


Входные данные
В первой строке записано число N (1 ≤ N ≤ 100). Во второй строке записаны натуральные числа a1, a2, …, aN (1 ≤ ai ≤ 100).
 
Выходные данные
Выведите одно число – выигрыш первого игрока.

Ввод Вывод
8
3 1 4 1 5 9 2 6
5

Динамическое программирование на таблицахПростые игры
✓ 91✗ 311800средняяВойти и решать
Олег и двоичные последовательности#30708
Олег очень любит двоичные последовательности — последовательности из нулей и единиц. Совсем недавно он написал в тетради очередную двоичную последовательность из n элементов.
Для выписанной последовательности Олег посчитал Z-функцию.

Z-функцией последовательности s1, . . . , sn называется массив z[1..n], в котором:

• z[1] = 0;
• Если i > 1, то z[i] равно длине наибольшего общего префикса последовательности s и суффикса последовательности s, начинающегося с i-й позиции. Иначе говоря, z[i] равно максимальному k, такому что s1 = si , s2 = si+1, . . . , sk = si+k−1.

Например, для последовательности s = h0, 0, 1, 1, 0, 0, 1i Z-функция следующая: z = h0, 1, 0, 0, 3, 1, 0i.
Записав в тетради последовательность и ее Z-функцию, Олег лег спать. Пока он спал, его младший брат Егор прокрался в комнату и закрасил фломастером последовательность и некоторые значения Z-функции. Проснувшись, Олег заинтересовался, сколько различных двоичных последовательностей он мог вечером написать в тетради, чтобы незакрашенные значения Z-функции были правильными.

Найдите число искомых последовательностей и выведите его по модулю 109 + 7. Заметьте, что Олег мог и ошибиться при вычислении Z-функции, в этом случае ни одна последовательность не подходит и ответ равен 0.
Формат входных данных
В первой строке входного файла находится целое число n — длина исходной двоичной последовательности (1 ≤ n ≤ 1000). Во второй строке входного файла находятся n целых чисел z[1], . . . , z[n], где z[i] — значение Z-функции в позиции i, или −1, если значение в i-й позиции было закрашено (−1 ≤ z[i] ≤ n).

Формат выходных данных
В выходной файл выведите единственное число — остаток от деления числа подходящих двоичных последовательностей на число 109 + 7.
 
Ввод Вывод
3
0 0 1		 2
4
0 0 1 0		 0
3
0 3 -1		 0
3
-1 -1 -1		 8


Пояснение
В первом примере подходят последовательности {0, 1, 0 }  и { 1, 0, 1 }.
Во втором примере не существует ни одной двоичной последовательности длины 4 с заданной Z-функцией.
В третьем примере z[2] = 3, что противоречит определению Z-функции, поэтому ответ 0.
В четвертом примере подходит любая двоичная последовательность длины 3.
Обход в глубинуПрименение обхода в глубинуРазбор случаев
✓ 1✗ 0—Войти и решать
Circular Barn#29547
У Фермера Джона круглый амбар. Амбар состоит из кольца из n комнат, пронумерованных 1…n по периметру (3≤n≤1,000). Каждая комната имеет двери в две соседние комнаты и одну дверь во внешний мир.
ФД хочет разместить ровно ri коров в комнате i (1≤ri≤1,000,000). Он планирует открыть k внешних дверей (1≤k≤7), через которые коровы будут входить в амбар. Каждая корова затем идёт по часовой стрелке, пока не добредёт до нужной комнаты. ФД хочет открыть двери так, чтобы все коровы вместе прошли как можно меньшее расстояние. Коровы предварительно могут собраться как им выгоднее перед этими незакрытыми дверями (эти перемещения не входят в общее расстояние, учитываемое в задаче). Определите минимальное суммарное расстояние, которое придётся пройти коровам, если ФД наилучшим образом выберет какие k открыть.
 
ФОРМАТ ВВОДА:
Первая строка ввода содержит n и k. Последующие n строк содержат r1…rn.

ФОРМАТ ВВОДА:
Выведите минимальное суммарное расстояние пройденное коровами.
 
Ввод Вывод
6 2
2
5
4
2
6
2
 14


ФД может открыть двери 2 и 5. 11 коров войдут в двери 2 и пройдут суммарное расстояние 8 чтобы попасть в комнаты 2,3,4. 10 коров войдут в дверь 5 и пройдут общее расстояние 6, чтобы попасть в комнаты 5,6,1.



 
Динамическое программированиеДинамическое программирование: два параметраЗадача на реализациюРекурсия
✓ 1✗ 1—Войти и решать
Fenced In#29546
Коровы Фермера Джона боятся больших пространств. Поэтому разгородил своё поле на некоторое количество маленьких регионов, построив вертикальные (север-юг) и горизонтальные (восток-запад) изгороди.
Поле представляет собой прямоугольник с угловыми вершинами в точках (0,0) and (A,B). ФД построил n вертикальных изгородей (0≤n≤25,000) в различных позициях a1…an (0<ai<A); каждая изгородь проходит от точки (ai,0) до точки (ai,B). Он также построил m горизонтальных изгородей (0≤m≤25,000) в в различных позициях b1…bm (0<bi<B); каждая изгородь, проходит из (0,bi) в (A,bi). Каждая вертикальная изгородь пересекается с каждой горизонтальной изгородью, разделив поле на (n+1)(m+1) регионов.
 
К несчастью, ФД забыл построить ворота в своих изгородях, сделав невозможным коровам покидать свой регион. Он хочет исправить ситуацию, удалив куски изгороди, чтобы позволить коровам перемещаться между соседними регионами. Он хочет выбрать некоторые пары соседних регионов и удалить всю длину изгороди между ними. А ещё он хочет обеспечить, чтобы коровы могли попасть в любую часть поля.
 
Например, ФД мог построить изгороди так:
 
+---+--+
|      |   |
+---+--+
|     |    |  
|     |    |
+---+--+
и открыть их так:
 
+---+--+
|          |  
+---+  +  
|          |  
|          |
+---+--+
Помогите ФД определить минимальную суммарную длину изгородей, которые он должен удалить, чтобы достичь своей цели.
 
ФОРМАТ ВВОДА:
Первая строка ввода содержит числа A, B, n, and m (1≤A,B≤1,000,000,000). Следующие n строк содержат a1…an. Следующие m строк содержат b1…bm.

ФОРМАТ ВЫВОДА:
Выведите минимальную длину изгороди, которую ФД должен удалить. Заметим что это число может не поместиться в 32-битное целое и Вам нужно использовать 64-битное целое (например, "long long" в C/C++ )
 
Ввод Вывод
15 15 5 2
2
5
10
6
4
11
3
 44
Алгоритмы сортировкиЖадный алгоритм
✓ 1✗ 41 200средняяВойти и решать
Дом у дороги#29479
Министерство дорожного транспорта решило построить себе новый офис. Поскольку министр регулярно выезжает с инспекцией наиболее важных трасс, было решено, что офис министерства не должен располагаться слишком далеко от них.
 
Наиболее важные трассы представляют собой прямые на плоскости. Министерство хочет выбрать такое расположение для своего офиса, чтобы максимум из расстояний от офиса до трасс был как можно меньше.
 
Требуется написать программу, которая по заданному расположению наиболее важных трасс определяет оптимальное расположение дома для офиса министерства дорожного транспорта.
 
Входные данные
Первая строка входного файла содержит одно целое число n — количество наиболее важных трасс (1  ≤ n ≤ 104 ).
 
Последующие n строк описывают трассы. Каждая трасса описывается четырьмя целыми числами x1, y1, x2 и y2 и представляет собой прямую, проходящую через точки (x1, y1)  и (x2, y2) . Координаты заданных точек не превышают по модулю 104. Точки (x1 , y1)  и (x2 , y2)  ни для какой прямой не совпадают.
 
Выходные данные
Выходной файл должен содержать два разделенных пробелом вещественных числа: координаты точки, в которой следует построить офис министерства дорожного транспорта. Координаты по модулю не должны превышать 109, гарантируется, что хотя бы один такой ответ существует. Если оптимальных ответов несколько, необходимо выведите любой из них.
 
Ответ должен иметь абсолютную или относительную погрешность не более 10−6, что означает следующее. Пусть максимальное расстояние от выведенной точки до некоторой трассы равно x, а в правильном ответе оно равно y. Ответ будет засчитан, если значение выражения | x − y | /  max(1, |y| )  не превышает 10−6.
 
 
Ввод Вывод
4
0 0 0 1
0 0 1 0
1 1 2 1
1 1 1 2
 0.5000000004656613 0.4999999995343387
7
376 -9811 376 -4207
6930 -3493 6930 -8337
1963 -251 1963 -5008
-1055 9990 -684 9990
3775 -348 3775 1336
7706 -2550 7706 -8412
-9589 8339 -4875 8339
 4040.9996151750674 12003.999615175067

 Личные олимпиады, Всероссийская олимпиада школьников, Региональный этап, 2011, 2 день, Задача D 
Вычислительная геометрияТернарный поиск
✓ 2✗ 381 300средняяВойти и решать
Точки на прямой#28417
Маленький Петя очень любит точки. Недавно мама подарила ему n точек, лежащих на прямой OX. Пете стало интересно, сколькими способами он может выбрать три различные точки так, чтобы расстояние между двумя самыми удаленными из выбранных точек не превышало d.
Обратите внимание, что порядок точек внутри выбранной тройки значения не имеет.

Входные данные
Первая строка содержит два целых числа: n и d (1 ≤ n ≤ 105; 1 ≤ d ≤ 109). Следующая строка содержит n целых чисел x1, x2, ..., xn, по модулю не превосходящих 109 — x-координаты точек, подаренных Пете.
Гарантируется, что координаты точек во входных данных строго возрастают.

Выходные данные
Выведите единственное целое число — количество троек точек, в которых расстояние между двумя самыми удаленными точками не превосходит d.
Пожалуйста, не используйте спецификатор %lld для чтения или записи 64-х битовых чисел на С++. Рекомендуется использовать потоки cin, cout или спецификатор %I64d.
 
Ввод Вывод
4 3
1 2 3 4
 4
4 2
-3 -2 -1 0
 2
5 19
1 10 20 30 50
 1
 
В первом примере нам подходит любая тройка различных точек.
Во втором примере нам подходят всего 2 тройки: {-3, -2, -1} и {-2, -1, 0}.
В третьем примере нам подходит одна тройка: {1, 10, 20}.
 
"Два указателя"Комбинаторика
✓ 384✗ 725600лёгкаяВойти и решать
Пары точек#28344
На прямой находятся N точек. Требуется подсчитать количество пар индексов (i, j) таких, что i не равно j и |ai - aj|  <= D.

Формат входных данных
В первой строке находятся два числа N и D (1 <= N <= 105, 1 <= D <= 109). Во второй строке находится N неотрицательных чисел, каждое из котороых не более чем 2*109.

Формат выходных данных
Выведите на экран ответ на задачу.
"Два указателя"Использование сортировки
✓ 571✗ 2 912600лёгкаяВойти и решать
Palindromic Paths#28324
Ферма Джона представлена решёткой из N×N полей(2≤N≤18), каждое из которых помечено буквой алфавита. Например,
ABCD
BXZX
CDXB
WCBA
Каждый день корова Беси идёт с левого верхнего угла в правый нижний, двигаясь либо на одну клетку вправо, либо на одну клетку вниз. Беси записывает строку, которая получается в результате её маршрута, построенную из букв, по которым она прошла. Он будет очень расстроена, если в результате построенная строка окажется палиндромом (читается одинаково от начала к концу и от конца к началу), поскольку она запутается в каком направлении она шла.
 
Пожалуйста, помогите Беси определить количество различных палиндромов, которые она сможет сформировать во время своего путешествия. Различные способы формировать один и тот же палиндром следует учитывать только один раз. Например, в примере выше имеется несколько способов сформировать палиндром ABXZXBA, однако существует всего 4 различных палиндрома, которые Беси может сформировать ABCDCBA, ABCWCBA, ABXZXBA, ABXDXBA.
 
ФОРМАТ ВВОДА :
Первая строка ввода содержит N, а последующие N строк содержат N описание поля. Каждая строка содержит по N символов в диапазоне A..Z.

ФОРМАТ ВЫВОДА :
Выведите количество различных палиндромов, которые Беси может сформировать.
 
Ввод Вывод
4
ABCD
BXZX
CDXB
WCBA
 4

 
meet in the middleПеребор
✓ 7✗ 261 100средняяВойти и решать
Ski Course Rating#27302
Лыжный маршрут описывается M x N решеткой высот (1 <= M,N <= 500), каждая высота в интервале 0 .. 1,000,000,000.  
 
Некоторые из этих ячеек помечены как стартовые точки маршрута. Организаторы хотят вычислить рейтинг трудности каждой стартовой точке. Рейтинг трудности стартовой точки P – это минимальное число D такое, что корова сможет  успешно достичь как минимум T ячеек решётки  (1 <= T <= MN), если она стартует в P и может двигаться в соседнюю ячейку (на север, юг, запад или восток), только если абсолютная величина разности высот в этих ячейках не превосходит D. 
 
Вычислите рейтинг трудности для каждой стартовой точки и выведите их сумму.
 
 
INPUT FORMAT:
 
* Строка 1: Целые числа M, N, T.
 
* Строки 2..1+M: Каждая из этих M строк содержит N целых высот.
 
* Строки 2+M..1+2M: Каждая из этих M строк содержит N величин равных 0 или 1, где 1 означает, что это ячейка – стартовая точка


OUTPUT FORMAT:
 
* Строка 1: Сумма рейтингов трудности всех стартовых точек (заметим, что это число может не поместиться в 32-битное целое, даже если каждый рейтинг в отдельности поместится).
 

INPUT DETAILS:
 
Местность описывается решеткой из 3 х 5 высот.
Верхняя левая и правая нижняя ячейки являются стартовыми точками.
Из каждой стартовой точки мы должны быть способны добраться до 10 ячеек.
 
OUTPUT DETAILS:
Рейтинг трудности верхнего левого угла равен 4.
Рейтинг трудности правого нижнего угла равен 20.
 
Ввод Вывод
3 5 10
20 21 18 99 5
19 22 20 16 17
18 17 40 60 80
1 0 0 0 0
0 0 0 0 0
0 0 0 0 1
 24

 
Бинарный поиск по ответуграфыПоиск компонент связности
—Войти и решать
Cow Curling#27300
В коровий кёрлинг вовлечены две команды, каждая из которых двигает N тяжёлых камней (3 <= N <= 50,000) по льду. В конце игры имеется 2N камней на льду, каждый из которых расположен в различной точке
плоскости.  
 
Подсчёт очков в коровьем кёрлинге ведётся следующим образом:
Камень считается «захваченным», если он содержится внутри треугольника, по углам которого находятся камни противника (камень, который находится на границе такого треугольника, также считается захваченным). Счёт команды есть количество камней команды противника, которые «захвачены».
 
Вычислите финальный счёт матча по коровьему кёрлингу, по заданному расположению всех камней.
 
 
INPUT FORMAT:
 
* Строка 1: Целое число N.
 
* Строки 2..1+N: Каждая строка содержит 2 целых числа, указывающих x  и y координаты камня команды A (каждая координата лежит в диапазоне -40,000 .. +40,000).
 
* Строки 2+N..1+2N: Каждая строка содержит 2 целых числа, указывающих x  и y координаты камня команды B (каждая координата лежит в диапазоне -40,000 .. +40,000).
 
OUTPUT FORMAT:
 
* Строка 1: Два разделённых пробелом целых числа, представляющих счета команд A и B 
 
SAMPLE:
 
Ввод Вывод
4
0 0
0 2
2 0
2 2
1 1
1 10
-10 3
10 3 		 1 2
 
INPUT DETAILS:
 
У каждой команды по 4 камня.
Команда A имеет камни (0,0), (0,2), (2,0), (2,2).
Команда B имеет камни (1,1), (1,10), (-10,3), (10,3).
 
 
OUTPUT DETAILS:
 
Команда A захватила камень противника в точке (1,1).
Команда B захватила камни противника в точках (0,2) и (2,2).
Вычислительная геометрияДинамическое программированиеСтруктуры данных
—Войти и решать
Поделиться
Класснуть