Страница: << 64 65 66 67 68 69 70 >> Отображать по:

#111286

Темы: [НОД и алгоритм Евклида]

Источники: [ Командные олимпиады, ВКОШП, 2011, Задача A ]

Сегодня на уроке математики шестиклассник Петя изучил понятие наибольшего общего делителя. Петя тут же решил применить полученные знания на практике.

Петя выписал на листке бумаги $n$ чисел $a_1, \ldots, a_n$ --- номера домов, в которых живут его друзья. Теперь он хочет выбрать такое подмножество этих чисел, чтобы их наибольший общий делитель был равен его любимому числу $d$.

Помогите Пете выбрать из выписанных чисел искомое подмножество.

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

Первая строка входного файла содержит два целых числа $n$ и $d$ ($1 \le n \le 1000$, $1 \le d \le 10^9$). Вторая строка содержит $n$ целых чисел: $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 10^9$).

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

Если существует искомое подмножество, выведите на первой строке выходного файла число $k$ --- количество чисел в нем. На второй строке выведите числа, входящие в это подмножество.

Если решения не существует, выведите на первой строке выходного файла число $-1$.

Если возможных ответов несколько, выведите любой из них.

Примеры тестов

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

4 3
6 8 12 9

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

2
6 9

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

3 3
2 4 8

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

-1

#111288

Телефонный номер

Темы: [Динамическое программирование]

Источники: [ Командные олимпиады, ВКОШП, 2011, Задача C ]

Недавно Васе продиктовали номер телефона. Он записал его, разделив числа дефисами, но потом начал сомневаться, не ошибся ли он в записи номера. Ведь бывают различные телефонные номера, которые произносятся одинаково. Например, все четыре номера «3000-100-1», «3000-101», «3100-1», «3101» читаются как «три тысячи сто один». Теперь он хочет выяснить, какие номера произносятся также, как и записанный им номер.

Вася считает, что при произношении телефонного номера не употребляются числа, состоящие более чем из девяти цифр. Напомним, как произносятся числа от $1$ до $999\,999\,999$.

Если число больше или равно $1\,000\,000$, то сначала произносится число миллионов в мужском роде, затем слово «миллион», «миллиона» или «миллионов», по следующим правилам. Если число миллионов, взятое по модулю 100, не равно 11 и дает остаток 1 по модулю 10, то произносится слово «миллион». Если число миллионов, взятое по модулю 100, не равно 12, 13 или 14 и дает остаток 2, 3 или 4 по модулю 10, то произносится слово «миллиона». Иначе произносится слово «миллионов».

Если число по модулю $1\,000\,000$ больше или равно $1\,000$, то затем произносится число тысяч в женском роде, затем слово «тысяча», «тысячи» или «тысяч», по следующим правилам. Если число тысяч, взятое по модулю 100, не равно 11 и дает остаток 1 по модулю 10, то произносится слово «тысяча». Если число тысяч, взятое по модулю 100, не равно 12, 13 или 14 и дает остаток 2, 3 или 4 по модулю 10, то произносится слово «тысячи». Иначе произносится слово «тысяч».

Затем, если число по модулю $1\,000$ отлично от нуля, в мужском роде произносится число единиц.

Например, число $978\,121\,014$ произносится как «девятьсот семьдесят восемь миллионов сто двадцать одна тысяча четырнадцать», а число $1\,000\,142$ как «один миллион сто сорок два». Заметим, что перед словом «миллион» нельзя опускать слово «один», перед словом «тысяча» слово «одна», а числа от $11$ до $19$ произносятся одним словом.

Помогите Васе найти все телефонные номера, которые произносятся так же, как тот, который он записал.

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

На входе единственная строка, содержащая номер записанного Васей телефона. Номер телефона --- это целые числа, разделенные символом «-» (ASCII код 39). Каждое число в записи положительно, содержит не более девяти цифр и не содержит ведущих нулей. Гарантируется, что в записанном Васей номере встречается не больше 50 цифр.

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

В первой строке выведите количество телефонных номеров, которые читаются так же, как и записанный Васей номер. В следующих строках выведите эти номера телефонов. Каждый номер должен находиться в отдельной строке. Каждый номер должен состоять из чисел от 1 до $999\,999\,999$, разделенных дефисами.

Порядок телефонов в ответе не важен. Гарантируется, что количество номеров в ответе не превышает $100\,000$. Учтите, что в ответе могут встречаться и номера, составленные более чем из 50 цифр.

Примеры тестов

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

3000-101

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

#111295

Поезда

Темы: [Генерация по номеру] [Динамическое программирование]

Источники: [ Командные олимпиады, ВКОШП, 2011, Задача J ]

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

Любимым занятием Васи стала сортировка поездов с использованием специального сортировочного тупика. $\text{[math]}$

Справа к тупику подъезжает поезд, составленный из всех $n$ вагонов. Затем вагоны по одному загоняются в сортировочный тупик и выгоняются из него налево. Васе нравится, если ему удается отсортировать поезд с помощью сортировочного тупика — добиться того, чтобы слева от тупика вагоны были расположены по порядку от 1 до $n$.

Например, пусть в исходном поезде 4 вагона, которые следуют в порядке 3, 1, 2, 4. Его можно отсортировать следующим образом. Загоняем вагон 3 в тупик. Загоняем вагон 1 в тупик. Выгоняем вагон 1 из тупика. Загоняем вагон 2 в тупик. Выгоняем вагон 2 из тупика. Выгоняем вагон 3 из тупика. Загоняем вагон 4 в тупик. Выгоняем вагон 4 из тупика.

Не все поезда можно отсортировать таким образом. Например, поезд из 3 вагонов, следующих в порядке 2, 3, 1, отсортировать нельзя.

Вася выписал на листке в лексикографическом порядке все поезда длины $n$, которые можно отсортировать с помощью тупика. Поезд $(a_1, a_2, \ldots, a_n)$ идет раньше поезда $(b_1, b_2, \ldots, b_n)$ в лексикографическом порядке, если существует такое $i$ ($1 \le i \le n$), что для всех $j < i$ выполняется $a_j = b_j$, а $a_i < b_i$. Например, все поезда из трех вагонов, которые можно отсортировать с помощью тупика, в лексикографическом порядке выписываются следующим образом: $(1, 2, 3)$, $(1, 3, 2)$, $(2, 1, 3)$, $(3, 1, 2$), $(3, 2, 1)$.

Вася потерял свой листок, и его интересует вопрос: какой поезд был выписан на его листке под номером $k$. Помогите ему выяснить это.

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

Входной файл содержит два целых числа — $n$ и $k$ ($1 \le n \le 30$, $1 \le k \le 10^{18}$).

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

Выведите в выходной файл $n$ целых чисел: $k$-й в лексикографическом порядке поезд из $n$ вагонов, который можно отсортировать с помощью тупика.

Если с помощью тупика можно отсортировать менее $k$ поездов из $n$ вагонов, выведите $-1$.

Примеры тестов

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

4 1

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

1 2 3 4

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

4 3

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

1 3 2 4

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

4 15

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

-1

#111510

Простая игра

Темы: [Условный оператор (if)]

Источники: [ Командные олимпиады, Турнир Архимеда, 2012, Задача A ]

Как непросто быть школьником! Именно такие мысли чаще всего посещают Петю после уроков математики. Сегодня учительница рассказывала, что такое простые числа. Петя впервые услышал о них. Оказывается, простое число — это такое натуральное число, которое имеет ровно два различных натуральных делителя, то есть делится без остатка только на единицу и на само себя. После урока Петя и его друг Сережа придумали такую игру: один называет два числа A и B, а другой говорит, сколько нулей на конце произведения всех простых между A и B включительно. Петя заметил, что Сережа отвечает на вопрос намного быстрее, чем он сам, и очень просит вас ему помочь. Напишите для Пети программу, которая будет отвечать на вопросы Сережи.

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

На вход подается два числа A, B (1 ≤ A ≤ B ≤ 10⁹), разделенных пробелом. Гарантируется, что между A и B есть хотя бы одно простое число.

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

Выведите количество нулей, на которое заканчивается произведение всех простых чисел на отрезке от A до B.

Примеры

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

1 7

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

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

3 3

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

#111662

Красивые номера

Темы: [Хеш]

Источники: [ Командные олимпиады, Турнир Архимеда, 2013, Задача C ]

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

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

$\text{[math]}$

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

Каждая фирма хочет, чтобы ее телефонный номер было просто запомнить. Если набранное на телефоне название компании соответствует телефонному номеру компании, то номер очень легко запомнить, и ни один клиент его не забудет.

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

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

В первой строке вводится целое число N — количество новых фирм (1 ≤ N ≤ 10³).

В последующих N строках вводятся названия фирм. Название каждой фирмы состоит из семи строчных латинских букв. Гарантируется, что названия всех фирм различны.

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

Выведите одно число — максимальное количество фирм, которые смогут получить удобный номер.

Примеры

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

4
lacoste
hyundai
renault
peugeot

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

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

3
aaaaaaa
bbbbbbb
ccccccc

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

Страница: << 64 65 66 67 68 69 70 >> Отображать по:

Выбрано

Отменить

Добавить в контест