7866.png
ЧЕЛЯБИНСК,ЮУРГУ,ИЕТН

Назад

images/home.png Начало
images/balloon.gif Соревнования
2010

Подразделы

Другие разделы

Дата и время

19/04/2024 20:47:55

Авторизация

Имя:
Пароль:
Зарегистрироваться
Восстановить пароль
 

printЗадачи Южно-Уральского командного чемпионата 2010

A. Дверь в чудесный сад

Ограничения: время – 100ms/500ms, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

11214.gif
"Алиса открыла дверцу и увидела за ней нору, совсем узкую, не шире крысиной. Алиса встала на колени и заглянула в нее – в глубине виднелся сад удивительной красоты. Ах, как ей захотелось выбраться из темного зала и побродить между яркими цветочными клумбами и прохладными фонтанами! Но она не могла просунуть в нору даже голову."
Если Алиса выпьет `K` капель из найденного на стеклянном столике пузырька, то ее рост уменьшится в `K` раз, а если она откусит `L` кусочков от пирожка из коробочки под столом, то ее рост увеличится в `L` раз. Алиса может попасть в сад, только если ее рост будет строго больше `P_1/Q_1` и строго меньше `P_2/Q_2`.
Напишите программу, определяющую по ограничениям на рост, сколько капель нужно выпить Алисе из пузырька и сколько кусочков пирожка нужно съесть, чтобы попасть в сад. Начальный рост Алисы равен 1.
Первая строка ввода содержит 4 целых числа `P_1`, `Q_1`, `P_2`, `Q_2` (`1\ ≤\ P_1,\ Q_1,\ P_2,\ Q_2\ ≤\ 10^9`, `P_1/Q_1\ <\ P_2/Q_2`) – ограничения на рост Алисы.
Вывести два целых числа `K` и `L` – наименьшее возможное количество капель (ведь "Алиса отлично помнила, что если выпьешь слишком много из бутылки, на которой нарисованы череп и кости и написано "Яд!", то почти наверняка тебе не поздоровится") и количество кусочков пирожка. Если существует несколько вариантов для значения `L`, то вывести наименьшее из них.

Пример ввода

27 161 28 160

Пример вывода

23 4

B. Was it a cat I saw?

Ограничения: время – 100ms/500ms, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

11217.gif
Увидев улыбающегося кота, Алиса очень удивилась. Еще больше она удивилась, увидев, как Чеширский Кот исчез, оставив свою улыбку. Свое удивление от этой встречи Алиса записала с помощью фразы-палиндрома "Was it a cat I saw?", расположив буквы в форме квадрата, повернутого на 45 градусов, как показано на рисунке. Фразу "Was it a cat I saw" здесь можно прочитать несколькими способами, двигаясь от любой буквы W на границе к соседней букве слева, справа, снизу или сверху, от нее – к следующей, пока не дойдем до буквы C в центре квадрата, а затем двигаясь назад к границе. Разрешается при чтении фразы проходить дважды по одной и той же букве. К сожалению, когда Алиса рисовала квадрат с фразой, она поставила несколько клякс, скрывших некоторые буквы.
Напишите программу, определяющую число способов прочитать фразу "Was it a cat I saw" на рисунке Алисы без использования букв, скрытых кляксами.
Ввод содержит 13 строк, в формате, показанном в примере. Буквы, которые невозможно разобрать из-за клякс, заменены символом '*'.
Выведите одно целое число – количество способов прочтения фразы-палиндрома.

Пример ввода

      W
     WAW
    WASAW
   WASIS*W
  WASITISAW
 WASI*ATISAW
WASITACATISAW
 WA**TATISAW
  WASITISAW
   WASISA*
    WASAW
     WAW
      W

Пример вывода

23104

C. Игра перед чаепитием

Ограничения: время – 500ms/1000ms, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

11221.png
Чтобы убить время перед чаепитием, Мартовский Заяц и Болванщик играют в следующую игру. Игра идет на части квадрата размером `N\ times\ N` клеток, разрезанного по диагонали. В диагональных клетках записаны некоторые числа. В левый нижний угол доски помещается фишка. Игроки по очереди двигают фишку на соседнюю клетку вверх, вправо или по диагонали вверх-вправо, пока фишка не окажется на диагонали квадрата. Игрок, достигший клетки на диагонали квадрата, получает выигрыш, равный числу, записанному в этой клетке (отрицательное число в этой клетке означает проигрыш игрока).
Напишите программу, вычисляющую максимальный выигрыш, который может получить игрок, делающий первый ход, при оптимальной игре обоих игроков.
Первая строка содержит одно целое число `N` (`2\ ≤\ N\ ≤\ 1000`) – размер доски, вторая строка – `N` целых чисел в диапазоне от `-10^6` до `10^6` – числа на диагонали.
Вывести одно целое число – максимальный выигрыш первого игрока.

Пример ввода

7
7 1 4 9 -3 9 2

Пример вывода

3

D. Приглашение на королевский крокет

Ограничения: время – 300ms/600ms, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

"- А какого роста ты хочешь быть? – спросила наконец Гусеница.
- Ах, все равно, – быстро сказала Алиса. – Только, знаете, так неприятно всё время меняться…"
Чтобы попасть на крокет к Королеве, Алиса нужно пройти через двери разных размеров, используя кусочки гриба для изменения своего роста.
Напишите программу, которая по карте Страны Чудес определяет, как Алиса сможет прийти на крокет к Королеве, изменив свой рост наименьшее количество раз. Если существует несколько путей с одинаковым количеством изменений роста, то программа должна минимизировать количество кусочков гриба, использованных для изменения роста.
В первой строке ввода содержатся два целых числа `N`, `M` (`1\ ≤\ N,\ M\ ≤\ 100`) – размеры Страны Чудес. Далее следует `N` строк, содержащих по `M` символов – карта Страны Чудес. Символ 'A' означает начальное положение Алисы, символ 'Q' – место встречи с Королевой. Символы от '1' до '9' означают двери, цифра указывает, каким должен быть рост Алисы при проходе через эту дверь. Символ '#' означает препятствие, а символ '.' – свободное место. Рост Алисы в начале путешествия равен 1. В конце путешествия рост может быть любым. Для изменения роста на `K` (неважно, уменьшения или увеличения), необходимо потратить `K` кусочков гриба. Гарантируется, что на карте ровно один символ 'A' и один символ 'Q', что никакие двери не располагаются рядом в соседних клетках и что существует путь от 'A' до 'Q' через свободные клетки и клетки с дверями.
Выведите в первой строке два целых числа – минимальное количество изменений роста и минимальное количество использованных кусочков гриба при таком количестве изменений роста. Во второй строке вывести последовательность из символов 'N', 'S', 'W', 'E', которая описывает последовательность перемещений Алисы ('N' – вверх, 'S' – вниз, 'W' – влево, 'E' – вправо). Если существует несколько вариантов такого пути, то вывести любой из них. Путь не должен проходить по одной клетке более одного раза.

Пример ввода

3 5
A.3..
9##4#
....Q

Пример вывода

1 8
SSEEEE

E. Поле для крокета

Ограничения: время – 100ms/500ms, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

11225.png
Пока остальные слуги перекрашивают розы, Тройка и Четверка пытаются расположить квадратное поле для крокета на треугольной поляне таким образом, чтобы его площадь была максимально возможной.
Напишите программу, которая вычисляет максимальную длину стороны квадрата, который можно разместить на треугольной поляне с заданными длинами сторон.
Ввод содержит три целых числа от 1 до 1000 – длины сторон треугольника. Гарантируется, что сумма любых двух сторон больше длины третьей стороны.
Выведите одно вещественное число – максимальную длину стороны квадрата с точностью `10^{-6}`.

Пример ввода

5 5 5

Пример вывода

2.320508

F. Покраска роз

Ограничения: время – 1s/2s, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

11228.gif
Когда Алиса пришла в королевский цветник, она обнаружила трех садовников, которые спешно перекрашивали розы. При этом один перекрашивал белые розы в красный цвет, другой – красные розы в желтый цвет, а третий – желтые розы в белый цвет. Немного понаблюдав за ними, Алиса обнаружила, что в начале каждого часа садовник, перекрашивающий розы цвета `X` в цвет `Y`, находит в цветнике все розы цвета `X`, рядом с которыми на одной из соседних клеток (с общей границей) растет роза цвета `Y`, а затем до конца часа перекрашивает все такие розы в цвет `Y`. По истечении часа эта процедура повторяется снова.
Напишите программу, которая определит состояние цветника к приходу Королевы.
Первая строка ввода содержит три целых числа `N`, `M`, `T` (`1\ ≤\ N,\ M,\ T\ ≤\ 100`) – размеры цветника и время в часах до появления Королевы. Далее следует `N` строк, содержащих по `M` символов 'W', 'R' и 'Y' – начальное состояние цветника. Символ 'W' обозначает розу белого цвета, 'R' – красного, 'Y' – желтого.
Вывести `N` строк по `M` символов – состояние цветника к моменту появления Королевы, с использованием обозначений, указанных в формате ввода.

Пример ввода

3 4 2
RWYR
WYRW
YRWY

Пример вывода

RRRW
RRWY
RWYR
После 1-го часа состояние цветника будет таким
RRWY
RWYR
WYRW

G. Пирожки

Ограничения: время – 300ms/600ms, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (2)

"Все пришли к Червонной Даме
Выпить чаю с пирожками.
Пирожков у Дамы нет:
Пирожки стащил Валет!"
Стащив пирожки, Валет спрятался в саду. Зная, что вскоре пропажа будет обнаружена и через `T` минут он будет арестован, Валет решил в полной мере насладиться едой. Пирожки оказались двух видов. На поедание пирожка с картошкой Валет тратит `N` минут, а пирожка с капустой – `M` минут. Валет хочет наслаждаться едой как можно дольше, а к моменту появления стражи спрятать оставшиеся пирожки и притвориться, что он сочиняет стихи.
Напишите программу, которая минимизирует время, потраченное Валетом на сочинение стихов, и максимизирует количество съеденных пирожков.
Ввод содержит несколько тестовых случаев (не более 100). Каждая строка ввода описывает один тестовый случай и содержит три целых числа `N`, `M` и `T` (`1≤\ N\ <\ M\ ≤\ 10^5`, `1\ ≤\ T\ ≤\ 10^9`) – время на поедание пирожков каждого вида и время, оставшееся до ареста.
Для каждого тестового случая вывести одну строку, содержащую три целых числа – минимальное время, которое Валет уделит сочинению стихов, затем количество съеденных пирожков с картошкой, а затем – с капустой. Если существует несколько вариантов, минимизирующих время на сочинение стихов, то вывести вариант, в котором общее количество съеденных пирожков максимально.

Пример ввода

3 5 16
5 7 18

Пример вывода

0 2 2
1 2 1

H. Love Calculator

Ограничения: время – 500ms/1000ms, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Alice had found the way to calculate the love between two persons, in her elder sister's notebook. Since mathematics is too complex for Alice, you will have to write a program so that Alice can calculate love between any two persons very quickly.
You will be given two names. These two names can have white space or some other non-alphabetical characters like $ @ & % etc. Each character has a particular value. Letters L, V, and E have value 9, letters Y, O, and U – 12, other characters – 0. Both upper case and lower case holds the same values. The love strength is calculated in percents as the difference between the sum of letters' values in both names and the half-sum of names' lengths. Remember: result can not be more than 100% and less than 0%.
The input contains two lines. Each line contains the name, which holds not more than 30 characters.
Your program have to calculate the love between these two persons and print the result in percents with one digit after the decimal point.

Sample Input

Romeo Montague
Juliet Capulet

Sample Output

100.0%
The sum of letters' values in "Romeo Montague" is 12+9+12+12+12+9=66
The sum of letters' values in "Juliet Capulet" is 12+9+9+12+9+9=60
The love strength is 66+60-(14+14)/2=112% `->` 100%

I. Траляля и Труляля идут в бой

Ограничения: время – 2500ms/5000ms, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

11236.gif
"Раз Труляля и Траляля
Решили вздуть друг дружку,
Из-за того, что Траляля
Испортил погремушку, –
Хорошую и новую
испортил погремушку."
Перед боем Траляля и Труляля отправились по домам, чтобы надеть на себя доспехи: крышки от кастрюль, совки для угля, диванные валики и каминные коврики. Они договорились, что ровно в пять часов они выйдут из дома навстречу друг другу и встретятся для боя где-нибудь по пути. Но как ни странно, они прошли весь путь до домов друг друга ни разу не повстречавшись.
Напишите программу, которая вычисляет минимальное время, за которое Траляля и Труляля могли дойти до домов, не встретившись друг с другом, а также максимальное ближайшее расстояние, на котором они могли пройти друг от друга, без ограничений на время пути.
Первая строка ввода содержит два целых числа `N`, `M` (`2\ ≤\ N,\ M\ ≤\ 25`) – размеры леса, в котором живут Траляля и Труляля. Следующие `N` строк ввода содержат по `M` символов – карта леса. Символ 'A' означает дом Траляля, а символ 'U' – дом Труляля. Символ '#' означает препятствие, а символ '.' – свободную клетку. Гарантируется, что существует путь по свободным клеткам от одного дома до другого. При движении героев из клетку в клетку считается, что встреча произошла, если в конце хода они оказываются в одной клетке, или если они движутся из соседних клеток навстречу друг другу. При определении ближайшего расстояния рассматриваются только расстояния между Траляля и Труляля в конце хода. Оба героя могут останавливаться, пропускать ход или проходить по одной клетке несколько раз.
Вывести в первой строке одно целое число `T` – минимальное время путешествия без встречи. Во второй строке вывести путь Траляля в виде последовательности из `T` символов 'N', 'S', 'W', 'E' и '.' ('N' – вверх, 'S' – вниз, 'W' – влево, 'E' – вправо, '.' – пропуск хода). В третьей строке вывести аналогичным образом путь Труляля. Если существует несколько вариантов для путей, то можно вывести любой вариант. В четвертой строке вывести одно вещественное число – максимальное ближайшее расстояние во время путешествия с точностью `10^{-3}`. В четвертой строке вывести путь Траляля, обеспечивающий это расстояние, а пятой – путь Труляля. Если существует несколько вариантов таких путей, максимизирующих это расстояние, то вывести минимальный по времени вариант (можно вывести любой из них). Если не существует способа путешествия без встречи, то в первой и единственной строке вывести число `-1`.

Пример ввода

4 5
.....
.###.
A..#.
....U

Пример вывода

5
EESEE
WWWWN
3.162
...SEE.EE
NNNWWWWSS

J. Траляля и Труляля делят лес

Ограничения: время – 200ms/500ms, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Поссорившись, Траляля и Труляля решили поделить все деревья в лесу. Перед разделом леса они измерили расстояние между каждой парой деревьев. При этом путь между этими деревьями проходил вдали от других деревьев. Таким образом, может оказаться так, что "прямое" расстояние `D_{ij}` между деревьями `i` и `j` может оказаться больше суммы путей `D_"ik"` и `D_"kj"`. Такой способ измерения расстояний был использован по следующей причине: при охране своих деревьев может потребоваться быстро бежать от одного дерева к другому, а если на пути окажется какое-то дерево, то можно удариться о него лбом.
Напишите программу, которая разделит деревья в лесу между Траляля и Труляля таким образом, чтобы максимальное расстояние между своими деревьями у каждого было минимально. Максимальное расстояние между деревьями Траляля должно быть больше или равно максимальному расстоянию между деревьями Труляля.
Первая строка ввода содержит одно целое число `N` (`3\ ≤\ N\ ≤\ 100`). Далее следует `(N-1)` строка, `i`-я cтрока ввода содержит `(i-1)` целое число `D_{ij}` в диапазоне от 1 до `10^6` – расстояния от `i`-го до `j`-го, где `j` от 1 до `i-1`.
Вывести в первой строке одно целое число `K` (`K\ <\ N`) – количество деревьев у Траляля в распределении, минимизирующих максимальное расстояние между своими деревьями, во второй строке выведите `K` чисел – номера этих деревьев. Если существует несколько вариантов, минимизирующих расстояние между деревьями Траляля, выведите из них вариант, минимизирующий расстояние между деревьями Труляля.

Пример ввода

4
1
4 5
2 2 3

Пример вывода

3
1 2 4
loading