Темы
    Информатика(2656 задач)
---> 13 задач <---
Источники --> Личные олимпиады --> Всероссийская олимпиада школьников --> Региональный этап --> Московская областная олимпиада
    2007(7 задач)
    2008(6 задач)
Страница: << 1 2 3 Отображать по:
#3142
Автозаправки
  

Фирма «АйОйЛ» построила на скоростном шоссе Москва-Тверь N автозаправок. Каждая автозаправка имеет свой номер, который присваивался ей при строительстве, начиная с единицы. Кроме того, каждая автозаправка располагается на определенном километре шоссе. Километры на шоссе нумеруются от 0, начиная от Москвы.

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

Требуется написать программу, которая находит автозаправку, которую можно сократить.

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

Первая строка входного файла содержит количество автозаправок N (2 ≤ N ≤ 105). Вторая строка входного файла содержит N различных целых чисел xi – километр, на котором расположена автозаправка с номером i (1 ≤ i ≤ N). Числа в строке разделены пробелом. Значения всех xi не меньше ноля и не  превосходят 109 по абсолютной величине.

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

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

Ввод
Вывод
5
10 3 7 2 5
4
#3143
Перевес багажа
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

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

У Пети в чемодане лежат N предметов, каждый предмет имеет свой вес Wi килограмм и ценность Ai рублей, причем оказалось так, что для любого предмета выполняется следующее неравенство:

W1 + W2 + … + Wi-1 ≤ Wi

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

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

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

В первой строке задаётся количество предметов в багаже у Пети N (1 ≤ N ≤ 50) и какой у Пети перевес чемодана в килограммах M (1 ≤ M ≤ 1018). Во второй строке задаются N целых неотрицательных чисел – вес всех вещей Wi, сумма чисел не превышает 1018. В третьей строке заданы N целых неотрицательных чисел – ценность всех вещей Ai , все числа не превышают 109.

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

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

Ввод
Вывод
4 15
5 10 15 30
1 5 3 6
3
3 2
1 2 4
7 6 5
5
#3144
ASCII-art
  
ASCII art (от англ. ASCII artwork) — форма изобразительного искусства, использующая символы ASCII на моноширинном экране компьютерного терминала (или принтера) для представления изображений. При создании такого изображения используется палитра, состоящая из буквенных, цифровых символов и символов знаков пунктуации.

Википедия

Флатландия – необычная страна, и искусство у флатландцев тоже необычное. Особый интерес представляют их картины. Во-первых, флатландские художники используют для написания картин только ASCII символы, во-вторых, все картины исключительно квадратные.

Пете захотелось приобщиться к искусству Флатландии, однако, он столкнулся с очень серьёзной проблемой. Дело в том, что все картины защищены законом об авторских правах и кодируются следующим образом: над картиной последовательно выполняются K операций. Каждая операция – одно из четырёх зеркальных отражений:

Operations with image
  • Ось отражения – горизонтальная прямая, делящая изображение пополам. При отражении первая строка меняется местами с последней, вторая – с предпоследней и т.д.
  • Ось отражения – вертикальная прямая, делящая изображение пополам. При отражении первый столбец меняется местами с последним, второй – с предпоследним и т.д.
  • Ось отражения – побочная диагональ (диагональ, соединяющая правый верхний и левый нижний угол изображения). При отражении левый верхний угол меняется с правым нижним и т. д.
  • Ось отражения – главная диагональ (диагональ, соединяющая левый верхний и правый нижний угол изображения). При отражении правый верхний угол меняется с левым нижним и т. д.

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

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

В первой строке входного файла находятся два натуральных числа N и K (1 ≤ N ≤ 1000, 1 ≤ K ≤ 1000000), где N – размер картины, K – число отражений, применяемых для кодирования. Во второй строке содержатся K натуральных чисел, обозначающих номера отражений (числа могут принимать только значения 1, 2, 3 или 4).

В следующих N строках описывается само закодированное изображение. В (i+2)-й строке записана i-я строка закодированной картины. В изображении используются символы с ASCII-кодами от 32 до 126 включительно.

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

В выходной файл требуется вывести раскодированное изображение.

Ввод
Вывод
5 1 
1
UVWXY
PQRST
KLMNO
FGHIJ
ABCDE
ABCDE
FGHIJ
KLMNO
PQRST
UVWXY
7 8 
1 3 1 2 4 1 2 3
RQZQQWD
MFSUWDS
YODIIKO
KNECWHT
YRQZQQW
NMFSUWD
SYODIIK
DSOTWDK
WDKHQWI
QWIWQUI
QUICZSD
ZSDEQFO
QFONRMY
RMYKYNS
11 2
1 4 
[/|  ||   .
_=~||_ _   
]\ |||||   
_ \_   _/  
[/__  =_ _ 
_=_*OO=_(_ 
]\__  =_)_ 
_ /_   _\  
[/ |||||   
_=~||_ _   
]\|  ||   .
.         .
    ___    
   / ()\   
 _|_____|_ 
| | === | |
|_|  O  |_|
 ||  O  || 
 ||__*__|| 
|~ \___/ ~|
/=\ /=\ /=\
[_]_[_]_[_]
36 7
1 3 4 2 4 2 1 
 |||||||||||||||||||||||||||||||||| 
-                                  -
-                                  -
-                                  -
-                                  -
-                                  -
-                 &  &,   &        -
-             &   7&~BM   M#6      -
-             M    4M_M    MM&g    -
-         !#8&@     M M    M_MM    -
-         *]44Q     M #    M8Mj    -
-             M   MMMMM   !Mj      -
-             *           *        -
-                                  -
-                                  -
-                                  -
-                                  -
-                                  -
-                                  -
-               r   g         6    -
-     ^        ^    ^  FMg`X  M&   -
-^&#&\(# ~    f ~    ~  _7M "  B00c -
-~MMMMN ~MMMMM ^    ~    M_ _  "#M&-
-~    " ~]]]]M ~g   #  , M& _  ^ Mj-
-               M&8#g  N "0#   ^!  -
-               "0M0          Ej   -
-                 ]           _    -
-                                  -
-                                  -
-                                  -
-                                  -
-                                  -
-                                  -
-                                  -
-                                  -
 ||||||||||||||||||||||||||||||||||
----------------------------------
|           j&                     |
|           MMc                    |
|          ! #0                    |
|         j^^"0&                   |
|        _E   BM6        jMg       |
|                        MM&       |
|           __          j8_M6      |
|          #  "X        MMMM#      |
|          0&_ `       *!   M&     |
|          "MMMg                   |
|             7M                   |
|          N, _F                   |
|                       M#MMM,     |
|                       M  _B&     |
|          g#~~^g       MMMM~      |
|         0#            M  4&      |
|        ]M8            M   7&     |
|         0&                       |
|         "Mg   r                  |
|           ~^~^                   |
|                      *MQ@M&      |
|           MMf          4&        |
|           ]M           48        |
|           ]M           ]#        |
|           ]M           *!        |
|           ]M                     |
|           ~~~                    |
|                                  |
|           "N#^                   |
|            M\)                    |
|            M&                    |
|            M#                    |
|            M&                    |
|           ~~^                    |
 ----------------------------------
Страница: << 1 2 3 Отображать по:
Выбрано
:
Отменить
|
Добавить в контест