Темы --> Информатика
    Язык программирования(952 задач)
    Алгоритмы(1657 задач)
    Структуры данных(279 задач)
    Интерактивные задачи(17 задач)
    Другое(54 задач)
---> 4 задач <---
Источники --> Личные олимпиады --> Московская олимпиада школьников --> 10-11 классы --> 2007 --> 1 день
Страница: 1 Отображать по:
#490
Очень Легкая Задача
  
Есть один листок и два ксерокса. Необходимо определить время, за которое можно получить N копий исходного листка. Первый ксерокс копирует страницу за X секунд, второй - за Y.

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

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

На вход программы поступают три натуральных числа N, x и y, разделенные пробелом (1 ≤ N ≤ 2∙108, 1 ≤ x, y ≤ 10).

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

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

Примеры
Входные данные
4 1 1
Выходные данные
3
Входные данные
5 1 2
Выходные данные
4
#491
Почти палиндром
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

Слово называется палиндромом, если его первая буква совпадает с последней, вторая – с предпоследней и т.д. Например: "abba", "madam", "x".

Для заданного числа K слово называется почти палиндромом, если в нем можно изменить не более K любых букв так, чтобы получился палиндром. Например, при K = 2 слова "reactor", "kolobok", "madam" являются почти палиндромами (подчеркнуты буквы, заменой которых можно получить палиндром).

Подсловом данного слова являются все слова, получающиеся путем вычеркивания из данного нескольких (возможно, одной или нуля) первых букв и нескольких последних. Например, подсловами слова "cat" являются слова "c", "a", "t", "ca", "at" и само слово "cat" (а "ct" подсловом слова "cat" не является).

Требуется для данного числа K определить, сколько подслов данного слова S являются почти палиндромами.

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

В первой строке вводятся два натуральных числа:N (1 ≤ N ≤ 5 000) – длина слова и K (0 ≤ K ≤ N).

Во второй строке содержится слово S, состоящее из N строчных латинских букв.

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

Требуется вывести одно число – количество подслов слова S, являющихся почти палиндромами (для данного K).

Примеры
Входные данные
5 1
abcde
Выходные данные
12
Входные данные
3 3
aaa
Выходные данные
6
#492
Рейтинг
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

Новый учитель математики ввел в школе оригинальную систему оценки учеников – рейтинговую. На каждом уроке школьнику предлагалось выполнить задание, состоящее из нескольких задач. После этого учитель увеличивал рейтинг школьника на число, равное отношению количества решенных им сегодня задач к количеству задач, решенных им на прошлом занятии. Например, если сегодня ученик решил 5 задач, а вчера – две, то к его рейтингу сегодня прибавится = 2.5. Изначально рейтинг равен нулю; он начинает увеличиваться со второго дня. Если в один из дней какой-то ученик не решал ни одной задачи, то учитель объявлял его полной бездарностью и переводил в другой класс (с облегченным изучением математики), поэтому каждый день все ученики старались решить хотя бы одну задачу.

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

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

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

В следующей строке содержатся числа a1,a2, …, aN– количество задач, которые учитель предложил школьникам на первом, втором, …, N-м уроках соответственно (1 ≤ ai ≤ 100).

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

В первой строке выведите максимальный рейтинг, который может получить школьник за N дней, с точностью не менее 0.001.

Во второй строке выведите N чисел – количество задач, которые должен решить школьник в каждый из дней. Если вариантов несколько, выведите один любой из них.

Примеры
Входные данные
3
1 2 3
Выходные данные
4.00000
1 1 3
Входные данные
3
1 10 8
Выходные данные
10.800000
1 10 8
#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


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

                            
                                


                        

                    

                

                
        

            Страница: 
                    1
            Отображать по:
            
        

    
            

        

        
    
    

    

        

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