Язык программирования

640 задачвместе с подтемами
Число у задачи — рейтинг сложности, слово рядом — насколько она трудна по сравнению с другими задачами такого же типа. Шкалы задач с ответом и задач с кодом между собой не сравниваются. Рядом — счётчики попыток: ✓ успешные, ✗ неуспешные.
РейтингЛюбойдо 800800–11991200–15991600+Без рейтинга
СначалаПодходящиеНовыеПопулярныеПростыеСложные
Симметричный подарок#48418

Максимус любит симметричные строки. В качестве новогоднего подарка, он попросил ему подарить несколько натуральных чисел.  При этом, Максимус будет доволен, если он сможет записать все значащие цифры шестнадцатеричной записи этих чисел так, чтобы полученная строка было симметричной (читалась одинаково как слева направо, так и справа налево). 
Дед Мороз выбрал для Максимуса N натуральных целых чисел, каждое из которых не больше 1000. Он просит вас помочь ему определить, будет ли доволен Максимус таким подарком.
Если Максимус будет доволен, то ваша программа должна вывести на экран число 1, а иначе - число 0.


Формат входных данных
На вход программе подаётся натуральное число N (N <= 105), а затем N натуральных чисел, каждое из которых не превышает 10000.

Формат выходных данных
Если Максимус будет доволен, то ваша программа должна вывести на экран число 0, а если возможно, то вывести число 1.

Примечание
1. В первом тестовом примере, если перевести все числа в шестнадцатеричную систему счисления, то получим цифры D, 1, 6, 2, 0. Из данных цифр невозможно составить симметричную строку. Ответ: 0.
2. Во втором тестовом примере, если перевести все числа в шестнадцатеричную систему счисления, то получим цифры A, B, 4, 4, A, B, D. Из данных цифр можем составить симметричную строку, например такую AB4D4BA. Ответ: 1.

 
Массивы
✓ 18✗ 26900средняяВойти и решать
Бинарная картина для Алисы#48128

Дед Мороз принёс Алисе новогодний подарок - Бинарную картину, которая представляет собой матрицу размером n x n, где каждое значение равно 0 или 1. Однако, перед тем как положить его под елку, Дед Мороз заметил, что полученная картина немного отличается от той, которую она заказывала.

Чтобы получить картинку, которую хотела Алиса, нужно выполнить следующие два шага:

  1. Отразить картинку горизонтально: перевернуть каждую строку матрицы.
  2. Инвертировать каждый пиксель: заменить каждое значение 0 на 1 и каждое значение 1 на 0.

У Деда Мороза осталось совсем немного времени, чтобы изменить ошибочную картину. Для этого необходимо просто записать в его волшебный посох программу, которая бы изменила текущую.

Помогите Деду Морозу написать программу для посоха, иначе дети могут остаться без новогодних подарков!

Формат входных данных
Программа получает на вход в первой строке число n - размер картины (1 <= n <= 20). В каждой из следующих n строк написано по n чисел 0 или 1. 

Формат выходных данных
Выведите бинарную картину, которую хотела получить на Новый год Алиса. Элементы в строке разделяются одним пробелом.
 

Двумерные массивы
✓ 34✗ 8800средняяВойти и решать
XOR-cумма массива#47936
XOR-cумма массива определяется как побитовое XOR всех его элементов или 0, если массив пуст.

Например, XOR-сумма массива [2,5,6] равна 2 XOR 5 XOR 6 = 1.
Для заданного массива nums, верните сумму всех XOR-сумм для каждого подмножества nums. 

Примечание: подмножества, состоящие из одинаковых элементов, считаются различными и должны подсчитываться несколько раз. 
Массив a является подмножеством массива b, если a может быть получено из b путем удаления некоторых (возможно не удалением никаких) элементов b.
 

Входные данные
Программа получает на вход в первой строке натуральное число n - количество элементов массива nums. Во второй строке записаны n чисел numsi.
 

Ограничения

  • 1 <= n <= 12
  • 1 <= numsi <= 20

Выходные данные
Выведите ответ на задачу.

Пояснения к тестовым примерам
В первом примере 
В [1,3] существует 4 подмножества:
- Пустое подмножество имеет XOR-сумму 0.
- [1] имеет XOR-сумму, равную 1.
- [3] имеет XOR-сумму, равную 3.
- В [1,3] сумма XOR равна 1 XOR 3 = 2.
0 + 1 + 3 + 2 = 6

Во втором примере
В [5,1,6] 8 подмножеств:
- Пустое подмножество имеет XOR-сумму 0.
- [5] имеет XOR-сумму, равную 5.
- [1] имеет XOR-сумму, равную 1.
- [6] имеет XOR-сумму, равную 6.
- [5,1] имеет XOR-сумму 5 XOR 1 = 4.
- [5,6] имеет XOR-сумму 5 XOR 6 = 3.
- [1,6] имеет XOR-сумму 1 XOR 6 = 7.
- [5,1,6] имеет XOR-сумму 5 XOR 1 XOR 6 = 2.
0 + 5 + 1 + 6 + 4 + 3 + 7 + 2 = 28


 
Перебор с возвратомРекурсия
✓ 73✗ 48800средняяВойти и решать
Слияние списков#47668

У Максимуса есть коллекция волшебных амулетов, каждый из которых обладает своей магической силой. Список имеющихся у него амулетов отсортирован в порядке неубывания магической силы. Вернувшись из очередного путешествия, Максимус составил список новых амулетов, предварительно отсортировав их по невозрастанию магической силы. Теперь у него два отдельных списка и он хочет объединить их в один упорядоченный по неубыанию список. 
Он хочет сделать это как можно быстрее. Помогите ему отсортировать два этих списка. Максимус просит вас написать программу, которая будет работать за O(len(A)+len(B)). 
 

Входные данные
Программа получает на вход два неубывающих списка, каждый в отдельной строке.

Выходные данные
Программа должна вывести последовательность неубывающих чисел, полученных объединением двух данных списков.
 
Примеры
№ Входные данные Выходные данные
1 1 5 7
2 4 4 5		 1 2 4 4 5 5 7
"Два указателя"Одномерные массивы
✓ 53✗ 191800средняяВойти и решать
Максимус спасает Элстейд#47509
Одарённый невероятной магией и всезнанием Максимус заметил группу из n монстров, приближающихся к городку Элдстейд. Своими волшебными способностями он мгновенно определил расстояние в километрах от города до каждого монстра. Он также заметил, что все монстры двигаются с постоянной скоростью. У Максимуса есть оружие, способное уничтожить одного монстра после полной зарядки. Зарядка занимает ровно одну минуту. Чтобы победить монстра, оружие должно быть полностью заряжено к моменту приближения монстра к городу. Другими словами, невозможно убить монстра достигшего города, даже если в этот момент оружие закончило полную зарядку.
Максимус задается вопросом, сможет ли он сам спасти город от всех монстров или ему нужна помощь.
Напишите программу, которая поможет Максимусу мгновенно определить максимальное количество монстров, которое он сможет уничтожить до того момента, как хотя бы один монстр достигнет города.

Входные данные
Первая строка содержит число n - количество монстров. Во второй строке записано n чисел dist[i] - начальное расстояние в километрах от города для i-го монстра. Третья строка содержит n чисел speed[i] - скорость i-го монстра в километрах в минуту.

Ограничения

  • n == длина массива dist == длина массива speed
  • 1 <= n <= 105
  • 1 <= dist[i], speed[i] <= 105


Выходные данные
Выведите ответ на задачу.
 
 
Примеры
№ Входные данные Выходные данные Примечание
1 
3
1 3 4 
1 1 1
 
3
 Вначале расстояния между монстрами равны [1,3,4]. Максимус уничтожает первого монстра.
Через минуту расстояния между монстрами становятся [X,2,3]. Максимус уничтожает второго монстра.
Через минуту расстояния между монстрами будут [X,X,2]. Максимус уничтожает третьего монстра.
Все три монстра могут быть уничтожены.
 
2 
4
1 1 2 3
1 1 1 1
 
1
 Вначале расстояния между монстрами равны [1,1,2,3]. Максимус уничтожает первого монстра.
Через минуту расстояния между монстрами становятся равными [X,0,1,2], и второй монстр достиг города.
Максимус может уничтожить только 1 монстра.

 
Алгоритмы сортировкиЖадный алгоритмМассивы
✓ 40✗ 171800средняяВойти и решать
Бобы Айвена - 2#47480
В перерывах между отработкой заклинаний, Айвен любит лакомиться бобами. Бобы в волшебной школе имеют свою особенность. На каждом бобе написано некоторое целое число. Сегодня Айвен принес мешок, в котором лежит N бобов. Айвен хочет съесть только два боба, но такие чтобы произведение чисел, которые записаны на бобах было бы наименьшим среди всех пар бобов (пару образовывают любые два боба, лежащие в его мешке).
Определите это произведение.

Входные данные 
В первой строке вводится число N (2 ≤ N ≤105) - количество бобов в мешке Айвена, а затем N целых чисел, по одному в строке - числа, записанные на бобах, в том порядке, в котором их доставал Айвен (каждое число мо модулю не превосходит 40000).
 
Выходные данные 
Выведите ответ на задачу.
 
Примеры
№ Входные данные Выходные данные
1 3
1
-3
2		 -6
Циклы
✓ 26✗ 159800средняяВойти и решать
Контейнер артефактов#47241
Магистр Максимус отправился на поиски волшебных реликвий в глубины древнего храма. В храме находятся два вида артефактов - драгоценные камни и мистические амулеты. Камней A штук, а амулетов - B штук. Для того, чтобы вынести артефакты из храма, Максимус использует специальные контейнеры, в каждый из которых можно поместить только три артефакта. При этом в каждом контейнере должны быть артефакты обоих видов - либо два камня и один амулет, либо один камень и два амулета.
Помогите Магистру Максимусу определить, можно ли упаковать все имеющиеся артефакты в контейнеры, и если да, то предложить подходящий способ размещения артефактов по контейнерам.


Входные данные
Программа получает на вход два целых числа A и B, записанных в отдельных строках. 1 <= A <= 109, 1 <= B <= 109.

Выходные данные
Если можно разложить все артефакты по контейнерам в соответствии с условием задачи, программа должна вывести два целых числа. Первое число равно количеству контейнеров, в которых лежит два драгоценных камня и один амулет. Второе число равно количеству контейнеров, в которых лежит один драгоценный камень и два амулета. 
Если разложить все артефакты по контейнерам нужным способом нельзя, программа должна вывести одно число -1.
 
Примеры
№ Входные данные Выходные данные
1 4
5		 1 2
2 5
3		 -1
Условный оператор
✓ 42✗ 238800средняяВойти и решать
Не летное положение#47204

Три скворца сидят на ветке дерева. Ветку дерева будем считать числовой прямой. С учетом этого, можно сказать, что скворцы сидят в трёх разных точках с целочисленными координатами a, b, c. Когда скорцам становится скучно, один из крайних скворцов перелетает на другое место (скворец считается крайним, если слева или справа нет другого скворца). Причем, из-за того, что скворцы не хотят улетать друг от друга слишком далеко, скворец, который решил сменить положение, перелетает только в целочисленную точку между двумя другими скворцами, если такая есть. Скворцы могут менять свое положение до тех пор пока их положение не станет "не летным". "Не летным" называется положение, при котором ни один из скорцов не может перелететь и сесть между двумя другими в целочисленную точку. 

По начальному положению скворцов определите минимальное и максимальное число перелетов, которые могут совершить скворцы, пока не попадут в какое-нибудь "не летное" положение.



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

В трёх строках заданы три различных целых числа - a, b, c (1 <= a, b, c <= 1018), исходные позиции скворцов.


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

Выведите два числа -  минимальное и максимальное число перелетов, за которое скворцы могут достичь "не летного" положения.

  
Примеры
№ Входные данные Выходные данные
1 
1
3
4
 
1
1
2 
1
10
2
 
2
7
3 
1
2
3
 
0
0
4 
2
1
5
 
2
2
Разбор случаев
✓ 23✗ 1821 000средняяВойти и решать
Волшебные строки#47187

Магистр Аркадий очень любит работать со строками и превращать одни строки в другие. Он считает, что две строки s и t являются "магическими", если символы в s можно заменить таким образом, чтобы получилась строка t. При этом, все вхождения символа заменяются на другой символ с сохранением порядка следования символов. НО, никакие два символа не могут быть заменены на один и тот же символ. Однако символ может быть заменен на самого себя.

Входные данные
Программа получает на вход две строки s и t.

Ограничения

  • 1 <= Длина строки s <= 5 * 104
  • Длина строки s = Длина строки t
  • s и t состоят из любых допустимых ASCII символов



Выходные данные
Выведите YES, если данные строки "магические" и NO в противном случае. Вы можете можете выводить ответ в любом регистре.
 

Примеры
№ Входные данные Выходные данные
1 
egg
add
 
YES
1 
foo
bar
 NO
Словари
✓ 19✗ 203900средняяВойти и решать
Сортировка строки по частоте букв#46034
Дана строка s. Отсортируйте символы данной строки в порядке убывания частоты встречаемости. Частота встречаемости символа - это количество раз, которое данный символ встречается в строке.

Выведите отсортированную строку. Если два символа встречаются одинаковое количество раз, то они должны идти в лексикографическом порядке.

Входные данные
Программа получает на вход

Ограничения
1 <= s.length <= 5 * 105 (s.length - длина строки s)
s содержит большие и маленькие английские буквы и цифры.


Выходные данные
Выведите отсортированную строку.
 
 
Примеры
№ Входные данные Выходные данные
1 
tree
 
eert
2 
cccaaa
 
aaaccc
3 
Aabb
 
bbAa
Сортировка подсчетомСтроки
✓ 52✗ 186800средняяВойти и решать
Два массива - 2#45460
Алиса со своим отцом профессором Селезневым записывают на листочке числа. Алиса записала n чисел, профессор Селезнев - m чисел. Алиса и профессор будут рады, если они записали одни и те же числа (без учета кратности). Помогите им определить это, так как им необходимо срочно улетать в очередное космическое путешествие. 
 
Входные данные
В первой строке содержится число n  (1 <= n <= 100000) - количество чисел, записанных Алисой. Во второй строке идет n целых чисел, не превосходящих по модулю 109 – числа Алисы. Третья строка содержит целое число m - количество чисел, записанных профессором Селезневым (1 <= m <= 100000) . В четвертой строке идет m целых чисел, не превосходящих по модулю 109 – числа профессора Селезнева.
 
Выходные данные
Выведите YES, если профессор и Алиса записали одни и те же числа, и слово NO в противном случае.
 
 
Примеры
№ Входные данные Выходные данные
1 3
2 0 7
4
2 0 0 7		 YES
Одномерные массивыСортировка слиянием
✓ 144✗ 959800средняяВойти и решать
Путешествие ферзя#44711
Алиса часто играет в шахматы. Причем так как она любит путешествовать по другим галактикам, она знает много разновидностей этой древней игры.  Иногда она просто решает головоломки, созданные на шахматной доске.  Шахматная доска Алисы может иметь самые разные размеры, не только 8×8.
Сейчас Алиса решает шахматную головоломку, суть которой заключается в следующем. На одно из полей доски размером m×n записывается некоторое положительное целое число и затем на него ставится ферзь. После этого ферзь делает k ходов. Ходит ферзь по стандартным шахматным правилам. Ферзь не может ходить на поля, на которых уже был. Также, перед там как выполнить ход, на выбранном поле пишется целое число, причем такое, что оно больше всех других чисел, уже записанных на доске.
Решение головоломки заключается в том, чтобы восстановить маршрут ферзя по числам, записанным на доске. Возможно записанные числа не дают решения. 
Для решения этой головоломки Алиса написала программу, которая может быстро ее решать при больших значениях m, n и k. 
Напишите и вы такую программу. 

В стандартных шахматных правилах ферзь может переместиться на любое поле доски, находящееся на одной вертикали, горизонтали или диагонали с тем полем, на котором он находится.

Входные данные
В первой строке вводятся числа m, n и k ( 1< = m, n <= 300, 0 <= k <  mn). Следующие m строк содержат по k целых чисел и описывают поля доски (пустому полю соответствует число 0, а полю, на котором записано число – это число). Все числа, записанные на доске, положительные, целые и не превышают 109.

Выходные данные
Если головоломка составлена с ошибкой и  записанные на ней числа не дают решения, то вывелите «Wrong Board».
В противном случае выведите m строк по n чисел – для каждого поля выведите номер хода, перед которым ферзь побывал на этом поле, а для последнего поля, на котором он оказался – число k + 1. Для полей, на которые ферзь не попадал, выведите число 0.
 
Примеры
№ Входные данные Выходные данные
1 
4 4 7
10 20 0 100
30 0 0 40
0 0 0 0
45 42 0 70
 
1 2 0 8 
3 0 0 4 
0 0 0 0 
6 5 0 7
2 
2 4 4
10 20 30 40
0 50 0 0
 
Wrong Board
3 
2 2 2
1 2
4 3
 
Wrong Board
Двумерные массивы
✓ 4✗ 361 100средняяВойти и решать
Седловая точка#44616

Седловая точка – это элемент матрицы, который одновременно является наибольшим в своем столбце и наименьшим в своей строке. Напишите программу, которая находит индексы всех седловых точек матрицы. Нумерация строк и столбцов матрицы начинается с единицы.

 

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

В первой строке записаны через пробел размеры прямоугольной матрицы N и N (количество строк и количество столбцов, 1  <= N, M <=  100). В следующих N строках записаны строки матрицы, в каждой – по M натуральных чисел, разделённых пробелами.
 

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

Программа должна вывести индексы всех седловых точек матрицы в порядке обхода по строкам (сверху вниз, слева направо). Номер строки и номер столбца каждой седловой точки разделяются пробелами. Нумерация начинается с единицы. Если в матрице нет ни одной седловой точки, нужно вывести число 0.

 
Примеры
№ Входные данные Выходные данные
1 
4 5
1 2 3 4 5
6 7 8 9 10
11 12 13 14 15
9 17 18 19 20
 
3 1
Двумерные массивы
✓ 15✗ 40800средняяВойти и решать
Максимальный XOR#44583

Два числа a и b записаны в двоичной системе счисления. Запись обоих имеет длину 2n. Обе записи разбиты на n блоков по 2 стоящие рядом цифры. В каждом из чисел вы можете сколько угодно раз менять два произвольных блока местами. Какое максимальное значение может быть у результата применения побитовой операции XOR к получившимся числам?

Определим операцию побитового исключающего «ИЛИ» (XOR). Пусть даны два целых неотрицательных двоичных числа x и y длины k (возможно с ведущими нулями): xk-1...x2x1x0 и yk-1...y2y1y0. Здесь xi это i-й бит числа x, а yi это i-й бит числа y. Пусть r = x XOR y - результат операции XOR над числами x и y. Тогда двоичной записью r будет rk-1...r2r1r0, где:  

\(r_i = \begin{cases} 1, ~ \text{если} ~ x_i ~ \neq ~ y_i \\ 0, ~ \text{если} ~ x_i ~ = ~ y_i \end{cases}\)



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

В первой строке содержится одно целое число n (1 <= n <= 100000) - количество блоков по две цифры в записях обоих числах. Во второй строке задана запись числа a. В третьей строке задана запись числа b.

Для удобства блоки разделены символом «|».


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

В единственной строке вам необходимо вывести одно двоичное число из n блоков, которое является ответом на задачу, в таком же блочном формате, в каком заданы числа a и b.


Примечание

В первом примере можно поменять два соседних блока в первом числе, получится 11|00  XOR  00|10=11|10.

Во втором примере любая перестановка цифр не меняет a  XOR  b. Обратите внимание, что длина выводимого числа должна состоять из n блоков, поэтому надо выводить блоки из лидирующих нулей.

В третьем примере можно получить 101001 из a и 010100 из b.

 

Примеры
№ Входные данные Выходные данные
1 
2
00|11
00|10
 
11|10
2 
3
00|00|00
00|00|00
 
00|00|00
3 
3
10|10|01
00|01|01
 
11|11|01
Битовые операции
✓ 1✗ 31 000средняяВойти и решать
2022#44582

Эвелине на Новый год подарили массив a из n неотрицательных целых чисел, каждое из которых не превосходит 2022. Её заинтересовал вопрос, сколько в этом массиве существует различных пар индексов, у которых первый индекс в паре меньше второго, таких, что сумма соответствующих элементов массива равна 2022. Формально, она хочет понять, сколько существует пар 1 <= i,j <= n, для которых выполняется ai+aj=2022.

Уже наступил февраль, а Эвелина все еще не успела посчитать ответ на вопрос, потому что массив слишком большой. Но она смогла запомнить его и рассказала о своем массиве вам, чтобы получить помощь с поиском ответа.



Входные данные
В первой строке содержится одно целое число n (1 <= n <= 100000) - количество элементов массива. Во второй строке заданы n целых чисел a1, a2, ..., an (0 <= ai <= 2022) - элементы массива Эвелины.

Выходные данные
Выведите одно число - количество подходящих пар.

Примечание

В первом примере не существует пар с суммой 2022.

Во втором подходят пары (1, 2), (3, 4).

В третьем примере подходят все пары (2, 4), (2, 5), (3, 4), (3, 5). 

 
Примеры
№ Входные данные Выходные данные
1 
2
1 2022
 
0
2 
4
1000 1022 1001 1021
 
2
3 
5
700 1 1 2021 2021
 
4
Алгоритмы обработкиБинарный поиск в массивеИспользование сортировки
✓ 5✗ 22900средняяВойти и решать
Минимальная OR сумма#44571

Громозека записал на листочек n чисел ai. Затем он выполняет над массивом следующую операцию

  • выбирает два различных целых числа i, j (1 <= i < j <= n) и заменяет ai на x и aj на y. Чтобы не нарушать массив, Громозека следить чтобы выполнялось условия ai|aj=x|y, где | обозначает побитовое ИЛИ. Заметьте, что x и y это целые неотрицательные числа.

Громозека хочет определить минимальную сумму элементов массива, которую он может получить после выполнения вышеуказанной операции любое количество раз. Так как Громозека должен как можно быстрее отправиться в очередное космическое путешествие, он просит у вас помощи!


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

Первая строка  входных данных содержит целое число n (2 <= n <= 100) -  количество чисел, которые записал Громоезка на листочке. Вторая строка входных данных содержит n целых чисел a1,a2,…,an (0<=ai<=230).


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

Выведите минимальную возможную сумму массива.



Примеры
№ Входные данные Выходные данные
1 
3
1 3 2
 
3
2 
5
1 2 4 8 16
 
31
3 
2
6 6
 
6
4 
3
3 5 6
 
7
 
Битовые операции
✓ 39✗ 37800средняяВойти и решать
Лягушки#44504

Три лягушки сидят на числовой прямой в трёх различных точках с целочисленными координатами a, b, c. Лягушки боятся отступать слишком далеко друг от друга, поэтому прыгать может только одна из крайних лягушек (такая, что слева или справа от нее нет других лягушек) и только в целочисленную точку между двумя другими лягушками, если такая есть. Заметим, что в некоторых положениях ни одна из лягушек прыгнуть не может, назовем их стабильными .

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



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

В трёх строках заданы три различных целых числа - a, b, c (1 <= a, b, c <= 1018), исходные позиции лягушек.

Обратите внимание, что входные данные могут быть больше, чем возможное значение 32-битной целочисленной переменной, поэтому необходимо использовать 64-битные целочисленные типы данных (тип int64 в языке Pascal, тип long long в C и C++, тип long в Java и C#). Язык Python будет корректно работать и с типом int.


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

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

 

Примечание

В первом примере из условия лягушка с позиции 4 может прыгнуть на позицию 2 и образовать стабильное положение (1,2,3). Можно показать, что больше одного прыжка они сделать не смогут.

Во втором тесте из условия лягушка с позиции 1 может прыгнуть на позицию 4, а затем лягушка с позиции 10 может прыгнуть на позицию 3, тем самым придя в стабильное положение (2,3,4) за два прыжка. Можно показать, что больше 7 прыжков по описанным правилам лягушки сделать не могли.

В третьем тесте из условия лягушки уже находятся в стабильном положении, поэтому прыгать не смогут.

В четвёртом тесте из условия лягушка с позиции 1 может прыгнуть на позицию 4, а затем лягушка с позиции 5 может прыгнуть на позицию 3, тем самым придя в положение (2,3,4) за два прыжка. Можно показать, что больше двух прыжков лягушки сделать не могли.

 
Примеры
№ Входные данные Выходные данные
1 
1
3
4
 
1
1
2 
1
10
2
 
2
7
3 
1
2
3
 
0
0
4 
2
1
5
 
2
2
Разбор случаев
✓ 50✗ 94900средняяВойти и решать
Волшебник ORZ#44389

Волшебник ORZ любит колдовать над числами. Вы решили проверить его силу и дали ему массив a, состоящий из n целых чисел, а также целое число z. Нумерация элементов массива начинается с 1.

Волшебник ORZ проделывает следующую операцию любое количество (возможно, ноль) раз:

  • Он выбирает целое число i, такое что 1<= i <= n. Затем он шепчет заклинание и после этого одновременно число  ai превращается в число равное (ai or z), а число z превращается в число, равное (ai and z). 


Здесь or и and обозначают операции побитового ИЛИ и побитового И соответственно.

Найдите максимально возможное значение максимального элемента в массиве a после некоторого (возможно, нулевого) количества превращений.


Входные данные
Первая строка набора входных данных содержит два целых числа: n и z (1 <= n <= 2000, 0 <= z < 230). Вторая строка набора входных данных содержит n целых чисел: a1, a2,...,an (0 <= ai < 230). Гарантируется, что сумма значений n по всем наборам входных данных не превосходит 104.

Выходные данные
Выведите ответ на задачу.
 
 
Примеры
№ Входные данные Выходные данные Примечание
1 2 3
3 4		 7

Одной из оптимальных последовательностей действий является следующая:

  • Выполнить операцию для i = 1. Теперь a1 становится равным (3 or 3) = 3, а z становится равным (3 and 3) = 3.
  • Выполнить операцию для i = 2. Теперь a2 становится равным (4 or 3) = 7,, а z становится равным (3 and 3) = 0.
  • Выполнить операцию для i = 1. Теперь a1 становится равным (3 or 0) = 3, а z становится равным (3 and 0) = 0.

После этих операций последовательность a становится равной [3,7], и максимальное значение в ней равно 7. Можно доказать, что максимальное значение в a не может превосходить 7 ни при какой последовательности операций, так что ответ равен 7.
2 5 5
0 2 4 6 8		 13  
Битовые операции
✓ 19✗ 36800средняяВойти и решать
Заказ в магазине#44273
Решив запастись ручками на весь новый учебный год, Игорь подсчитал, что ему нужно M ручек.
В его любимом интернет-магазине есть удобная функция — он может сразу добавить в заказ упаковку из любого числа ручек от 1 до N. Правда, оказалось, что нельзя добавить в заказ две упаковки одного размера. Например, если Игорю нужно купить M = 12 ручек, а максимальное число ручек в упаковке N = 10, то Игорь может добавить в заказ упаковку из 7 ручек и упаковку из 5 ручек, но не сможет добавить две упаковки из 6 ручек.
Сформируйте заказ на M ручек, используя минимальное число различных упаковок.

Входные данные
Первая строка входных данных содержит число N — максимальный размер одной упаковки (1 ≤ N ≤ 109 ). Вторая строка входных данных содержит целое число M — необходимое количество ручек в заказе (1 ≤ M ≤ 109 ).

Выходные данные
Программа должна вывести одно или несколько чисел от 1 до N — размеры выбранных упаковок в любом порядке. Есть имеется несколько возможных решений, то выведите любое из них. Если решения не существует, необходимо вывести одно число «0».
Примеры
№ Входные данные Выходные данные
1 10
12		 5
7
2 2
5		 0
Вывод формулыЖадный алгоритм
✓ 51✗ 226900средняяВойти и решать
44199#44199
Математической моделью является:

1) модель автомобиля;
2) сборник правил дорожного движения;
3) формула закона всемирного тяготения;
4) номенклатура списка товаров на складе.
Вывод формулы
800лёгкаяВойти и решать
Поделиться
Класснуть