Темы
Информатика(2656 задач)
--->
228 задач
<---
#854
Темы:
[Простые задачи на перебор]
Источники:
[
Командные олимпиады,
Московская командная олимпиада,
9-11 классы,
2008,
Лига А,
Задача A
]
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes
На склад, который имеет форму прямоугольного параллелепипеда, привезли ноутбуки, упакованные в коробки. Каждая коробка также имеет форму прямоугольного параллелепипеда.
По правилам хранения коробки с ноутбуками должны быть размещены на складе с выполнением следующих двух условий:
Стороны коробок должны быть параллельны сторонам склада
Коробку при помещении на склад разрешается расположить где угодно (с выполнением предыдущего условия), в том числе на другой коробке, но все коробки должны быть ориентированы одинаково (т.е. нельзя одну коробку расположить «стоя», а другую – «лежа»)
Напишите программу, которая по размерам склада и размерам коробки с ноутбуком определит максимальное количество ноутбуков, которое может быть размещено на складе.
Входные данные
Вводится шесть натуральных чисел. Первые три задают длину, высоту и ширину склада. Следующие три задают соответственно длину, высоту и ширину коробки с ноутбуком. Каждое из чисел не превышает 1000.
Выходные данные
Выведите одно число — максимальное количество ноутбуков, которое может быть размещено на складе.
Примеры
| Входные данные | Выходные данные |
| 100 200 300 1 2 3 | 1000000 |
| 100 200 300 3 2 1 | 1000000 |
| 100 100 1 2 2 2 | 0 |
| 7 7 7 3 3 3 | 8 |
#855
Темы:
[Стек]
[Задачи на моделирование]
Источники:
[
Командные олимпиады,
Московская командная олимпиада,
9-11 классы,
2008,
Лига А,
Задача B
]
Необходимо упорядочить числа с помощью стека.
К тупику со стороны пути 1 (см. рисунок) подъехал поезд. Разрешается отцепить от поезда один или сразу несколько первых вагонов и завезти их в тупик (при желании, можно даже завезти в тупик сразу весь поезд). После этого часть из этих вагонов вывезти в сторону пути 2. После этого можно завезти в тупик еще несколько вагонов и снова часть оказавшихся вагонов вывезти в сторону пути 2. И так далее (так, что каждый вагон может лишь один раз заехать с пути 1 в тупик, а затем один раз выехать из тупика на путь 2). Заезжать в тупик с пути 2 или выезжать из тупика на путь 1 запрещается. Нельзя с пути 1 попасть на путь 2, не заезжая в тупик.
Известно, в каком порядке изначально идут вагоны поезда. Требуется с помощью указанных операций сделать так, чтобы вагоны поезда шли по порядку (сначала первый, потом второй и т.д., считая от головы поезда, едущего по пути 2 в сторону от тупика).
Входные данные
Вводится число N — количество вагонов в поезде (1≤N≤2000). Дальше идут номера вагонов в порядке от головы поезда, едущего по пути 1 в сторону тупика. Вагоны пронумерованы натуральными числами от 1 до N, каждое из которых встречается ровно один раз.
Выходные данные
Если сделать так, чтобы вагоны шли в порядке от 1 до N, считая от головы поезда, когда поезд поедет по пути 2 из тупика, можно, выведите действия, которые нужно проделать с поездом. Каждое действие описывается двумя числами: типом и количеством вагонов:
- если нужно завезти с пути 1 в тупик K вагонов, должно быть выведено сначала число 1, а затем — число K (K≥1),
- если нужно вывезти из тупика на путь 2 K вагонов, должно быть выведено сначала число 2, а затем — число K (K≥1).
Если возможно несколько последовательностей действий, приводящих к нужному результату, выведите любую из них.
Если выстроить вагоны по порядку невозможно, выведите одно число 0.
Примеры
| Входные данные | Выходные данные |
| 3 3 2 1 | 1 3 2 3 |
| 4 4 1 3 2 | 1 2 2 1 1 2 2 3 |
| 3 2 3 1 | 0 |
#856
Темы:
["Длинная" арифметика]
Источники:
[
Командные олимпиады,
Московская командная олимпиада,
9-11 классы,
2008,
Лига А,
Задача C
]
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes
Напишите программу, вычисляющую остаток от деления заданного «длинного» числа на заданную цифру.
Входные данные
В первой строке задана цифра K (1≤K≤9). Во второй строке задано натуральное число N, состоящее из не более чем 100000 цифр.
Выходные данные
Выведите остаток от деления N на K.
Примеры
| Входные данные | Выходные данные |
| 5 123456789 | 4 |
| 1 123 | 0 |
#857
Темы:
[Строки]
[Бинарный поиск в массиве]
Источники:
[
Командные олимпиады,
Московская командная олимпиада,
9-11 классы,
2008,
Лига А,
Задача D
]
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes
Учительница задала Пете домашнее задание — в заданном тексте расставить ударения в словах, после чего поручила Васе проверить это домашнее задание. Вася очень плохо знаком с данной темой, поэтому он нашел словарь, в котором указано, как ставятся ударения в словах. К сожалению, в этом словаре присутствуют не все слова. Вася решил, что в словах, которых нет в словаре, он будет считать, что Петя поставил ударения правильно, если в этом слове Петей поставлено ровно одно ударение.
Оказалось, что в некоторых словах ударение может быть поставлено больше, чем одним способом. Вася решил, что в этом случае если то, как Петя поставил ударение, соответствует одному из приведенных в словаре вариантов, он будет засчитывать это как правильную расстановку ударения, а если не соответствует, то как ошибку.
Вам дан словарь, которым пользовался Вася и домашнее задание, сданное Петей. Ваша задача — определить количество ошибок, которое в этом задании насчитает Вася.
Входные данные
Вводится сначала число N — количество слов в словаре (0≤N≤20000).
Далее идет N строк со словами из словаря. Каждое слово состоит не более чем из 30 символов. Все слова состоят из маленьких и заглавных латинских букв. В каждом слове заглавная ровно одна буква — та, на которую попадает ударение. Слова в словаре расположены в алфавитном порядке. Если есть несколько возможностей расстановки ударения в одном и том же слове, то эти варианты в словаре идут в произвольном порядке.
Далее идет упражнение, выполненное Петей. Упражнение представляет собой строку текста, суммарным объемом не более 300000 символов. Строка состоит из слов, которые разделяются между собой ровно одним пробелом. Длина каждого слова не превышает 30 символов. Все слова состоят из маленьких и заглавных латинских букв (заглавными обозначены те буквы, над которыми Петя поставил ударение). Петя мог по ошибке в каком-то слове поставить более одного ударения или не поставить ударения вовсе.
Выходные данные
Выведите количество ошибок в Петином тексте, которые найдет Вася.
Примеры
| Входные данные | Выходные данные | Комментарии |
| 4 cAnnot cannOt fOund pAge thE pAge cAnnot be fouNd | 2 | В слове cannot, согласно словарю возможно два варианта расстановки ударения. Эти варианты в словаре могут быть перечислены в любом порядке (т.е. как сначала cAnnot, а потом cannOt, так и наоборот). Две ошибки, совершенные Петей — это слова be (ударение вообще не поставлено) и fouNd (ударение поставлено неверно). Слово thE отсутствует в словаре, но поскольку в нем Петя поставил ровно одно ударение, признается верным. |
| 4 cAnnot cannOt fOund pAge The PAGE cannot be found | 4 | Неверно расставлены ударения во всех словах, кроме The (оно отсутствует в словаре, в нем поставлено ровно одно ударение). В остальных словах либо ударные все буквы (в слове PAGE), либо не поставлено ни одного ударения. |
#858
Темы:
[Способы задания графа]
[Обход в глубину]
Источники:
[
Командные олимпиады,
Московская командная олимпиада,
9-11 классы,
2008,
Лига А,
Задача E
]
Подсчет количества циклов в графе, где у каждой вершины ровно одно исходящее ребро.
У Васи есть N свинок-копилок, свинки занумерованы числами от 1 до N. Каждая копилка может быть открыта единственным соответствующим ей ключом или разбита.
Вася положил ключи в некоторые из копилок (он помнит, какой ключ лежит в какой из копилок). Теперь Вася собрался купить машину, а для этого ему нужно достать деньги из всех копилок. При этом он хочет разбить как можно меньшее количество копилок (ведь ему еще нужно копить деньги на квартиру, дачу, вертолет…). Помогите Васе определить, какое минимальное количество копилок нужно разбить.
Входные данные
В первой строке содержится число N — количество свинок-копилок (1≤N≤100000). Далее идет N строк с описанием того, где лежит ключ от какой копилки: в i-ой из этих строк записан номер копилки, в которой находится ключ от i-ой копилки.
Выходные данные
Выведите единственное число: минимальное количество копилок, которые необходимо разбить.
Пример
| Входные данные | Выходные данные | Комментарий |
| 4 2 1 2 4 | 2 | Ключи от первой и третьей копилки лежат в копилке 2, ключ от второй — в первой, а от четвертой — в ней самой. Чтобы открыть все копилки, достаточно разбить, например, копилки с номерами 1 и 4. |
Выбрано
:
|