Темы
    Информатика(2609 задач)
---> 304 задач <---
Источники --> Личные олимпиады --> Всероссийская олимпиада школьников
    Муниципальный этап(80 задач)
    Окружная олимпиада(18 задач)
    Региональный этап(109 задач)
    Заключительный этап(97 задач)
Страница: << 1 2 3 4 5 6 7 >> Отображать по:

В целях улучшения ландшафтной архитектуры и экологической обстановки управление городского хозяйства разработало проект программы озеленения центрального проспекта. Согласно проекту, с одной стороны проспекта планируется высадить в ряд деревья K различных видов, для чего были закуплены саженцы деревьев, причем i-го вида было закуплено ai саженцев.

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

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

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

В первой строке вводятся два целых числа: K — количество различных видов деревьев (1 ≤ K ≤ 100 000), и P — требуемое количество подряд идущих деревьев разных видов (2 ≤ PK). Последующие K строк  входных данных содержат целые числа ai, задающие количество закупленных саженцев деревьев i-го вида  (1 ai 109), по одному числу в каждой строке.

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

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

Примеры
Входные данные
3 3
1
200 
1
Выходные данные
4
ограничение по времени на тест
0.0 second;
ограничение по памяти на тест
0 megabytes

Юный информатик стал исследовать, как изменяются суммы цифр натуральных чисел при умножении и делении на разные однозначные числа. Однажды он задался вопросом, можно ли восстановить число A, если нам известна сумма его цифр, а также сумма цифр числа D×A, где D — заданное однозначное число. Довольно быстро он установил, что для восстановления числа А этой информации недостаточно. Так, например, у чисел 9 и 45 одинаковые суммы цифр. Если же их умножить на 5, то получим числа 45 и 225, которые тоже имеют одинаковые суммы цифр.

Тогда юный информатик стал искать ответ на поставленный вопрос при условии, что нам известно K — количество десятичных знаков в числе A. К сожалению, и тут его ждало разочарование. У некоторых чисел, имеющих одинаковое количество цифр и одинаковые суммы цифр, после умножения на один и тот же множитель эти суммы опять оказываются одинаковыми. Такими числами, например, являются 42 и 51 при D = 3.

И тогда юный информатик поставил перед собой такую задачу: найти наименьшее K значное натуральное число A в десятичной системе счисления, которое имеет сумму цифр, равную S, а число D×A имеет сумму цифр, равную P.

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

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

Вводятся четыре натуральных числа K, S, P, D (1 K 100, 1 S 9K, 1 P ≤ 9(K+1), 1 D 9).

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

Выведите  число A, если оно существует, или –1, в противном случае. Число A не может начинаться с нуля.

Примечание

Решения, корректно работающие при K ≤ 40, будут оцениваться, исходя из 80 баллов.

Примеры
Входные данные
3 15 15 1
Выходные данные
159
ограничение по времени на тест
0.0 second;
ограничение по памяти на тест
0 megabytes

В городе Шахматовске два интернет-провайдера выполняют план по всеобщей интернетизации страны. Город расположен на бесконечной целочисленной решетке, по всем линиям которой проходят прямые улицы, а единичные квадраты сетки определяют кварталы. Координатами квартала считаются координаты вершины левого нижнего угла соответствующего единичного квадрата. Кварталы города окрашены в черный и белый цвета в шахматном порядке, при этом квартал с координатами (0, 0) окрашен в черный цвет.Интернет-провайдер «Черный интернет» занимается подключением кварталов черного цвета. Недавно стало известно, что жителям квартала, подключенного K-м, будет предоставлена скидка в 10%.

В соответствии с планом компании «Черный интернет» интернетизация будет проводиться в течение N дней. В i-й день бригада сотрудников компании движется по какой-то из улиц города, начиная из точки (xi, yi). Бригада проходит li кварталов в заданном направлении. При этом она подключает ранее не подключенные кварталы черного цвета, граничащие по стороне с путем движения бригады (см. рис.).

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

рис. 1 
Рисунок к примеру 1

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

В первой строке  задаются два целых числа N и K (1 ≤ N ≤ 2 000, 1 ≤ K ≤ 1018).

Далее следуют N строк с описанием плана развития компании. В i-й строке описания плана записан путь бригады в i-й день: xi и yi (–1015xi ≤ 1015, –1015yi ≤ 1015) — координаты начальной точки пути, символ ci — направление движения, и li (1 ≤ li ≤ 1015) — расстояние, которое пройдет бригада. Направление движения задается одним из следующих символов: «N» — север (по увеличению y-координаты), «E» — восток (по увеличению x-координаты), «S» — юг (по уменьшению y-координаты), «W» — запад (по уменьшению x-координаты).

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

Выведите  координаты x и y квартала, подключенного K-м.

Примеры
Входные данные
5 19
20 6 S 5
9 7 S 7
9 18 W 1
13 18 N 2
12 13 E 5
Выходные данные
15 13
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

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

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

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

Цель игры состоит в том, чтобы сделать как можно больше ходов.

Задана начальная расстановка фишек на доске. Требуется найти самую длинную последовательность ходов, которую может сделать Петя из заданной позиции.

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

Первая строка входного файла содержит размеры доски: два целых числа $m$ и $n$ (1 ≤ $m$, $n$ ≤ 300, хотя бы одно из этих чисел четно). Далее следуют $m$ строк по $n$ чисел в каждой, $j$-е число в $i$-й из этих строк представляет собой номер цвета $j$-й слева фишки в $i$-й горизонтали. Цвета пронумерованы натуральными числами от 1 до $n$*$m$ / 2. На доске ровно две фишки каждого цвета.

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

В первой строке выходного файла выведите $k$ — максимальное количество ходов, которое может сделать Петя из заданной начальной позиции. Во второй строке выходного файла выведите разделенные пробелами $k$ чисел — номера цветов фишек в том порядке, в котором они должны сниматься с доски. Если возможных ответов несколько, выведите любой.

Примеры
Входные данные
1 2
1 1
Выходные данные
1
1 
Входные данные
4 1
1
2
2
1
Выходные данные
2
2 1 
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

Строительная компания хочет построить дом, в котором будет $n$ квадратных комнат. Каждая комната характеризуется своим размером — длиной стены. Обозначим размеры комнат в новом доме как $a_1$, $a_2$, …, $a_n$.

При этом для того, чтобы квартиры в доме активнее распродавались, компания объявила его «Домом оригинальности и гармонии». Оригинальность означает, что размер любой комнаты не должен делиться на размер никакой другой комнаты. Свойство гармонии требует, чтобы площадь любой комнаты делилась на размер каждой из комнат. Иначе говоря, для любых различных $i$ и $j$ должны выполняться условия: $a_i$ не делится на $a_j$, а $a_i$2 делится на $a_j$.

Требуется по заданному числу n выбрать такие размеры комнат, чтобы выполнялись свойства оригинальности и гармонии. При этом с целью экономии строительных материалов размер каждой комнаты не должен превышать 263 – 1.

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

Входной файл содержит число $n$ (1 ≤ $n$ ≤ 1000).

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

Выведите в выходной файл размеры комнат — $n$ положительных целых чисел, не превосходящих 263 – 1. Разделяйте числа пробелами.

Примеры
Входные данные
2
Выходные данные
6523157998489532400
5519595229491142800

Страница: << 1 2 3 4 5 6 7 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест