Темы --> Информатика --> Алгоритмы
    Задачи на моделирование(78 задач)
    Арифметические алгоритмы(240 задач)
    Алгоритмы поиска(155 задач)
    Алгоритмы сортировки(194 задач)
    Динамическое программирование(355 задач)
    Алгоритмы на графах(319 задач)
    Перебор(154 задач)
    Игры и выигрышные стратегии(33 задач)
    Вычислительная геометрия(216 задач)
    Эвристические методы(30 задач)
    Алгоритмы на строках(45 задач)
    Пересечение множеств(10 задач)
    Жадный алгоритм(71 задач)
    Теория расписаний(5 задач)
    Обработка текста(31 задач)
    Дата и время(14 задач)
---> 1657 задач <---
Источники
    Личные олимпиады(938 задач)
    Командные олимпиады(684 задач)
Страница: << 141 142 143 144 145 146 147 >> Отображать по:
#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


                            

                        

                    

                    

                        

                            

                                #1377
                            

                            

                                Остовное дерево
                            

                              
                
                            

                                
                                


                                

                            


                        

                        

                                

                                

                                    

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

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

                                        64 megabytes
                                    

                                

                            
                            

   




Требуется найти в связном графе остовное дерево минимально веса. 
 

   


   

    

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





Первая строка входного файла содержит два натуральных числа n и m - количество вершин и ребер графа соответственно (1≤n≤20000, 0≤m≤100000). Следующие m строк содержат описание ребер по одному на строке. Ребро номер i описывается тремя натуральными числами bi, ei и wi - номера концов ребра и его вес соответственно (1≤bi,ei≤n, 0≤wi≤100000).
 

 
Граф является связным.
  

   


   

    

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




Выведите единственное целое число - вес минимального остовного дерева.


    

    


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

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


                            
                                


                        

                    

                    

                        

                            

                                #1382
                            

                            

                                Трубочист
                            

                              
                
                            

                                
                                
                            


                        

                        

                                

                                

                                    

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

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

                                        64 megabytes
                                    

                                

                            
                                Дана последовательность чисел. Необходимо переставить все числа (кроме одного фиксированного) так, чтобы сумма модулей разностей соседних чисел была минимальна. 
                            

   

 	


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


 
Дома будут строиться вплотную друг другу, а крыши соседних домов будут соединяться лестницами (длина лестницы равна разнице высот домов), чтобы трубочист мог путешествовать по крышам и чистить трубы.


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

   


   

    

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




Во входном файле записано сначала число N (1 ≤ N ≤ 10000), затем N чисел — высоты домов до пожара (это натуральные числа от 1 до 109), и затем K — номер уцелевшего дома.
 

   


   

    

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




В выходной файл выведите высоты домов в таком порядке, чтобы выполнялось требование Главного Трубочиста. Обратите внимание, что K-ый дом (уцелевший) перестраивать не нужно (и следовательно его высота должна остаться прежней).


   



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

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


   


                            
                            
                                


                        

                    

                    

                        

                            

                                #1384
                            

                            

                                Репортаж
                            

                              
                
                            

                                
                                
                            


                        

                        

                                

                                

                                    

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

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

                                        64 megabytes
                                    

                                

                            
                                Для N дней заданы высоты. Требуется выделить максимальное подмножество дней нечетной длины (2K+1), так что бы впервые K дней высота увеличивалась,на K+1 день был достигнут максимум, а в оставшиеся дни высота уменьшалась. 
                            

   

 	


Группа альпинистов покорила много вершин и возвратилась в родной город. Одна из местных газет решила написать статью об их походе. Как выяснилось, в процессе похода альпинисты N раз останавливались на ночлег на той или иной высоте hi. Поскольку главный редактор газеты настаивает, чтобы название статьи было «Восхождение и спуск», решено было не упоминать о некоторых днях похода, рассказав лишь о 2k+1 дне, причем если статья будет рассказывать о x1-ом, x2-ом, …, x2k+1-ом (x1 < x2 < … < x2k+1)) дне, то должно выполняться условие hx1 < hx2 < … < hxk < hxk+1  > hxk+2 > … > hx2k+1 . Найдите максимальное k, для которого можно соответствующим образом выбрать 2k+1 день.


   


   

    

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




Первая строка входного файла содержит число N – количество дней в походе (1 ≤ N ≤ 100). Следующая строка содержит N целых чисел – h1, h2, …, hN  (0 ≤ hi ≤ 104).


   


   

    

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



 
В первой строке выходного файла выведите число k. Затем выведите 2k+1 число - номера дней, репортаж о которых следует включить в статью, в возрастающем порядке. Если возможных ответов несколько, выведите любой.


   




Примеры
Входные данные
7
0 3 1 10 7 2 1

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

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

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


   


                            
                            
                                


                        

                    

                

                
        

            Страница: 
                <<
                    141
                    142
                    143
                    144
                    145
                    146
                    147
                >>
            Отображать по:
            
        

    
            

        

        
    
    

    

        

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