Темы
Информатика(2656 задач)
--->
36 задач
<---
Юный джедай Иван был заброшен на Звезду Смерти с заданием уничтожить её. Для того, чтобы уничтожить Звезду Смерти, ему требуется массив неотрицательных целых чисел a i длины N . К сожалению, у Ивана нет этого массива, но есть секретный документ с требованиями к этому массиву, который ему передал его старый друг Дарт Вейдер.
В этом документе содержится квадратная матрица m размера N , где элемент в i -й строке в j -м столбце равен побитовому "И" чисел a i и a j . Для повышения безопасности главная диагональ матрицы была уничтожена и вместо чисел на ней были записаны нули. Помогите Ивану восстановить массив a и выполнить свою миссию.
Гарантируется, что решение всегда существует. Если решений несколько, выведите любое.
В первой строке содержится число N ( 1 ≤ N ≤ 1000 ) – размер матрицы. Каждая из последующих N строк содержит по N целых чисел m ij ( 0 ≤ m ij ≤ 9 ) – элементы матрицы.
В единственной строке выведите N целых неотрицательных чисел, не превышающих 100 – требуемый массив a .
40 баллов — (1 ≤ N ≤ 5) .
100 баллов — (1 ≤ N ≤ 1 000) .
3 0 1 1 1 0 1 1 1 0
1 1 1
5 0 0 1 1 1 0 0 2 0 2 1 2 0 1 3 1 0 1 0 1 1 2 3 1 0
1 2 3 1 3
На родной планете Чубакки растет очень большое дерево, на ветках которого вуки строят свои домики. Чубакке стало интересно, как быстро можно попасть из некоторых домиков в другие. Вам придется ответить на несколько его вопросов, чтобы он вас отпустил.
Вам дано дерево с N вершинами порядка K , то есть каждая вершина дерева может иметь не более K потомков. Дерево создано по принципу "минимальной энергии": вершины в нем располагается на новом уровне только тогда, когда все места на предыдущем уровне (слева направо) заняты. В таком же порядке вершины дерева пронумерованы, начиная с 1.
Вам необходимо ответить на Q запросов вида " x y ", где ответом является расстояние (количество ребер в минимальном пути) в данном дереве между вершинами с номерами x и y .
Первая строка содержит три целых числа: N ( 1 ≤ N ≤ 10 15 ), K ( 1 ≤ K ≤ 1000 ) и Q ( 1 ≤ Q ≤ 100000 ). Каждая из следующих Q строк содержит пару чисел x y ( 1 ≤ x , y ≤ N , x ≠ y ) - запросы, описанные в условии.
Выведите Q строк, в каждой из которых одно целое число - ответ на соответствующий запрос.
Решения, работающие при 1 ≤ N , Q ≤ 1000 , будут оцениваться в 20 баллов. Решения, работающие при 1 ≤ N , Q ≤ 100000 , будут оцениваться в 50 баллов.
7 2 3 1 2 2 1 4 7
1 1 4
9 3 3 8 9 5 7 8 4
2 2 3
Давным-давно в одной далекой-далекой галактике, было N планет. Также было N - 1 межпланетных магистралей, соединявших между собой все планеты (не обязательно напрямую). Иными словами, сеть планет и магистралей образовывала дерево. Кроме того, каждая магистраль имеет свой показатель интересности, заданный неотрицательным целым числом. Пара планет ( A , B ) называется скучной, если выполняются следующие условия:
1. A и B - различные планеты.
2. В действующей сети межпланетных магистралей существует путь между A и B .
3. Побитовый XOR показателей интересности всех магистралей в этом пути равен 0.
Ныне в галактике правит злой император, и он планирует использовать Силу, чтобы уничтожить все межпланетные магистрали в определенном порядке. Для того, чтобы спасти вселенную от гибели, вам необходимо определить количество пар скучных планет и после каждого разрушения вновь подсчитывать эту величину.
Первая строка содержит одно целое число N ( 1 ≤ N ≤ 100000 ). Каждая из следующих N - 1 строк содержит три целых числа A i , B i , Z i ( 1 ≤ A i , B i ≤ 100000 , 0 ≤ Z i ≤ 1000000000 ), которые означают, что планеты с номерами A i и B i соединены магистралью с показателем интересности Z i . Последняя строка содержит N - 1 число: перестановку натуральных чисел от 1 до N - 1 , отражающую порядок уничтожения магистралей (если i -е число в строке равно j , то император уничтожит дорогу между планетами A j и B j на i -м шаге).
Выведите N строк, в k -й строке выведите одно число - количество пар скучных планет после уничтожения k - 1 дорог.
Решения, работающие при N ≤ 1000 , будут оцениваться в 20 баллов. Решения, работающие в случае когда показатель интересности всех путей равен 0, будут оцениваться не менее чем в 30 баллов.
2 1 2 0 1
1 0
3 1 2 4 2 3 4 1 2
1 0 0
4 1 2 0 2 3 0 2 4 0 3 1 2
6 3 1 0
На лесистой луне Эндора находится, если верить Имперской Книге Рекордов, самая длинная ветка в галактике. На этой ветке длиной L метров сидит N дружелюбных хамелеонов. Каждый хамелеон ходит вдоль ветки со скоростью 1 м/с в одном из двух возможных направлений (налево или направо), а также имеет собственный цвет среди одного из K возможных.
Известно, что хамелеоны на Эндоры следуют древним законам, в соответствии с которыми любая прогулка вдоль ветки должна продолжаться до ее конца (после чего хамелеон спрыгивает с ветки), а в случае столкновения двух хамелеонов, они должны развернуться на 180 градусов и продолжить движение в противоположном направлении. Кроме того, при таком столкновении, если хамелеон, двигавшийся налево, имел цвет a , а хамелеон, двигавшийся направо - цвет b , то после разворота первый хамелеон изменит свой цвет на b , а второй хамелеон - на ( a + b ) modK .
Вам даны изначальные цвета, положения и направления движения всех хамелеонов. Определите для каждого цвета, какое расстояние пройдут хамелеоны, находящиеся в этом цвете, до того момента, пока не спрыгнут с ветки.
В первой строке содержится три целых числа числа N , K и L ( 1 ≤ N ≤ 100000 , 1 ≤ K ≤ 40 , 1 ≤ L ≤ 1000000 ). В последующих N строках дана информация о хамелеонах. В i -й строке содержатся: целое число d i ( 1 ≤ d i ≤ L ) - изначальное положение, целое число b i ( 1 ≤ b i ≤ K - 1 ) - изначальный цвет, и символ "L" (налево) или "D" (направо) - изначальное направление движения. Гарантируется, что все числа d i различны и даны в возрастающем порядке.
Выведите K строк, i -я строка должна содержать одно число - расстояние, пройденное хамелеонами цвета i .
Решения, работающие при 1 ≤ Nle 3000 , будут оцениваться в 50 баллов.
2 3 10 0 0 D 10 1 L
10.0 10.0 0.0
4 3 7 1 0 D 3 0 D 4 1 L 6 2 D
10.0 4.0 1.0
4 4 5 1 1 D 3 3 L 4 2 D 5 0 L
2.5 4.0 2.5 4.0
Случилось ужасное! Отважный хорватский охотник попал в его собственную ловушку. В погоне за ценной добычей он помчался вперед и оказался пойман. Чтобы выбраться наружу, он должен решить следующую задачу (а так как умом он не блещет, вам придется ему помочь):
Вам даны 3 целых числа L, D и X. Определите минимальное такое число N , для которого L ≤ N ≤ D и сумма цифр которого равна X . Также определите максимальное M для которого L ≤ M ≤ D и сумма цифр которого равна X . Гарантируется, что такие числа всегда существуют.
В первое строке содержится одно целое число L ( 1 ≤ L ≤ 10000 ). Во второй строке содержится одно целое число D ( 1 ≤ L ≤ D ≤ 10000 ). В третьей строке содержится одно целое число X ( 1 ≤ X ≤ 36 ).
В первой строке выведите одно целое число N из задачи. Во второй строке выведите одно целое число M из задачи.
1 100 4
4 40
100 500 12
129 480
1 10000 1
1 10000