Темы --> Информатика --> Алгоритмы
    Задачи на моделирование(78 задач)
    Арифметические алгоритмы(240 задач)
    Алгоритмы поиска(155 задач)
    Алгоритмы сортировки(194 задач)
    Динамическое программирование(355 задач)
    Алгоритмы на графах(319 задач)
    Перебор(154 задач)
    Игры и выигрышные стратегии(33 задач)
    Вычислительная геометрия(216 задач)
    Эвристические методы(30 задач)
    Алгоритмы на строках(45 задач)
    Пересечение множеств(10 задач)
    Жадный алгоритм(71 задач)
    Теория расписаний(5 задач)
    Обработка текста(31 задач)
    Дата и время(14 задач)
---> 405 задач <---
Источники --> Личные олимпиады
    Олимпиады сайта(17 задач)
    Школьная личная олимпиада ФМШ №2007 г. Москвы(7 задач)
    Золотая середина (Новосибирск)(10 задач)
    Нижегородская олимпиада школьников(42 задач)
    Московская олимпиада школьников(168 задач)
    Индивидуальная олимпиада по информатике и программированию (ИОИП)(22 задач)
    Открытая олимпиада школьников(173 задач)
    Украинские олимпиады(61 задач)
    Республиканская олимпиада школьников (Беларусь)(6 задач)
    Жаутыковские олимпиады(8 задач)
    Всероссийская олимпиада школьников(304 задач)
    Международные олимпиады(32 задач)
    Central European Olympiad in Informatics (4 задач)
    Интернет-олимпиады(2 задач)
    COCI(36 задач)
    Турнир Архимеда(36 задач)
    Baltic Olympiad in Informatics(10 задач)
Страница: << 31 32 33 34 35 36 37 >> Отображать по:
#1355
Векторы
  

На плоскости задано множество точек (x, y), где x, y – целые числа, 1≤x≤M, 1≤y≤N. Из каждой точки выходит ровно один из следующих векторов: (-1,-1), (-1,0), (-1,1), (0,1), (1,1), (1,0), (1,-1), (0,-1). Каждый вектор соединяет одну целочисленную точку плоскости с другой. Например, если из точке (2, 5) выходит вектор (1, 1), то он соединяет эту точку с (3, 6), но не наоборот.

Последовательность из двух и более точек плоскости a1, a2,…, ak назовем циклом, если каждая точка ai соединена вектором с ai+1 (1≤i≤k-1), и ak соединена вектором с a1. Циклы считаются разными если они отличаются хотя бы одной вершиной.

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

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

Первая строка входного файла содержит два целых числа N (1≤N≤100) и M (1≤M≤100). Каждая из последующих N строк, содержит M пар чисел (т.е. 2≤M чисел). Пара x, которая находится в строке y, задает вектор в точке (x, y).

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

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

Примеры
Входные данные
2 4 
-1 1 -1 1 -1 0 0 1
1 0 1 0 0 -1 0 -1
Выходные данные
2
#1358
Работники
  
Темы: [Перебор]
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

На заводе каждая из N деталей может быть обработанной на одном из двух станков: A или B. Каждая деталь имеет порядковый номер от 1 до N. К обработке детали поступают последовательно, в соответствии со своими номерами. Количество деталей всегда четно.

Существуют правила, по которым определяется можно ли обрабатывать деталь на определенном станке.

  1. Если на текущий момент на станке B было обработано такое же количество деталей, как и на станке A, то следующая деталь должна быть обработана на станке A.
  2. В итоге на каждом из станков должно быть обработано одинаковое количество деталей.

Сколько людей, столько и мнений. Каждый из работников этого завода предложил свою последовательность обработки деталей, причем все предложения оказались разными, но удовлетворяющими правилам 1 и 2.

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

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

Единственная строка входного файла содержит четное число N (2≤N≤28) – количество деталей которое необходимо обработать.

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

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

Комментарий к примеру тестов

Первый работник считает, что на станке A необходимо обработать детали 1 и 2, а на станке B, соответственно, 3 и 4. Второй думает, что на станке A нужно обработать детали 1 и 3, а на станке B – детали 2 и 4. Других вариантов последовательности обработки не существует.

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

Робот движется по полю, которое состоит из N клеток, выстроенных в ряд. На каждой из клеток находится кубик определенного цвета.

До начала движения робот находится на первой клетке поля и не держит ни одного кубика. Находясь на клетке, робот может выполнить не более одного раза каждую из следующих операций: (1) положить кубик того же цвета, который лежит на текущей клетке; (2) поднять с клетки тот кубик, который находился там сначала. После этого робот перемещается на следующую клетку или останавливается, если текущая клетка последняя в поле.

Одновременно робот может держать не более K кубиков. На момент остановки робот не должен держать ни одного кубика.

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

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

Первая строка входного файла содержит символьную строку длинны N (1≤N≤1000). Строка состоит из маленьких букв латинского алфавита. Каждая буква соответствует клетке поля и определяет цвет кубика, который находится в этой клетке. Вторая строка содержит ограничение на количество кубиков, которое одновременно может держать робот K (1≤K≤25).

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

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

Подзадачи и система оценки

Баллы за эту задачу будут начислены если ваше решение проходит все тесты

Примеры
Входные данные
rgbbggrmcm
2
Выходные данные
4
#1360
Зал круглых столов
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

Единственный способ попасть в Зал Круглых Столов – пройти через Колонный Коридор. Стены Коридора изображаются на карте прямыми линиями, которые параллельны оси OY системы координат. Вход в Коридор находится снизу, а выход из Коридора в Зал – сверху. В Коридоре есть цилиндрические (на карте круглые) Колонны одинакового радиуса R.

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

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

В первой строке входного файла заданы два числа XL и XR – x-координаты левой и правой стен Коридора. Во второй строке находится целое число R (1≤R≤1 000 000) – радиус всех Колонн. В третей – целое число N (1≤N≤200), которое задает количество Колонн. Далее следуют N строк, в каждой из которых по два числа – x- и y-координаты центра соответствующей Колонны.

Все входные координаты – целые числа, которые по модулю не превосходят 1 000 000.

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

Единственная строка выходного файла должна содержать одно число – искомый диаметр наибольшего Стола. Диаметр следует выводить с точностью 3 знака после десятичной точки (даже в случае, когда он окажется целым). Если нельзя пронести ни одного Стола, то ответ должен быть: 0.000

Точность 3 знака после точки, по обычным правилам округления, обозначает, что ответ, который выдается в выходной файл, должен отличаться от точного не более чем на 510-4 (т.е. на 0.0005). Например, если точный ответ 1.234567, то в файле должно находится число 1.235. Если точный ответ 5.0005, то необходимо округлять в большую сторону, т.е. в файл следует выдать 5.001

Примеры
Входные данные
0 90
3
4
10 10
70 10
50 50
10 90
Выходные данные
47.000
#1373
Изобретательный Петя
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes
Требуется определить количество вхождений подстроки в строку.

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

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

  • сколько угодно раз напечатать сообщение X
  • разобрать хитроумное устройство и посимвольно напечатать еще что-нибудь (назовем это Y)
  • оторвать и выбросить начало ленты так, чтобы на оставшейся ленте было напечатано в точности сообщение Z

Поскольку набирать отдельные символы сообщения Y довольно сложно, Петя хочет, чтобы в сообщении Y было как можно меньше символов.

Для лучшего понимания задачи смотрите примеры и пояснения к ним.

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

В первой строке вводится слово X, которое Петя может печатать с помощью хитроумного устройства сколько угодно раз. Во второй строке вводится сообщение Z, которое хочет получить Петя. Каждое сообщение состоит только из маленьких латинских букв и имеет длину не более 100 символов.

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

Выведите минимальное по длине сообщение Y, которое Пете придется допечатать вручную.

Комментарии к примерам тестов

1. Сначала Петя два раза напечатает слово mama, потом к нему припечатает букву m, а затем отрежет и выбросит три начальных символа (mam). Ответом является допечатываемая отдельно буква m.

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

3. Казалось бы, Петя может напечатать слово computer, а затем отрезать и выбросить его конец — однако он не может так поступить, потому что отрезать и выбросить он может только начало ленты.

4. Пете достаточно один раз напечатать слово ejudge, а затем отрезать и выбросить букву e. Ничего посимвольно выводить ему не придется, поэтому ответом является пустая строка.

5. Достаточно трижды напечатать исходное слово и нужный результат будет получен. Ничего добавлять не надо, поэтому ответ – пустая строка.

Примеры
Входные данные
mama
amamam
Выходные данные
m
Входные данные
ura
mura
Выходные данные
mura
Входные данные
computer
comp
Выходные данные
comp
Входные данные
ejudge
judge
Выходные данные
Входные данные
m
mmm

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

                            
                                


                        

                    

                

                
        

            Страница: 
                <<
                    31
                    32
                    33
                    34
                    35
                    36
                    37
                >>
            Отображать по:
            
        

    
            

        

        
    
    

    

        

            
Выбрано
:
            
Отменить
|
            
Добавить в контест