Олимпиады по информатике (ХМАО - Югра)

   
 
Югорский НИИ ИТ, Югорский ФМЛ
Логин:   Пароль:    
 
   
 
Новости
О проекте
Регистрация
Гостевая книга
Форум
Архив задач
Состояние системы
Олимпиады
Работа в системе
Рейтинг
Новичкам
Методическое пособие
Дистанционное обучение
Дистрибутивы
Ссылки

HotLog

[Расписание] [Архив] [Содержание] [Задачи] [Рейтинг]

Задачи олимпиады "Олимпиада, посвящённая Дню программиста"

Задача A. Бисер

(Время: 1 сек. Память: 16 Мб)

В шкатулке хранится разноцветный бисер (или бусины). Все бусины имеют одинаковую форму, размер и вес. Бусины могут быть одного из N различных цветов. В шкатулке много бусин каждого цвета.

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

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

Входной файл INPUT.TXT содержит одно натуральное число N - количество цветов бусин (1 ≤ N ≤ 109).

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

В выходной файл OUTPUT.TXT выведите ответ на поставленную задачу.

Пример

INPUT.TXTOUTPUT.TXT
134

Задача B. Станки

(Время: 1 сек. Память: 16 Мб)

Есть два станка, на которых выпускают одинаковые запчасти. Один производит A запчастей в час, другой – В запчастей в час.

Найдите минимальное время (в часах), необходимое для выпуска N запчастей. При этом можно использовать как один станок, так и оба одновременно.

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

Входной файл INPUT.TXT содержит три натуральных числа: N, A и B (1 ≤ N, A, B ≤ 109).

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

В выходной файл OUTPUT.TXT выведите целое число – минимальное время (в часах), необходимое для выпуска N запчастей.

Примеры

INPUT.TXTOUTPUT.TXT
110 2 32
25 1 13

Задача C. Паркет - 2

(Время: 1 сек. Память: 16 Мб)

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

Напоминание: правильный многоугольник – это выпуклый многоугольник, у которого все стороны равны между собой и все углы равны между собой.

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

Входной файл INPUT.TXT содержит целое число N – количество вершин в правильном многоугольнике (3 ≤ N ≤ 1000).

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

В выходной файл OUTPUT.TXT выведите «YES», если плоскость можно замостить и «NO» в противном случае.

Примеры

INPUT.TXTOUTPUT.TXT
14YES
25NO

Задача D. Шахматное поле

(Время: 1 сек. Память: 16 Мб)

На стандартной шахматной доске 8х8 заданы координаты двух клеток. Требуется определить: имеют ли данные клетки одинаковый цвет?

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

Входной файл INPUT.TXT содержит целые числа x1, y1, x2, y2, описывающие координаты двух клеток (x1,y1) и (x2,y2). Ограничения: 1 ≤ x1,y1,x2,y2 ≤ 8.

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

В выходной файл OUTPUT.TXT выведите YES, если поля одного цвета, или слово NO в противном случае.

Примеры

INPUT.TXTOUTPUT.TXT
11 1 4 4YES
21 2 7 5NO

Задача E. Обратное число

(Время: 1 сек. Память: 16 Мб)

Назовем обратным числом для натурального числа N число, получающееся по следующему правилу:

  1. число N записывают в двоичной системе счисления;
  2. все нули заменяют на единицы, а единицы – на нули;
  3. результат переводится в десятичную систему счисления.

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

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

Входной файл INPUT.TXT содержит натуральное число N (N ≤ 1018) в десятичной системе счисления.

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

В выходной файл OUTPUT.TXT выведите обратное число для числа N в десятичной системе счисления.

Примеры

INPUT.TXTOUTPUT.TXT
152
2123
3238
487
5100000000073741823

Задача F. Коллекция

(Время: 1 сек. Память: 16 Мб)

Рассеянный учёный с мировым именем Василий изобрёл числодробилку. Принцип действия этого революционного изобретения довольно прост: оно превращает любое число в список всех его делителей, кроме него самого.

К сожалению, по рассеянности Василий поместил в числодробилку свою великолепную коллекцию составных чисел. Сами числа бесследно пропали, но у Василия остались списки их делителей.

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

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

Первая строка входного файла INPUT.TXT содержит одно натуральное число N (N ≥ 2). Во второй строке содержатся N натуральных чисел Ai – список всех делителей искомого числа K.

Гарантируется, что K – составное число, не превышающее 109.

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

В выходной файл OUTPUT.TXT выведите единственное целое число K – восстановленное по своим делителям число.

Примеры

INPUT.TXTOUTPUT.TXT
19
2 12 8 1 24 4 6 16 3
48
28
2 25 20 1 4 5 10 50
100

Задача G. Вася и отрезки

(Время: 1 сек. Память: 16 Мб)

Вася очень любит решать задачи на геометрию, поэтому он был очень счастлив, когда мама подарила ему на день рождения отрезок AB. Он начал с ним играть, и вскоре у него возник вопрос, можно ли найти точки D и E, которые будут лежать на равном расстоянии от точки C – середины отрезка AB, при этом отрезок DE должен быть перпендикулярен AB, проходить через точку C, а |CD|/|AB| = k.

Помогите Васе найти ответ на его вопрос.

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

Входной файл INPUT.TXT содержит координаты двух точек: Ax, Ay, Bx, By, k (0.01 ≤ k ≤ 1). Все координаты являются целыми числами и не превосходят 1000 по абсолютному значению, k задано не более, чем с двумя знаками после десятичной точки.

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

В выходной файл OUTPUT.TXT выведите координаты самой высокой точки. Если обе точки находятся на одинаковой высоте, выведите координаты самой левой из них. Координаты следует выводить с абсолютной или относительной погрешностью не хуже 10-4.

Пример

INPUT.TXTOUTPUT.TXT
10 0 2 2 0.50 2

Задача H. Число - 3

(Время: 1 сек. Память: 16 Мб)

Дано натуральное число N. Над ним можно произвести следующий набор операций:

  • вычитать единицу;
  • делить на три, если число кратно трем;
  • делить на два, если число четное.

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

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

Входной файл INPUT.TXT содержит натуральное число N (N ≤ 106).

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

В выходной файл OUTPUT.TXT выведите наименьшее количество операций, в результате выполнения которых будет получена единица.

Примеры

INPUT.TXTOUTPUT.TXT
153
210
3103

Задача I. Взвешивания

(Время: 1 сек. Память: 16 Мб)

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

Для взвешиваний используют чашечные весы и большой набор гирь 1, 3, 9, 27, 81 грамм и т.д. (для любого k ≥ 0 есть только одна гиря весом 3k грамм).

На одну из чашек весов положили груз весом N грамм. Какие гири нужно положить на левую и правую чашки, чтобы их уравновесить?

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

Входной файл INPUT.TXT содержит символ C и число N, разделенные пробелом. C - символ «L» или «R», обозначающий соответственно левую или правую чашку весов, на которой лежит груз. N – масса груза в граммах (1 ≤ N ≤ 109).

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

В выходной файл OUTPUT.TXT выведите две строки: первая строка должна начинаться с "L:", вторая – с "R:", после чего через пробел должны идти в порядке возрастания массы веса гирь, которые нужно положить на левую и правую чашу весов, соответственно.

Примеры

INPUT.TXTOUTPUT.TXT
1L 5L:1 3
R:9
2R 3L:3
R:

Задача J. Системы счисления

(Время: 1 сек. Память: 16 Мб)

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

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

Входной файл INPUT.TXT содержит целые числа A и B (1 ≤ A ≤ 109, 10 ≤ B <100), записанные в десятичной системе счисления.

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

В выходной файл OUTPUT.TXT в произвольном порядке выведите все основания систем счисления, в которых запись числа A оканчивается на десятичную запись числа B. Если таких систем нет, выведите −1.

Пример

INPUT.TXTOUTPUT.TXT
171 134 68


 
     
Югорский НИИ ИТ, Югорский ФМЛ