Темы --> Информатика --> Алгоритмы --> Алгоритмы сортировки
    Квадратичные сортировки(24 задач)
    Сортировка записей(9 задач)
    Использование сортировки(13 задач)
    Быстрая сортировка(55 задач)
    Сортировка слиянием(9 задач)
    Сортировка подсчетом(27 задач)
    Сканирующая прямая(39 задач)
    Сортировка событий(4 задач)
---> 59 задач <---
Источники --> Личные олимпиады
    Олимпиады сайта(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 задач)
Страница: << 1 2 3 4 5 6 7 >> Отображать по:
#489
Тупики
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes
Есть K тупиков и расписание (время приезда и отъезда) электричек. Необходимо каждую электричку поставить в свободный тупик с минимальным номером.

На вокзале есть K тупиков, куда прибывают электрички. Этот вокзал является их конечной станцией, поэтому электрички, прибыв, некоторое время стоят на вокзале, а потом отправляются в новый рейс (в ту сторону, откуда прибыли).

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

Тупики пронумерованы числами от 1 до K. Когда электричка прибывает, ее ставят в свободный тупик с минимальным номером. При этом если электричка из какого-то тупика отправилась в момент времени X, то электричку, которая прибывает в момент времени X, в этот тупик ставить нельзя, а электричку, прибывающую в момент X+1 — можно.

Напишите программу, которая по данному расписанию для каждой электрички определит номер тупика, куда прибудет эта электричка.

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

Сначала вводятся число K — количество тупиков и число N — количество электропоездов (1≤K≤100000, 1≤N≤100000). Далее следуют N строк, в каждой из которых записано по 2 числа: время прибытия и время отправления электрички. Время задается натуральным числом, не превышающим 109. Никакие две электрички не прибывают в одно и то же время, но при этом несколько электричек могут отправляться в одно и то же время. Также возможно, что какая-нибудь электричка (или даже несколько) отправляются в момент прибытия какой-нибудь другой электрички. Время отправления каждой электрички строго больше времени ее прибытия.

Все электрички упорядочены по времени прибытия. Считается, что в нулевой момент времени все тупики на вокзале свободны.

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

Выведите Nчисел — по одному для каждой электрички: номер тупика, куда прибудет соответствующая электричка. Если тупиков не достаточно для того, чтобы организовать движение электричек согласно расписанию,  выведите два числа: первое должно равняться 0 (нулю), а второе содержать номер первой из электричек, которая не сможет прибыть на вокзал.

Примеры
Входные данные
1 1
2 5
Выходные данные
1
Входные данные
1 2
2 5
5 6
Выходные данные
0 2
Входные данные
2 3
1 3
2 6
4 5
Выходные данные
1
2
1
#493
Формула - 3
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes
Топологическая сортировка

В ежегодном чемпионате Флатландии (которая, естественно, является плоским миром) по космическим гонкам "Формула-3" участвуют N космических скутеров, имеющие форму треугольников. До начала гонок скутеры занимают положение в стартовой зоне согласно результатам жеребьевки.

1

Скутеры стартуют строго по порядку. Каждый скутер,получив команду «старт», уезжает в положительном направлении оси Ox. Следующий скутер стартует лишь тогда, когда предыдущий покинет стартовую зону. Скутеры уезжают строго параллельно оси Ox, скутеры в стартовой зоне не поворачивают и не разворачиваются.

Естественно, что если в момент старта на пути скутера окажется другой скутер, то произойдет авария (даже если скутер заденет лишь угол другого скутера своим углом).

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

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

Помогите Главному Судье — напишите программу, которая определит какой-нибудь порядок старта скутеров, чтобы аварии не произошло.

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

В первой строке вводится натуральное число N( 1 ≤ N ≤ 30 000).

В каждой из следующих N строк содержится по 6 чисел: x1, y1, x2, y2, x3, y3 – координаты трех вершин скутера на старте, целые числа, не превосходящие по модулю 106. В начальный момент скутеры не задевают друг друга.

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

Выведите через пробел N чисел – номера скутеров в том порядке, в котором они могут стартовать. Если решений несколько, выведите одно любое из них. Если решений нет, выведите одно число -1.

Примечание: первый тест соответствует приведенному рисунку. Ответ 2 3 1 в этом тесте также является правильным

Примеры
Входные данные
3
1 19 3 9 6 15
5 6 10 2 10 12
1 1 6 1 3 7
Выходные данные
Входные данные
3
0 1 -2 1 -1 -1
5 6 10 2 10 12
1 1 6 1 3 7


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

                            
                                


                        

                    

                    

                        

                            

                                #553
                            

                            

                                Расшифровка письменности Майя
                            

                              
                
                            

                                
                                
                            


                        

                        

                                

                                

                                    

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

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

                                        32 megabytes
                                    

                                

                            
                                Дана строка и подстрока. Требуется определить, сколько раз в строке встречалась подпоследовательность, состоящая из символов подстроки. 
                            

   

    

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



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



Одна из проблем расшифровки письменности Майя заключается в определении этого порядка. Рисуя значки некоторого слова, писатели Майя иногда выбирали позиции для значков, исходя скорее из эстетических взглядов, а не определенных правил. Это привело к тому, что, хотя звуки для многих значков известны, археологи не всегда уверены, как должно произноситься записанное слово.



Археологи ищут некоторое слово \(W\). Они знают значки для него, но не знают все возможные способы их расположения. Поскольку они знают, что Вы приедете на IOI ’06, они просят Вас о помощи. Они дадут Вам \(g\) значков, составляющих слово \(W\), и последовательность \(S\) всех значков в надписи, которую они изучают, в порядке их появления. Помогите им, подсчитав количество возможных появлений слова \(W\).
    

   


   

    

     Задание
    

    

		Напишите программу, которая по значкам слова \(W\) и по последовательности \(S\) значков надписи подсчитывает количество всех возможных вхождений слова \(W\) в \(S\), то есть количество всех различных позиций идущих подряд \(g\) значков в последовательности \(S\), которые являются какой-либо перестановкой значков слова \(W\) .
    

   








    

     Ограничения
    

    

		1 ≤ \(g\) ≤ 3 000, \(g\) – количество значков в слове \(W\) 



\(g\) ≤ |\(S\)| ≤ 3 000 000 где |\(S\)| – количество значков в последовательности \(S\)
    

   





    

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

    

		На вход программы поступают данные в следующем формате:



СТРОКА 1: Содержит два числа, разделенных пробелом – \(g\) и |\(S\)|. 

СТРОКА 2: Содержит \(g\) последовательных символов, с помощью которых записывается слово \(W\) . Допустимы символы: ‘a’-‘z’ и ‘A’-‘Z’; большие и маленькие буквы считаются различными. 

СТРОКА 3: Содержит |\(S\)| последовательных символов, которые представляют значки в надписи. Допустимы символы: ‘a’-‘z’ и ‘A’-‘Z’; большие и маленькие буквы считаются различными.
    

   



   

    

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

    

		Единственная строка выходных данных программы должна содержать количество возможных вхождений слова \(W\) в \(S\).
    


   






    

     Оценивание
    

    

		Для части тестов, оцениваемых в 50 баллов, выполняется ограничение \(g\) ≤ 10.
    


   







    

     Важно для программирования на PASCAL
    

    

		По умолчанию во FreePascal переменная типа string имеет ограничение размера в 255 символов. Если Вы хотите использовать более длинные строки, Вы должны добавить директиву {$ H +} в ваш код, сразу после строки program ...;.
    


   

 

 

                            
Примеры
Входные данные
4 11
cAda
AbrAcadAbRa

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


                            
                                


                        

                    

                    

                        

                            

                                #591
                            

                            

                                Триангуляция
                            

                              
                
                            

                                
                                
                            


                        

                        

                                

                                

                                    

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

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

                                        64 megabytes
                                    

                                

                            
                            

   

    

Вася нарисовал выпуклый \(N\)-угольник и провел в нем несколько диагоналей таким образом, что никакие две диагонали не пересекаются внутри \(N\)-угольника. Теперь он утверждает, что весь \(N\)-угольник оказался разбит на треугольники. Напишите программу, которая проверяет истинность Васиного утверждения.
    

   


   

    

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

    

Сначала вводятся числа \(N\) - количество вершин \(N\)-угольника (3 <= \(N\) <= 1000) и \(M\) - количество диагоналей, проведенных Васей. Далее на вход программы поступают \(M\) пар чисел, задающих диагонали (каждая диагональ задается парой номеров вершин, которые она соединяет). Гарантируется, что каждая пара чисел задает диагональ (то есть две вершины различны и не являются соседними), а также что никакие две пары не задают одну и ту же диагональ. Никакие две диагонали не пересекаются внутри \(N\)-угольника. Вершины \(N\)-угольника нумеруются числами от 1 до \(N\).
    

   


   

    

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

    

		Если Васино утверждение верно, то программа должна выводить единственное число 0. В противном случае необходимо вывести сначала число \(K\) - количество вершин в какой-нибудь не треугольной части. Далее должно быть выведено \(K\) чисел - номера вершин исходного \(N\)-угольника, которые являются вершинами этой \(K\)-угольной части в порядке обхода этой части.
    


   

 

                            
Примеры
Входные данные
3
0

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

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

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

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

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


                            
                                


                        

                    

                    

                        

                            

                                #592
                            

                            

                                Палиндром
                            

                              
                
                            

                                
                                
                            


                        

                        

                                

                                

                                    

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

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

                                        64 megabytes
                                    

                                

                            
                            

   

    

		Палиндром - это строка, которая читается одинаково как справа налево, так и слева направо.



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

   


   

    

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

    

		В первой строке входных данных содержится число \(N\) (1 <= \(N\) <= 100000). Во второй строке задается последовательность из \(N\) больших латинских букв (буквы записаны без пробелов).
    

   


   

    

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

    

		В единственной строке выходных данных выдайте искомый палиндром.
    



   





    

     Группы тестов
    

    

    




     25 баллов —
     
      (1 ≤
      
       N
      
      ≤ 10)
     
     .
    


    

     25 баллов —
     
      (1 ≤
      
       N
      
      ≤
      
       1 000
      )
     
     .
    

    

     50 баллов — полные ограничения.
Примечание
Сложность работы программы должна быть O(n). Использование встроенной сортировки(sort, sorted), алгоритмов сортировки пузырёк/quick sort/merge sort и других запрещено!



   



 

                            
Примеры
Входные данные
3
AAB

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

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

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

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

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


                            
                                


                        

                    

                

                
        

            Страница: 
                <<
                    1
                    2
                    3
                    4
                    5
                    6
                    7
                >>
            Отображать по:
            
        

    
            

        

        
    
    

    

        

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