Темы --> Информатика --> Алгоритмы --> Перебор
    Комбинаторные структуры(59 задач)
    Перебор с отсечением(22 задач)
    Простые задачи на перебор(43 задач)
    Гамильтонов цикл(2 задач)
---> 3 задач <---
Источники --> Личные олимпиады --> Всероссийская олимпиада школьников --> Муниципальный этап --> Москва
    2007(5 задач)
    2008(5 задач)
    2009(5 задач)
    2010(5 задач)
    2011(5 задач)
    2012(5 задач)
    2013(5 задач)
    2014(5 задач)
Страница: 1 Отображать по:
#727
Квас
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

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

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

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

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

Первая строка входных данных содержит число N – количество городов ( N ≤ 10) и еще N чисел – количество кваса, требуемое ежедневно 1-м, 2-м, …, N -м городом (города нумеруются подряд вдоль кольцевой дороги).

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

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

Задача Е, рис. 4Примеры

Пояснение для второго примера(см. рисунок):

На острове 6 городов, потребность каждого города указана в кружочках, номер города рядом с кружочком.

Если построить завод во 2-м городе (он выделен серым), то потребуется заплатить 4 + 1 (стоимость перевозки в 1-й и 3-й города) + 5*2 + 3*2 (в 4-й и 6-й) + 1*3 (в 5-й см. рисунок).
Во 2-й вообще ничего не везем. Это будет 24 тугрика. Легко проверить, что если построить завод в других городах, сумма будет больше. Например, если построить в 4-м городе, то сумма составит 1 + 1 + 3*2 + 4*2 + 4*3 = 28 тугриков.

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

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

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

Вводится сначала K — вес предмета, который положили на левую чашу (1≤K≤50). Далее записано общее количество гирек N (1≤N≤10). Далее записано N различных натуральных чисел, не превышающих 50, — веса гирек.

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

В первой строке выведите веса гирек, которые нужно поместить на левую чашу весов, во второй строке — гирьки, которые нужно поместить на правую чашу. Если на какую-то чашу ни одной гирьки помещать не нужно — выведите в этой строке число 0. Если с помощью данных гирек привести весы в равновесие нельзя, выведите одно число –1. Если вариантов несколько, выведите любой из них.

Примеры
Входные данные
5
2
3 5
Выходные данные
0
5
Входные данные
5
3
6 3 4
Выходные данные
4
3 6
Входные данные
5
1
2
Выходные данные
-1
#111858
Простой квадрат
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

У Пети имеется игровое поле размером \(3\times3\), заполненное числами от 1 до 9. В начале игры он может поставить фишку в любую клетку поля. На каждом шаге игры разрешается перемещать фишку в любую соседнюю по стороне клетку, но не разрешается посещать одну и ту же клетку дважды. Петя внимательно ведет протокол игры, записывая в него цифры в том порядке, в котором фишка посещала клетки. Пете стало интересно, какое максимальное число он может получить в протоколе. Помогите ему ответить на этот вопрос.

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

Входной файл содержит описание поля — 3 строки по 3 целых числа, разделенных пробелами. Гарантируется, что все девять чисел различны и лежат в диапазоне от 1 до 9.

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

Выведите одно целое число — максимальное число, которое могло получиться в протоколе при игре на данном поле.

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

Пример

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