Темы --> Информатика --> Алгоритмы
    Задачи на моделирование(78 задач)
    Арифметические алгоритмы(240 задач)
    Алгоритмы поиска(155 задач)
    Алгоритмы сортировки(194 задач)
    Динамическое программирование(355 задач)
    Алгоритмы на графах(319 задач)
    Перебор(154 задач)
    Игры и выигрышные стратегии(33 задач)
    Вычислительная геометрия(216 задач)
    Эвристические методы(30 задач)
    Алгоритмы на строках(45 задач)
    Пересечение множеств(10 задач)
    Жадный алгоритм(71 задач)
    Теория расписаний(5 задач)
    Обработка текста(31 задач)
    Дата и время(14 задач)
---> 264 задач <---
Источники --> Командные олимпиады
    Школьная командная олимпиада ФМШ № 2007 г.Москвы(21 задач)
    Турнир Архимеда(52 задач)
    Кировские командные турниры(8 задач)
    Барнаульские командные турниры(10 задач)
    Московская командная олимпиада(246 задач)
    Командные чемпионаты школьников Санкт-Петербурга по программированию(167 задач)
    ВКОШП(180 задач)
Страница: << 38 39 40 41 42 43 44 >> Отображать по:
#1786
Лабиринт
  

Открыв глаза, Принц Персии обнаружил, что находится на верхнем уровне подземного лабиринта Джаффара. Лабиринт состоит из \(h\) уровней, расположенных строго друг под другом. Каждый уровень представляет собой прямоугольную площадку, разбитую на \(m\) × \(n\) участков. На некоторых участках стоят колонны, поддерживающие потолок, на такие участки Принц заходить не может.

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

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

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

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

В первой строке входного файла содержатся натуральные числа \(h\), \(m\) и \(n\) – высота и горизонтальные размеры лабиринта (2 ≤ \(h\), \(m\), \(n\) ≤ 50). Далее во входном файле приведены \(h\) блоков, описывающих уровни лабиринта в порядке от верхнего к нижнему.

Каждый блок содержит \(m\) строк, по \(n\) символов в каждой: «.» (точка) обозначает свободный участок, «o» (строчная латинская буква «o») обозначает участок с колонной, «1» обозначает свободный участок, в котором оказался Принц в начале своего путешествия, «2» обозначает свободный участок, на котором томится Принцесса.

Символы «1» и «2» встречаются во входном файле ровно по одному разу: символ «1» – в описании самого верхнего уровня, а символ «2» – в описании самого нижнего.

Соседние блоки разделены одной пустой строкой.

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

В выходной файл выведите минимальное время в секундах, необходимое Принцу, чтобы найти Принцессу. Поскольку Добро всегда побеждает Зло, гарантируется, что Принц может это сделать.

Примеры
Входные данные
3 3 3
1..
oo.
...

ooo
..o
.oo

ooo
o..
o.2
Выходные данные
60
#1787
Число
  

По заданным числам \(a\), \(b\), \(c\) и \(d\), найдите наименьшее натуральное число \(n\), большее \(ac\), которое нельзя представить в виде произведения двух натуральных чисел \(u\) и \(v\), таких что \(a\) ≤ \(u\) ≤ \(b\) и \(c\) ≤ \(v\) ≤ \(d\).

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

Входной файл содержит одну строку, состоящую из натуральных чисел \(a\), \(b\), \(c\), \(d\) (1 ≤ \(a\) ≤ \(b\) ≤ \(10^6\), 1 ≤ \(c\) ≤ \(d\) ≤ \(10^6\)).

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

Выведите в выходной файл искомое число \(n\).

Примеры
Входные данные
1 2 1 2
Выходные данные
3
Входные данные
1 2 3 5
Выходные данные
7
#1788
Красивые номера
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

Вы, наверное, замечали, что многие компании используют для рекламы «красивые» номера телефонов, которые удобны для запоминания потенциальными клиентами. Но что делать, если номер вашей компании ничем не примечателен? Можно присмотреться к нему повнимательнее, а вдруг, если перегруппировать цифры номера некоторым образом, номер станет намного красивее? Например, если у вашей компании номер 872-73-33, то его можно сделать красивее, если перегруппировать цифры так: 8727-333.

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

	 
Шаблон группы          Баллы	 
aa                     2	 
aba                    2	 
aab, abb               2	 
aaa                    3	 
abac, baca             2	 
abab                   3	 
aabb                   3	 
abba                   4	 
baaa, abaa, aaba, aaab 3	 
aaaa                   5

В этой таблице символами «a», «b», «c» обозначены различные цифры. Например под шаблон «aab» подходят группы «223», «667», но не подходят «123» и «888».

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

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

Входной файл содержит одну строку из 7 цифр – заданный телефонный номер.

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

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

Если разбиений с максимальной величиной красоты несколько, выведите в выходной файл любое из этих разбиений.

Примеры
Входные данные
8727333
Выходные данные
8727-333
5
Входные данные
8827291
Выходные данные
88-272-91
4
#1789
Зоопарк
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

В городском зоопарке содержатся животные n разных видов. Для участия в международной выставке «Три твари» зоопарк должен представить трех животных различных видов. Теперь служителей зоопарка интересует, сколькими способами можно выбрать трех животных для участия в выставке.

Например, если в зоопарке два медведя, тигр, лев и пингвин, то есть семь способов выбрать трех животных:

1) первый медведь, тигр и лев;

2) первый медведь, тигр и пингвин;

3) первый медведь, лев и пингвин;

4) второй медведь, тигр и лев;

5) второй медведь, тигр и пингвин;

6) второй медведь, лев и пингвин;

7) тигр, лев и пингвин.

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

В первой строке входного файла содержится натуральное число \(n\) – количество видов животных в городском зоопарке (1 ≤ \(n\) ≤ \(10^5\)).

В каждой из следующих \(n\) строк содержится одно натуральное число – количество животных соответствующего вида. Общее число животных в зоопарке не превышает \(10^5\).

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

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

Примеры
Входные данные
4
2
1
1
1
Выходные данные
7
Входные данные
3
30000
30000
30000
Выходные данные
27000000000000
#1849
Плитки
  
Источники: [ Командные олимпиады, ВКОШП, 1999, Задача D ]
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

У Пети имеется неограниченный набор красных, синих и зеленых плиток размером 1×1. Он выбирает ровно N плиток и выкладывает их в полоску. Например, при N = 10 она может выглядеть следующим образом:


К

К

К

С

З

К

К

З

К

С


(Буквой К обозначена красная плитка, С – синяя, З – зеленая)

После этого Петя заполняет следующую таблицу:

красный

синий

зеленый

красный

Y

Y

Y

синий

Y

N

Y

зеленый

Y

Y

N


В клетке на пересечении строки, отвечающей цвету А, и столбца, отвечающего цвету Б, он записывает "Y", если в его полоске найдется место, где рядом лежат плитки цветов А и Б и "N" в противном случае. Считается, что плитки лежат рядом, если у них есть общая сторона. (Очевидно, что таблица симметрична относительно главной диагонали – если плитки цветов А и Б лежали рядом, то рядом лежали и плитки цветов Б и А.) Назовем такую таблицу диаграммой смежности данной полоски.

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

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

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


С

К

З

К

К

З

С

К

К

К


не совпадает с полоской, приведенной в начале условия.)

Формат входных данных

Первая строка входного файла содержит число N. (1 N 100). Следующие три строки входного файла, содержащие по три символа из набора {"Y", "N"}, соответствуют трем строкам диаграммы смежности. Других символов, включая пробелы, во входном файле не содержится. Входные данные корректны, т.е. диаграмма смежности симметрична.

Формат выходных данных

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

Примеры

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

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

10

YYY

YNY

YYN

4596

3

YYY

YYY

YYY

0


Страница: << 38 39 40 41 42 43 44 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест