Темы --> Информатика
    Язык программирования(952 задач)
    Алгоритмы(1657 задач)
    Структуры данных(279 задач)
    Интерактивные задачи(17 задач)
    Другое(54 задач)
---> 544 задач <---
Источники --> Личные олимпиады
    Олимпиады сайта(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 задач)
Страница: << 44 45 46 47 48 49 50 >> Отображать по:
#1372
Черепахи
  

По дороге одна за другой движутся N черепах. Каждая черепаха говорит фразу вида: “Впереди меня ai черепах, а позади меня bi черепах”. Ваша задача определить самое большее количество черепах, которые могут говорить правду.

Широко известна следующая задача для младших школьников. Три черепахи ползут по дороге. Одна черепаха говорит: “Впереди меня две черепахи”. Другая черепаха говорит: “Позади меня две черепахи”. Третья черепаха говорит: “Впереди меня две черепахи и позади меня две черепахи”. Как такое может быть? Ответ: третья черепаха врет!

По дороге одна за другой движутся N черепах. Каждая черепаха говорит фразу вида: “Впереди меня ai черепах, а позади меня bi черепах”. Ваша задача определить самое большое количество черепах, которые могут говорить правду.

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

В первой строке вводится целое число N \((1 \le N \le 10000)\). Далее следуют N строк, содержащих целые числа ai и bi, по модулю не превосходящие 10000, описывающие высказывание i-ой черепахи.

Данные о высказываниях черепах приведены в произвольном порядке, то есть первое высказывание не обязательно соответствует черепахе, идущей во главе колонны, второе - не обязательно следующей за ней и так далее

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

Выведите целое число M – максимальное количество черепах, которые могут говорить правду.

Примеры
Входные данные
3
2 0
0 2
2 2
Выходные данные
2
#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

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

                            
                                


                        

                    

                    

                        

                            

                                #1374
                            

                            

                                Снова ка-штаны
                            

                              
                
                            

                                
                                
                            


                        

                        

                            
                                Требуется найти набор, остаток от деления которого на размер рюкзака минимален. 
                            

   

 	

 
В этой задаче, как и в задаче B, Петя снова собирает своего M-лапого Зверя на прогулку (однако количество лап у Зверя в этой задаче может быть до 1000). Снова ему мама оставила N штанов, имеющих соответственно K1, K2, …, KN штанин. Однако тетерь Петя хочет надеть на Зверя штаны так, чтобы выполнялись следующие условия:
 


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

  • количество 	штанин, надетых на самую «утепленную» 	лапу, должно как можно меньше отличаться 	от количества штанин, надетых на самую 	легко одетую лапу (когда количество 	штанов, одетых на разные лапы, сильно 	отличается, Зверь испытывает дискомфорт),
    • 

  • в 	отличие от задачи B Петя не обязан надеть 	на Зверя все имеющиеся штаны — какие-то 	из них можно оставить дома.
 


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


 
Помогите Пете – напишите программу, которая для каждой лапы укажет, сколько штанин должно быть на нее надето. 
 

   


   

    

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




Вводится сначала число M, а затем число N (1 ≤ M ≤ 1000, 1 ≤ N ≤ 100). Далее вводятся N чисел Ki, обозначающих число штанин у оставленных мамой штанов (1 ≤ Ki ≤ M). Сумма всех Ki не меньше, чем M.


   


   

    

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




 
Выведите M строк, в i-ой строке должно быть выведено количество штанин, надетых на i-ю лапу. Если искомых ответов несколько, то выведите любой из них.



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



1. Первые штаны надеты на лапу 1;


вторые штаны не используем;


третьи штаны надеты на лапы 2, 3 и 4.


Таким образом, на всех лапах по 1 штанине.




2. Первые штаны надеты на лапы 1, 2 и 3;


вторые штаны надеты на лапы 1 и 4.


Таким образом, количество штанов на самой «утепленной» лапе (это лапа номер 1) – 2, а на остальных лапах по одной штанине, т.е. количество штанин на разных лапах отличается на один. Нетрудно заметить, что в этом примере нельзя одеть зверя так, чтобы на всех лапах было поровну штанин, поэтому этот ответ является оптимальным.


   

   


                            
Примеры
Входные данные
4 3
1 2 3

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

Входные данные
4 2
3 2

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


                            

                        

                    

                    

                        

                            

                                #1385
                            

                            

                                Автобусы
                            

                              
                
                            

                                
                                
                            


                        

                        

                                

                                

                                    

                                        
ограничение по времени на тест

                                        2.0 second;
                                    
                                        
ограничение по памяти на тест

                                        64 megabytes
                                    

                                

                            
                            

   


 	

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


 
В некоторый момент времени на всем участке между остановками номер X и Y (не обязательно соседними) начался ремонт дороги, из-за чего скорость движения на этом участке стала w километров в час. Скорость на ремонтируемом участке может оказаться как меньше обычной, так и больше за счет регулировщиков на этом участке дороги. При этом автобусы продолжили движение по маршруту с максимально возможной скоростью (w на ремонтируемом участке и v на остальном). Однако из-за этого интервалы движения между автобусами перестали быть равными.
 


Если какой-нибудь автобус оказался между остановками X и Y в момент начала ремонта, то он мгновенно меняет свою скорость с v на w, и едет с этой скоростью на протяжении всего ремонтируемого участка. Миновав его, он опять начинает ехать с нормальной скоростью v.


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


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

   


   

    

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



 
В единственной строке входного файла через пробел записаны целые числа L, N, M, X, Y, v, w.


 <>1 ≤ L, M, v, w ≤ 109, 2 ≤ N ≤ 109, 1 ≤ X < Y ≤ N.
 


   


   

    

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



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



 
Частичные ограничения


 
Первая группа состоит из тестов, в которых v = w.


 
Вторая группа состоит из тестов, в которых M = 2 (при этом v не обязательно равно w).


   

   


                            
Примеры
Входные данные
9 4 3 2 4 5 5

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

Входные данные
16 4 2 1 2 5 4

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

Входные данные
15 4 3 2 3 5 9

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


                            
                                


                        

                    

                    

                        

                            

                                #1386
                            

                            

                                Праздничные открытки
                            

                              
                
                            

                                
                                
                            


                        

                        

                            
                            

   

 	

 
Петя с Васей решили поздравить всех своих одноклассниц с Международным Женским Днем. Важной частью любого праздника являются открытки. Купив их достаточно, друзья сели писать пожелания. Подписанные открытки они складывали на специальный стол, расчерченный в квадратную клетку параллельно краям стола так, что длина и ширина его составляли N и M клеток соответственно. По удивительному совпадению каждая открытка была размером точь-в-точь с две клетки стола.  Петя настоял на том, чтобы класть подписанные поздравления строго по линиям сетки — горизонтально или вертикально, накрывая одной открыткой ровно две клетки.
 


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


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


   


   

    

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




В первой строке входного файла записаны два целых числа N и M (1 ≤ N, M ≤ 700) — длина и ширина стола. Гарантируется, что хотя бы одно из N, M четное. Будем считать, что все открытки занумерованы числами от 1 до NM. Следующие 2N строк содержат по M чисел: первые N строк описывают нижний слой, следующие N строк — верхний слой. Число k в i-й строке j-м столбце нижнего или верхнего слоя означает наличие на этой позиции одной из половинок открытки номер k.
 


Гарантируется, что входные данные корректны, то есть что каждое число 1 до NM встречается ровно два раза, и эти вхождения находятся на соседних позициях, при этом они могут находиться как в одном слое, так и в разных. Кроме того, если две открытки покрывают одни и те же клетки, то одна из них находится обеими половинками снизу, а другая — сверху.


   


   

    

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




В выходной файл запишите единственное слово NO, если не существует способа извлечь половину открыток нужным образом. В противном случае в первую строку выведите YES, во вторую — последовательность из NM/2 номеров открыток, которые надо достать, в правильном порядке. У каждой из них на момент извлечения хотя бы одна из половинок должна находиться сверху. Если искомых последовательностей несколько, выведите любую из них.



Частичные ограничения


 
Первая группа состоит из тестов, в которых произведение NM ≤ 24.


 
Вторая группа состоит из тестов, в которых N, M ≤ 100.
 


   

   


                            
Примеры
Входные данные
2 2
1 1
3 2
4 2
4 3

Выходные данные
YES
4
2

Входные данные
2 3
1 1 4
2 3 4
2 6 5
3 6 5

Выходные данные
YES
2
6
5


                            

                        

                    

                

                
        

            Страница: 
                <<
                    44
                    45
                    46
                    47
                    48
                    49
                    50
                >>
            Отображать по:
            
        

    
            

        

        
    
    

    

        

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