Темы --> Информатика
    Язык программирования(952 задач)
    Алгоритмы(1657 задач)
    Структуры данных(279 задач)
    Интерактивные задачи(17 задач)
    Другое(54 задач)
---> 2656 задач <---
Источники
    Личные олимпиады(938 задач)
    Командные олимпиады(684 задач)
Страница: << 143 144 145 146 147 148 149 >> Отображать по:
#900
Путешествие со свиньями
  

У свинофермера Васи есть свиноферма рядом с городом М. Он решил навестить своего друга в городе С.-П. По дороге из М. в С.-П. расположено N городов, в которых свинина пользуется стабильным спросом. Вася решил совместить приятное с полезным и заработать немного денег. Он взял с собой \(N\) свиней и решил продавать по одной свинье в каждом из городов.

Цены на свиней в разных городах разные. В \(j\)-ом городе за один килограмм живого веса платят \(P_j\) рублей. Расстояние до \(j\)-го города по дороге из М. в С.-П. равно \(D_j\) километров.

Васины свиньи имеют разные веса. Перевозка одного килограмма свиньи на один километр обходится в \(T\) рублей.

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

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

Первая строка входного файла содержит числа \(N (1 ≤ N ≤ 1000)\) и \(T (1 ≤ T ≤ 10^9)\). Вторая строка содержит \(N\) чисел \(W_i\), задающих вес Васиных свиней \((1 ≤ W_i ≤ 10^9)\). Третья строка содержит \(N\) чисел \(D_i\), задающих расстояния до города \(i\) от \(М (1 ≤ D_i ≤ 10^9)\). Четвертая строка содержит \(N\) чисел \(P_i\), задающих цены в городах \((1 ≤ P_i ≤ 10^9)\). Все числа целые.

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

Выведите \(N\) чисел. \(j\)-ое число должно быть номером свиньи, которую следует продать в \(j\)-ом городке. Свиньи нумеруются с \(1\) в том порядке, как они перечислены во входном файле.

Примеры
Входные данные
3 1
10 20 15
10 20 30
50 70 60
Выходные данные
3 2 1
#901
iDishwasher
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes
Создатели модного гаджета iDishwasher (обычная посудомоечная машина с нарисованной на ней надкусанной грушей и продающаяся по баснословной цене) решили добавить в стандартную прошивку игру, которая поможет развлечься домохозяйкам, скучающим во время мытья посуды. Игра похожа на шахматы, правда играют в нее не фигурами, а шахматными клетками. В настольной версии игры дается набор черных и белых полей, из которых необходимо составить квадратную шахматную доску максимального размера. В посудомоечной версии игры дается не набор, а количество полей черного и белого цветов. И в качестве ответа нужно не составить доску, а вывести сторону максимального «шахматного» квадрата, который можно составить из данных клеток. Поскольку не вся целевая аудитория справляется с этой интеллектуальной игрой, вам требуется написать программу, которая поможет отчаявшимся пользователям гаджета.
Входные данные
Единственная строка содержит числа \(B\) и \(W\) задающие количество белых и черных клеток соответственно \((0 \leq B, W \leq 10\,000\)).
Выходные данные
Выведите одно число — максимальную длину стороны квадрата, который можно составить из данных клеток. Или слово "Impossible" если нельзя составить ни одного квадрата.
Примеры
Входные данные
12 15
Выходные данные
5
Входные данные
0 0
Выходные данные
Impossible
#904
Локальная сеть
  

 

Максимальное время работы на одном тесте:

4 секунды

Максимальный объем используемой памяти:

64 мегабайта

Алексей работает системным администратором в локальной домовой сети. Его сеть соединяет множество квартир и располагается в нескольких зданиях.

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

Компания, в которой работает Алексей покупает кабель только в одном специализированном магазине. В магазине продается кабель пятой и шестой категорий по цене P5 и P6 рублей за метр. При этом в наличии имеется только Q5 метров кабеля пятой категории и Q6 метров кабеля шестой категории.

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

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

В первой строке входного файла содержится число N — количество квартир, которые необходимо соединить и M — количество возможных соединений (1 ≤ N ≤ 1000, 1 ≤ M ≤ 10 000).

Следующие M строк содержат описание возможных соединений. Каждое описание состоит из трех чисел A, B и L — где A и B задают номера квартир, а L — длина соединения между ними (1 ≤ L ≤ 100). Квартиры занумерованы от 1 до N.

Последняя строка входного файла содержит числа P5, Q5, P6, Q6 – цену и количество кабеля пятой и шестой категории соответственно (1 ≤ P, Q ≤ 10 000) .

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

Если все квартиры можно соединить в сеть, то следует вывести N строк, описывающих план сети. Первая строка должна содержать стоимость прокладки сети. Следующие N-1 строк должны содержать описание соединений, представленных двумя числами каждое: Ai и Ci, где Ai — номер соединения в списке возможных соединений (от 1 до M), а Ci задает категорию кабеля и может принимать значения 5 или 6. Если планов несколько — выведите любой из них.

Если все квартиры соединить невозможно выведите слово Impossible.

Пример

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

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

6 7

1 2 7

2 6 5

1 4 8

2 3 5

3 4 5

5 6 6

3 5 3

2 11 3 100

65

1 5

2 6

4 6

5 6

7 5

 

#905
Крестики-крестики
  

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

По известному N вам необходимо определить какой игрок победит при оптимальной игре обоих игроков.

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

Входной файл содержит одно число N (3 ≤ N ≤ 2000).

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

Выведите 1, если побеждает первый игрок и 2, если побеждает второй игрок.

Примеры
Входные данные
3
Выходные данные
1
Входные данные
6
Выходные данные
2
#906
Призы победителям сборов
  

Максимальное время работы на одном тесте:

2 секунды

Максимальный объем используемой памяти:

64 мегабайта

Оргкомитет и жюри Московской олимпиады проводят очередные учебно-тренировочные сборы. Победители туров на сборах получают в качестве приза мороженое. Поскольку мороженое имеет тенденцию таять, то оно должно храниться в холодильнике. Холодильник, имеющийся в 179 школе слишком мал для хранения всего запаса мороженого. Поэтому организаторы решили заказать специальный супер-пупер-большой холодильник. Новый холодильник должен быть параллелепипедом A × B × C и хранить ровно N кубических баночек мороженого размером 1 × 1 × 1. Для уменьшения потерь холода, общая площадь поверхности холодильника должна быть как можно меньше.

Например, если размер холодильника должен быть 12, возможными вариантами являются:

 

Размеры баночек

Площадь поверхности

3 × 2 × 2

32

4 × 3 × 1

38

6 × 2 × 1

40

12 × 1 × 1

50

Лучшим вариантом является 3 × 2 × 2.

Помогите организаторам сборов выбрать оптимальную форму холодильника.

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

Входной файл содержит одно число N (1 ≤ N ≤ 106).

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

Выведите три числа A, B и C — оптимальные длины сторон холодильника. Если решений несколько — выведите любое из них.

Примеры

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

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

12

3 2 2

13

1 13 1

1000000

100 100 100

 

Страница: << 143 144 145 146 147 148 149 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест