Темы --> Информатика
    Язык программирования(952 задач)
    Алгоритмы(1657 задач)
    Структуры данных(279 задач)
    Интерактивные задачи(17 задач)
    Другое(54 задач)
---> 2656 задач <---
Источники
    Личные олимпиады(938 задач)
    Командные олимпиады(684 задач)
Страница: << 199 200 201 202 203 204 205 >> Отображать по:
#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


                            

                        

                    

                    

                        

                            

                                #1375
                            

                            

                                Острова
                            

                              
                
                            

                                
                                


                                

                            


                        

                        

                                

                                

                                    

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

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

                                        64 megabytes
                                    

                                

                            
                            

   



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


   


   

    

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




Первая строка содержит два числа: число островов N (1≤N≤10000) и количество мостов в плане M (1≤M≤50000). Далее идет M строк, каждая содержит два числа x и y (1≤x,y≤N) - номера городов, которые соединяет очередной мост в плане.
 

   


   

    

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



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


    

    


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

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


                            
                                


                        

                    

                    

                        

                            

                                #1376
                            

                            

                                Вес компоненты
                            

                              
                
                            

                                
                                


                                

                            


                        

                        

                                

                                

                                    

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

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

                                        256 megabytes
                                    

                                

                            
                            

   





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

   


   

    

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




 
В первой строке записано два числа n и m (1≤n,m≤106) - количество вершин в графе и количество производимых добавлений и запросов. Далее следует m строк с описанием добавления или запроса. Каждая строка состоит из двух или четырех чисел. Первое из чисел обозначает код операции. Если первое число 1, то за ним следует еще три числа x, y, w. Это означает, что в граф добавляется ребро из вершины x в вершину y веса w. (1≤x<y≤n, 1≤w≤103). Кратные ребра допустимы. Если первое число 2, то за ним следует ровно одно число x. Это означает, что необходимо ответить на вопрос, какова сумма ребер в компоненте связности, которой принадлежит вершина x (1≤x≤n).
  

   


   

    

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




Для каждой операции с кодом 2 выведите ответ на поставленную задачу. Ответ на каждый запрос выводите на отдельной строке.


    

    


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

Выходные данные
0
1
3
6
3
0


                            
                                


                        

                    

                

                
        

            Страница: 
                <<
                    199
                    200
                    201
                    202
                    203
                    204
                    205
                >>
            Отображать по:
            
        

    
            

        

        
    
    

    

        

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