Темы --> Информатика --> Алгоритмы
    Задачи на моделирование(78 задач)
    Арифметические алгоритмы(240 задач)
    Алгоритмы поиска(155 задач)
    Алгоритмы сортировки(194 задач)
    Динамическое программирование(355 задач)
    Алгоритмы на графах(319 задач)
    Перебор(154 задач)
    Игры и выигрышные стратегии(33 задач)
    Вычислительная геометрия(216 задач)
    Эвристические методы(30 задач)
    Алгоритмы на строках(45 задач)
    Пересечение множеств(10 задач)
    Жадный алгоритм(71 задач)
    Теория расписаний(5 задач)
    Обработка текста(31 задач)
    Дата и время(14 задач)
---> 264 задач <---
Источники --> Командные олимпиады
    Школьная командная олимпиада ФМШ № 2007 г.Москвы(21 задач)
    Турнир Архимеда(52 задач)
    Кировские командные турниры(8 задач)
    Барнаульские командные турниры(10 задач)
    Московская командная олимпиада(246 задач)
    Командные чемпионаты школьников Санкт-Петербурга по программированию(167 задач)
    ВКОШП(180 задач)
Страница: << 1 2 3 4 5 6 7 >> Отображать по:
#43
Лапта
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

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

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

В первой строке входных данных содержатся два числа: D — максимальное расстояние удара и N — количество соперников на поле (D и N натуральные числа, D ≤ 1000, N ≤ 200). В следующих N строках задается по три числа – начальные координаты xi и yi и максимальная скорость vi соответствующего игрока (скорости и координаты — целые числа, –1000 ≤ xi ≤ 1000, 0 ≤ yi ≤ 1000, 0 < vi ≤ 1000), никакие два игрока не находятся изначально в одной точке. Игрок, бьющий мяч, находится в точке с координатами (0,0). Мяч выбивается в точку с неотрицательной ординатой (y ≥  0).

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

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

Оценка задачи

1 балл получат программы, которые верно работают, когда в поле не более двух соперников.

Примеры
Входные данные
10 2
1 1 1
-1 1 1
Выходные данные
9.05539
0.00000 10.00000
#44
Машинки
  
ограничение по времени на тест
4.0 second;
ограничение по памяти на тест
64 megabytes

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

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

В некоторый момент образовалась пробка. На 1-й дороге скопилось N машин, а на 2-й — M. Для каждой машины известно время, которое ей потребуется для проезда развилки, если она первая в очереди и ее дорога "активна".

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

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

Сначала вводятся числа T, N и M, затем N чисел — времена проезда перекрестка машинами с первой дороги (в порядке удаления от перекрестка), а затем M чисел — времена проезда перекрестка машинами со второй дороги.

<>Все числа  целые неотрицательные, все времена не превосходят 100, T ≤ 100, N, M ≤ 1000, N+M > 0.

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

В первой строке  выведите одно число — минимальное среднее время ожидания c точностью 10–3. Далее выводите информацию о машинах в порядке их проезда перекрестка и о переключении потока  следующим образом.

  • Для каждой машины выведите информацию в формате:

Car k from road i

где k — номер машины на своей дороге (ближайшая к перекрестку в момент образования пробки машина имеет номер 1, следующая на той же дороге — 2 и т.д.), i — номер дороги: 1 или 2.

  • Для каждого переключения потока выведите информацию:

Switch road from 1 to 2

для переключения потока с первой дороги на вторую или

Switch road from 2 to 1

для переключения потока со второй дороги на первую.

Информация обо всех событиях (переключениях и проездах через перекресток) должна выводиться именно в том порядке, в котором они происходят.

Если решений несколько, выведите любое из них.

Оценка задачи

1 балл будет набирать решение, верно работающее при N, M ≤ 10.

Примеры
Входные данные
1 2 2
5 6 
1 7
Выходные данные
11.500
Switch road from 1 to 2
Car 1 from road 2
Switch road from 2 to 1
Car 1 from road 1
Car 2 from road 1
Switch road from 1 to 2
Car 2 from road 2
#45
Контейнеры
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

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

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

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

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

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

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

Оценка задачи

1 балл будут получать программы, верно работающие при следующих ограничениях: количество стопок не больше 10, в каждой стопке не более 10 контейнеров.

Комментарий к примеру:

Изначально в первой стопке лежат четыре контейнера — снизу контейнер с товаром первого вида, над ним — с товаром второго вида, над ним — третьего, и сверху — еще один контейнер с товаром второго вида.

Одна из правильных последовательностей действий (вместо ответа в примере задачи):

1 2
1 3
1 2

Примеры
Входные данные
3
4 1 2 3 2
0
0
Выходные данные
1
#191
Шахматный детектив
  
Источники: [ Командные олимпиады, ВКОШП, 2006, Задача A ]
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
256 megabytes
Дано изображение состоящее из черных, белых и серых клеток. Необходимо определить, может ли изображение быть шахматной доской (клетки доски могут состоять из нескольких маленьких клеток). 

Известный частный сыщик поставил чашку с чаем на специальную подогревающую подставку, питающуюся от USB-порта его компьютера, и приступил к обдумыванию очередного запутанного преступления. Через пару часов раздумий он понял, что для разгадки этого дела достаточно определить, была ли на месте преступления шахматная доска.

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

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

 

includegraphics{pics/chess.1} includegraphics{pics/chess.2}

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

Шахматная доска – это квадрат, разбитый на x2 (для некоторого x) равных квадратов – полей. Стороны полей параллельны сторонам изображения. Длина стороны каждого поля шахматной доски выражается целым числом пикселей. Все пиксели, принадлежащие одному полю, покрашены в один и тот же цвет – черный или белый. При этом соседние поля (поля, имеющие общую сторону) покрашены в различные цвета.

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

В первой строке вводятся два целых числа: m и n – размеры фрагмента фотографии в пикселях ( 1\( le\)m, n\( le\)250).

Следующие m строк содержат по n символов каждая, j-й символ i-й строки соответствует пикселю с координатами (i, j). Символ «.» (точка) означает белый пиксель, символ «*» – черный, символ «?» – серый.

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

Если заданный фрагмент фотографии может быть изображением части шахматной доски, выведите  слово «YES». После этого выведите m строк по n символов в каждой – изображение соответствующей части шахматной доски в том же формате, что и во входных данных, только серые пиксели должны быть заменены на белые или черные. Если решений несколько, выведите любое.

В противном случае программа должна вывести слово «NO».

Примеры
Входные данные
4 5
*.?.?
.***.
.*?*.
.*?*.
Выходные данные
YES
*...*
.***.
.***.
.***.
Входные данные
4 5
..?..
.***.
.*?*.
.*?*.
Выходные данные
NO
#241
Тапочки
  
Темы: [Перебор]
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

У меня в прихожей стоят в ряд 20 тапочек – 10 левых и 10 правых. Приходя домой, я переобуваюсь и выбираю два тапочка – левый и правый, в которые мне удобнее всего засунуть ноги. Естественно, что левый тапочек должен стоять левее правого, и расстояние (количество других тапочек) между ними должно быть как можно меньше. Напишите программу, которая вычисляет, сколько же тапочек стоит между теми, которые мне удобнее всего надеть.

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

Вводится последовательность из 10 нулей и 10 единиц, записанных в некотором порядке. Единица соответствует левому тапочку, 0 – правому тапочку. Числа разделены пробелами.

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

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

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