Темы
    Информатика(2656 задач)
---> 167 задач <---
Источники --> Командные олимпиады --> Командные чемпионаты школьников Санкт-Петербурга по программированию
    1999(5 задач)
    2000(7 задач)
    2001(8 задач)
    2002(8 задач)
    2003(9 задач)
    2004(9 задач)
    2005(10 задач)
    2006(10 задач)
    2007(10 задач)
    2008(9 задач)
    2009(10 задач)
    2010(10 задач)
    2011(9 задач)
    2012(10 задач)
    2013(10 задач)
    2014(11 задач)
    2015(11 задач)
    2016(11 задач)
Страница: << 3 4 5 6 7 8 9 >> Отображать по:
#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
#1383
Квадраты
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

Рассмотрим целочисленную решетку размера N × N. Пусть некоторые ее узлы покрашены в белый, а некоторые – в черный цвет. Требуется определить количество квадратов на заданной решетке, то есть квадратов, вершины которых совпадают с узлами заданной решетки и покрашены в одинаковый цвет.

Например, на решетке размера 4 × 4, изображенной на рисунке 1 такой квадрат один, он показан на рисунке 2.


 

 



Рисунок 1. Решетка 4 × 4.



Рисунок 2. Квадрат на решетке.
Входные данные

Первая строка входного файла содержит число N – размер решетки (2 ≤ N ≤ 50). Следующие N строк содержат по N чисел из множества {0, 1} и задают решетку. Если точка с координатами (i, j) покрашена в белый цвет, то j-ое число i-ой строки есть 0, а если в черный, то 1.

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

Выведите в выходной файл количество квадратов на решетке из входного файла.

Примеры
Входные данные
4
0 1 0 0
0 0 1 1
1 0 0 0
0 1 1 1
Выходные данные
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
#1752
Автобусы
  
Заданы прямоугольные рамки с вершинами в целых точках и со сторонами параллельными осям координат. Требуется найти количество точек, лежащих на всех рамках.

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

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

Для простоты предположим, что действие происходит на координатной плоскости. Каждый автобус ездит по границе прямоугольника c ненулевыми сторонами, вершины которого имеют целочисленные координаты, а стороны параллельны осям координат. Требуется выяснить, какое максимальное число контролёров удастся принять на работу, если городское управление милиции, в свою очередь, требует, чтобы каждый контролёр находился в точке с целочисленными координатами.

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

На первой строке входного файла находится число \(n\) (1 ≤ \(n\) ≤ \(10^4\)) – количество маршрутов. Далее следуют \(n\) строк, на каждой из которых находятся две пары целых чисел – координаты двух противоположных вершин прямоугольника, по которому проходит данный маршрут. Все координаты не превосходят \(10^8\) по абсолютной величине.

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

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

Примеры
Входные данные
1
0 0 1 1
Выходные данные
4
#1753
Часы
  
Маленькая стрелка часов делает один оборот в час, а большая - один в сутки. Требуется определить, в какой момент стрелки совпадут.

В марсианских сутках \(N\) часов. У марсиан Ятеп и Ашам есть часы со стрелками, которые работают почти так же, как земные – большая стрелка делает один оборот в час, а маленькая – один оборот в сутки. Ятеп и Ашам поссорились и решили не разговаривать, пока стрелки часов не совпадут. Определите точный момент времени, когда это случится.

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

Во входном файле задано число тестов \(K\) (0 ≤ \(K\)<\(10^4\)), далее для каждого теста указаны целые числа \(N\), \(A\), \(B\) и \(C\) (1<\(10^9\), 0 ≤ \(A\), 0 ≤ \(B\) < \(10^9\)). Числа \(A\), \(B\) и \(C\) означают, что Ятеп и Ашам поссорились в \(A\)+\(B\)/\(C\) часов.

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

Для каждого теста выведите искомое время в том же формате: числа \(A\), \(B\) и \(C\), такие, что искомое время равно \(A\)+\(B\)/\(C\) (0 ≤ \(A\), 0 ≤ \(B\), дробь \(B\)/\(C\) – несократимая).

Примеры
Входные данные
2
12 11 0 1
12 0 0 1
Выходные данные
0 0 1
1 1 11
Страница: << 3 4 5 6 7 8 9 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест