---> 46 задач <---
Источники
    Личные олимпиады(938 задач)
    Командные олимпиады(684 задач)
Страница: 1 2 3 4 5 6 7 >> Отображать по:
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

Теплым весенним днем группа из N школьников-программистов гуляла в окрестностях города Кисловодска. К несчастью, они набрели на большую и довольно глубокую яму. Как это случилось — непонятно, но вся компания оказалась в этой яме.

Глубина ямы равна H. Каждый школьник знает свой рост по плечи hi и длину своих рук li. Таким образом, если он, стоя на дне ямы, поднимет руки, то его ладони окажутся на высоте hi + li от уровня дна ямы. Школьники могут, вставая друг другу на плечи, образовывать вертикальную колонну. При этом любой школьник может встать на плечи любого другого школьника. Если под школьником i стоят школьники j1, j2, …, jk, то он может дотянуться до уровня hj1 + hj2 + … + hjk + hi + li.

Если школьник может дотянуться до края ямы (то есть hj1 + hj2 + … + hjk + hi + liH), то он может выбраться из нее. Выбравшиеся из ямы школьники не могут помочь оставшимся.

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

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

В первой строке входных данных задается натуральное число N (1 ≤ N ≤ 2000) — количество школьников, попавших в яму.

Далее в N строках содержится по два целых числа: рост i-го школьника по плечи hi (1 ≤ hi ≤ 105) и длина его рук li (1 ≤ li ≤ 105).

В последней строке указано целое число — глубина ямы H (1 ≤ H ≤ 105).

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

В первой строке выведите K — максимальное количество школьников, которые смогут выбраться из ямы. Если K > 0, то во второй строке в произвольном порядке выведите их номера, разделяя их пробелами. Школьники нумеруются с единицы в том порядке, в котором они заданы во входных данных. Если существует несколько решений, выведите любое.

Примечание

Решение, дающее правильный ответ только при N ≤ 100; H, hi, li ≤ 1000, будет оцениваться из 70 баллов.

Примеры
Входные данные
1
239 239
566
Выходные данные
0
Входные данные
3
1 2
1 2
4 1
7
Выходные данные
2
2 1 
ограничение по времени на тест
0.0 second;
ограничение по памяти на тест
0 megabytes

Юный информатик стал исследовать, как изменяются суммы цифр натуральных чисел при умножении и делении на разные однозначные числа. Однажды он задался вопросом, можно ли восстановить число A, если нам известна сумма его цифр, а также сумма цифр числа D×A, где D — заданное однозначное число. Довольно быстро он установил, что для восстановления числа А этой информации недостаточно. Так, например, у чисел 9 и 45 одинаковые суммы цифр. Если же их умножить на 5, то получим числа 45 и 225, которые тоже имеют одинаковые суммы цифр.

Тогда юный информатик стал искать ответ на поставленный вопрос при условии, что нам известно K — количество десятичных знаков в числе A. К сожалению, и тут его ждало разочарование. У некоторых чисел, имеющих одинаковое количество цифр и одинаковые суммы цифр, после умножения на один и тот же множитель эти суммы опять оказываются одинаковыми. Такими числами, например, являются 42 и 51 при D = 3.

И тогда юный информатик поставил перед собой такую задачу: найти наименьшее K значное натуральное число A в десятичной системе счисления, которое имеет сумму цифр, равную S, а число D×A имеет сумму цифр, равную P.

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

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

Вводятся четыре натуральных числа K, S, P, D (1 K 100, 1 S 9K, 1 P ≤ 9(K+1), 1 D 9).

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

Выведите  число A, если оно существует, или –1, в противном случае. Число A не может начинаться с нуля.

Примечание

Решения, корректно работающие при K ≤ 40, будут оцениваться, исходя из 80 баллов.

Примеры
Входные данные
3 15 15 1
Выходные данные
159
ограничение по времени на тест
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
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

Компания BrokenTiles планирует заняться выкладыванием во дворах у состоятельных клиентов узоров из черных и белых плиток, каждая из которых имеет размер 1 х 1 метр. Известно, что дворы всех состоятельных людей имеют наиболее модную на сегодня форму прямоугольника N х M метров. Однако при составлении финансового плана у директора этой организации появилось целых две серьезных проблемы: во-первых, каждый новый клиент, очевидно, захочет, чтобы узор, выложенный у него во дворе, отличался от узоров всех остальных клиентов этой фирмы, а во-вторых, этот узор должен быть симпатичным.

Как показало исследование, узор является симпатичным, если в нем нигде не встречается квадрата 2 х 2 метра, полностью покрытого плитками одного цвета. Для составления финансового плана директору Васе необходимо узнать, сколько клиентов он сможет обслужить, прежде чем симпатичные узоры данного размера закончатся. Помогите ему!

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

Вводятся два положительных целых числа N и M (1 ≤ N · M ≤ 30).

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

Выведите единственное число –  количество различных симпатичных узоров, которые можно выложить во дворе размера N х M. Узоры, получающиеся друг из друга сдвигом, поворотом или отражением, считаются различными.

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

Дан прямоугольник N x M, состоящий из квадратиков 1 x 1. Некоторые квадратики вырезали. Надо найти наименьшее количество прямоугольников, на которое можно разрезать оставшуюся фигуру.

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

В первой строке входных данных заданы числа N и M, (1 ≤  N, M ≤ 10). Далее следует N строк. В (i+1)-ой содержится M чисел; j-е число равно 1, если клетку на i-й строке и в j-м столбце вырезали из доски, 0 – если оставили.

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

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

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

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