Для целого числа $$$D$$$ найдите координаты всех целочисленных точек $$$(x, y)$$$ c неотрицательными координатами таких, что Евклидово расстояние от $$$(x, y)$$$ до начала координат $$$(0, 0)$$$ равно $$$D \sqrt{2}$$$.
В единственной строке содержится целое число $$$D$$$ $$$(1 \le D \le 10^6)$$$ — параметр задачи.
В первой строке выведите целое число $$$K$$$ $$$(0 \le K \le 10^7)$$$ — количество найденных точек.
В следующих $$$K$$$ строках необходимо вывести через пробел по два целых числа $$$x_i$$$, $$$y_i$$$ $$$(0 \le x_i \le y_i \le 2 \cdot D)$$$ — координаты $$$i$$$-й найденной точки.
Точки должны быть отсортированы по возрастанию координаты $$$x$$$ $$$(x_1 \lt x_2 \lt \dots \lt x_k)$$$.
5
2 1 7 5 5
9
1 9 9
85
5 17 119 35 115 41 113 71 97 85 85
Определение: Евклидово расстояние от точки $$$(x, y)$$$ до точки $$$(a, b)$$$ вычисляется по формуле $$$\sqrt{(x - a)^2 + (y - b)^2}$$$.
Первый тестовый пример.
Для $$$D = 5$$$ существует две точки, удовлетворяющие условиям задачи:
$$$5 \sqrt{2} = \sqrt{25} \cdot \sqrt{2} = \sqrt{50}$$$:
Второй тестовый пример.
Для $$$D = 9$$$ существует только одна точка $$$(9, 9)$$$, удовлетворяющая условию задачи.
Алихан решил повесить новую занавеску. Занавеска держится на $$$N$$$ крючках вдоль всей гардины.
Очевидно, что если начать вешать занавеску на крючки слева направо подряд, то нагрузка будет неравномерной и гардина может свалиться.
Поэтому Алихан придерживается следующей стратегии:
После того, как Алихан повесил занавеску, его заинтересовало, а на каком шаге были использованы крючки под номерами $$$A_1, A_2, \dots, A_Q$$$.
Занавеска была очень большой, поэтому Алихан очень устал. Помогите Алихану и выведите для каждого интересующего Алихана крючка, на каком шаге он был использован.
В первой строке через пробел даны два целых числа $$$N$$$ и $$$Q$$$ $$$(1 \le N \le 10^{18}; 1 \le Q \le 10^4)$$$ — количество крючков на гардине и количество интересующих Алихана крючков.
Во второй строке через пробел записаны $$$Q$$$ различных целых чисел $$$A_1, A_2, \dots, A_Q$$$ $$$(1 \le A_i \le N)$$$ — интересующие Алихана крючки.
В единственной строке через пробел выведите $$$Q$$$ чисел $$$T_i$$$ — на каком шаге был использован крючок $$$A_i$$$.
10 101 10 2 9 3 8 4 7 5 6
1 1 5 8 3 4 6 7 2 2
9876543210 33456789120 5678912340 7891234560
5798205414 6764530002 3863296238
Первый тестовый пример.
На гардине $$$N = 10$$$ крючков.
Крючки будут использованы в следующем порядке:
Даны две различные десятичные цифры $$$A$$$ и $$$B$$$.
Выведите любое целое положительное число $$$N$$$, составленное только из этих цифр (или одной из них), которое нацело делится на $$$2023$$$.
В единственной строке даны через пробел два целых числа $$$A$$$ и $$$B$$$ $$$(0 \le A \lt B \le 9)$$$ — разрешенные десятичные цифры.
Выведите целое положительное число $$$N$$$ $$$(1 \le N \lt 10^{100})$$$, которое
Число $$$N$$$ не должно иметь ведущих нулей (старшая цифра должна быть отлична от $$$0$$$).
Если корректных ответов несколько — выведите любой из них.
2 3
322322332332
5 7
777775577775
Чтобы скоротать время в долгой поездке, Айзат придумала следующую игру.
В начале игры у Айзат есть клетчатый лист бумаги размером $$$W$$$ клеток в ширину и $$$H$$$ клеток в высоту (всего $$$W \times H$$$ клеток).
За один ход Айзат может разорвать лист на две части по границе клеток (по вертикали или по горизонтали). Из двух получившихся листов Айзат оставляет в игре лист с большим количеством клеток.
Айзат интересуется, за какое минимальное количество ходов она сможет получить лист, на котором будет не более чем $$$S$$$ клеток.
В первой строке находится единственное целое число $$$T$$$ $$$(1 \le T \le 10^3)$$$ — количество игр, в которые Айзат успеет сыграть в поездке.
Следующие $$$T$$$ строк содержат через пробел три целых числа $$$W_i$$$, $$$H_i$$$, $$$S_i$$$ $$$(1 \le W_i, H_i \le 10^9; 1 \le S_i \le 10^{18})$$$ — количество клеток в ширину и высоту на $$$i$$$-м листе, а также верхняя граница для количества клеток в конце $$$i$$$-й игры.
Выведите через пробел $$$T$$$ чисел $$$D_i$$$ — минимальное количество ходов, необходимое для того, чтобы из листа размером $$$W_i \times H_i$$$ клеток получился лист, содержащий не более $$$S_i$$$ клеток.
33 25 26 6 509 7 19
6 0 2
4123456789 567891234 912345678912345678 123456789 567891234567891234 912345678 123456789987654321 876543219 123456789123456789
27 28 32 3
Первый тестовый пример
Айзат сыграет в три игры:
Возможны и другие варианты ходов, но быстрее, чем за шесть ходов получить лист из $$$2$$$ или менее клеток нельзя.
Можно показать, что никакая другая последовательность из двух ходов не может привести к листу, содержащему не более 19 клеток.
При рождении каждому теленку присваивается идентификационный номер. Этот номер вместе с номерами отца и матери теленка записывается в паспорте теленка.
Для каждой породы коров и быков имеется отдельный ящик, в котором хранятся все паспорта животных данной породы. Идентификационные номера одной породы уникальны — зная породу и номер животного, можно однозначно идентифицировать его.
Новый начальник решил перенести все паспорта в электронный вид и поручил это студентам. К сожалению, студенты сделали ошибки при вводе чисел. Помогите написать программу, которая проверяет электронные паспорта каждой породы на ошибки следующего вида:
Первая строка содержит единственное натуральное число $$$N$$$ $$$(N \le 100)$$$– количество пород коров (и ящиков).
Далее следуют описания $$$N$$$ ящиков, описание $$$i$$$-го ящика состоит из двух строк:
Гарантируется, что общее количество паспортов $$$\sum{P_i} \le 10^5$$$.
Выведите $$$N$$$ строк, $$$i$$$-я строка содержит (без кавычек)
325 4 7 4 6 525 4 7 3 4 631 2 3 1 3 2 3 4 5
INCORRECT CORRECT INCORRECT
335 4 7 3 4 6 1 3 535 4 7 3 4 6 1 4 535 4 7 3 4 6 1 5 4
CORRECT CORRECT INCORRECT
Первый тестовый пример
Второй тестовый пример
Близнецам подарили треугольник на день рождения. Но они ходят в разные школы и каждый хочет показать свой подарок одноклассникам как можно скорее. Поэтому они хотят разрезать треугольник на две части справедливо.
Разрез считается справедливым, если площади двух фигур, полученных путем разреза, имеют равную площадь.
Для упрощения близнецы расположили треугольник следующим образом:
Также родители близнецов уже зафиксировали начало разреза — точку $$$P$$$ на одной из сторон треугольника.
Ваша задача — найти координаты точки $$$Q$$$ на одной из сторон треугольника такой, что отрезок $$$PQ$$$ разделяет треугольник на две фигуры равной площади.
Первая строка содержит через пробел три целых числа $$$a$$$, $$$b$$$ и $$$c$$$ $$$(0 \le a, b, c \le 10^6)$$$ — координаты второй вершины и $$$X$$$-координата третьей вершины треугольника соответственно.
Во второй строке записаны через пробел два целых числа $$$px$$$ и $$$py$$$ $$$(0 \le px, py \le 10^6)$$$ — координаты начала разреза $$$P$$$.
Гарантируется, что треугольник имеет ненулевую площадь.
Гарантируется, что точка $$$P$$$ лежит на одной из сторон треугольника.
Если не существует точки $$$Q$$$, удовлетворяющей условию — выведите через пробел без кавычек «-1 -1».
В ином случае выведите через пробел два вещественных числа $$$qx$$$ и $$$qy$$$ $$$(0 \le qx, qy \le 10^6)$$$ — координаты точки $$$Q$$$.
Ответ будет засчитан, если абсолютная и/или относительная погрешность координат не превосходит $$$10^{-4}$$$.
3 7 85 0
2.40000000 5.60000000
5 10 124 8
7.50000000 0.00000000
3 4 55 0
1.50000000 2.00000000
17 31 4923 0
18.84615385 29.21153846
Обратите внимание Рекомендуется выводить более, чем $$$4$$$ знака после запятой.
Пример Для вывода числа $$$z$$$ с $$$6$$$ знаками после запятой можно воспользоваться следующими командами:
(Требуются <iostream>, <iomanip>);
Первый тестовый пример.
В первом примере точка Q имеет координаты $$$(2.4, 5.6)$$$.
Удвоенная площадь всего треугольника равна $$$7 \cdot 8 = 56$$$.
Удвоенная площадь синего треугольника после разреза равна $$$5.6 \cdot 5 = 28$$$.
Разрез выглядит подобным образом Второй тестовый пример.
Во втором примере точка Q имеет координаты $$$(7.5, 0.0)$$$.
Удвоенная площадь всего треугольника равна $$$10 \cdot 12 = 120$$$.
Удвоенная площадь синего треугольника после разреза равна $$$8 \cdot 7.5 = 60$$$.
Третий тестовый пример.
В третьем примере точка Q имеет координаты (1.5, 2.0).
Удвоенная площадь всего треугольника равна $$$4 \cdot 5 = 20$$$.
Удвоенные площади синего и красного треугольников после разреза равны $$$2.0 \cdot 5 = 10$$$.
Последний тестовый пример.
Это интерактивная задача — ваша программа будет обмениваться данными с программой жюри через стандартный ввод и вывод (консоль).
Айбек агай спрятал Слона на шахматной доске $$$8 \times 8$$$. Вы очень хотите узнать его координаты.
Столбцы на шахматной доске обозначаются латинской заглавной буквой от $$$A$$$ до $$$H$$$, а строки — целым числом от $$$1$$$ до $$$8$$$. Например, клетка $$$D7$$$ расположена в $$$4$$$-м столбце и $$$7$$$-й строке.
Чтобы найти координаты Слона, вы можете задать Айбек агаю не более 10 раз следующий вопрос:
«За какое минимальное количество ходов Слон достигнет столбца $$$X_1$$$ и строки $$$Y_1$$$?
После вопросов вам необходимо вывести позицию, на которой предположительно располагается Слон.
Обратите внимание, что
Все координаты столбцов должны выводиться только заглавными буквами.
Вопрос задаётся в формате $$$\textbf{?}$$$ $$$X_1Y_1$$$ $$$(A \le X_1 \le H$$$, $$$1 \le Y_1 \le 8)$$$ — вопросительный знак и координаты клетки из вопроса.
Всего вы можете задать вопрос не более 10 раз.
В ответ на вопрос программа жюри выводит целое число $$$K$$$ :
Окончательный ответ выводится в формате $$$\textbf{!}$$$ $$$X_RY_R$$$ $$$(A \le X_R \le H$$$, $$$1 \le Y_R \le 8)$$$ — восклицательный знак и предполагаемые координаты Слона.
После вывода окончательного ответа ваша программа обязательно должна завершиться.
2 -1 1 0
? B6 ? F3 ? H6 ? G5 ! G5
Определение: шахматная фигура «Слон» за один ход может переместиться на любую клетку по диагонали.
Формально, если Слон стоит на клетке $$$X$$$$$$Y$$$, то он может переместиться в клетку $$$U$$$$$$V$$$ только в случае, если $$$|U - X| = |V - Y|$$$.
Первый тестовый пример.
Айбек агай спрятал Слона на клетке G5.
Компания Naudio планирует создание и выпуск нового производительного процессора для обработки аудио-данных. Набор команд процессора должен содержать $$$K$$$ команд.
Каждая команда процессора — двоичная строка некоторой фиксированной длины $$$Len$$$. Вам поручено определить кодировку каждой из $$$K$$$ команд, то есть определить их двоичный вид, соблюдая следующие условия:
Формально, пусть $$$i$$$ и $$$j$$$ $$$(1 \leq i, j \leq len)$$$ — номера каких-то бит в команде. Тогда $$$|cnt_k(i) - cnt_k(j)| \leq 1$$$ для любой пары $$$i, j$$$.
Здесь $$$cnt_k(i)$$$ определяется как количество команд, в которых $$$i$$$-й бит был равен единице.
В первой строке входные данных содержится одно целое число $$$T$$$ ($$$1 \leq T \leq 10$$$) — количество прототипов процессора.
Каждая из следующих $$$T$$$ строк состоит из одного целого числа $$$K_i$$$ ($$$1 \leq K_i \leq 10^4$$$) — требуемого количества команд в наборе команд $$$i$$$-го прототипа процессора Naudio.
Для $$$i$$$-го прототипа выведите:
Если корректных ответов несколько, выведите любой.
Гарантируется, что ответ всегда существует в заданных ограничениях задачи.
3123
2 01 2 01 10 4 1110 1101 0111
Первый прототип
В данном случае необходима одна команда.
Минимальная подходящая длина $$$Len$$$ равна $$$2$$$ (т.к. она обязана быть четной).
Всего возможно четыре варианта:
Можно вывести любую из них.
Второй прототип
Длина и набор возможных команд аналогичен первому прототипу.
В то же время подходит только пара команд 01 и 10 (в любом порядке), так как любая другая пара команд будет различаться по количеству единичных бит.
Третий прототип.
В данном случае длины $$$2$$$ уже не хватит, поэтому $$$Len = 4$$$.
Каждая из использованных команд содержит ровно $$$3$$$ единичных бита.
Рассмотрим, сколько команд содержат каждый бит:
Видно, что количество команд с каждым битом отличается не более, чем на 1.
Айбек и Айгуль играют в игру на дереве. Напомним, что дерево это связный граф без циклов. Дерево состоит из $$$n$$$ $$$(n \geq 2)$$$ вершин. Первым ходит Айбек - он выбирает любую вершину дерева, обозначим ее $$$u$$$. После чего ходит Айгуль и выбирает любую другую вершину дерева, обозначим ее $$$v$$$. После того, как оба игрока сделали свой выбор, случайно равновероятно выбирается какая-то одна из вершин дерева $$$w$$$ и затем:
Здесь $$$d(a, b)$$$ — это расстояние между двумя вершинами дерева, то есть количество ребер на простом пути между $$$a$$$ и $$$b$$$. Айбек не очень хорош в играх на деревьях, поэтому помогите ему найти такую вершину, при выборе которой он максимизирует свою вероятность выигрыша. Если же таких вершин несколько, найдите вершину с минимальным номером.
В первой строке входных данных содержится одно целое число $$$t$$$ $$$(1 \leq t \leq 10^3)$$$ — количество раундов игры, в которую будут играть Айбек и Айгуль.
Далее следуют описания каждого раунда игры — в первой строке содержится целое число $$$n$$$ $$$(2 \leq n \leq 2\cdot10^5)$$$ — число вершин в дереве.
В следующих $$$n - 1$$$ строках, описывающих раунд, содержится по 2 целых числа $$$u_i$$$ и $$$v_i$$$ $$$(1 \leq u_i, v_i \leq n, u_i \neq v_i)$$$ — ребра дерева.
Гарантируется, что граф из каждого раунда игры образует структуру дерева.
Также гарантируется, что сумма $$$n$$$ по всем входными данными не превосходит $$$2\cdot10^5$$$
Для каждого раунда игры выведите одно целое число — номер вершины дерева, которую следует выбрать Айбеку, чтобы максимизировать свою вероятность выиграть. Если существует несколько таких вершин, то выведите вершину с наименьшим номером.
251 44 34 22 521 2
4 1