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

Назад

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

Подразделы

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

Дата и время

21/12/2024 22:18:37

Авторизация

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

printЗадачи очного тура личного первенства 2010

printA. Телефонный номер

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

12036.jpg
Для упрощения запоминания номеров цифры часто заменяют буквами. На клавиатуре всех современных телефонов есть соответствующие обозначения, помогающие набирать такие номера.
БуквыABCDEFGHIJKLMNOPQRSTUVWXYZ
Цифра23456789
Напишите программу, которая переводит номер телефона с буквами в обычный номер из цифр.
Ввод содержит одну или более строк. Каждая строка содержит номер, состоящий из прописных латинских букв, цифр и символов '-' (минус), и ее длина не превышает 30 символов.
Для каждого номера из ввода вывести на отдельной строке обычный номер, заменив буквы по указанной выше таблице.

Пример ввода

1-888-SHOP-IBM
EASY-2-SOLVE

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

1-888-7467-426
3279-2-76583

printB. Пасьянс

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

В пункте меню "Статистика" игры "Пасьянс" можно увидеть вероятность выигрыша, а также максимальные длины полос из выигрышей и проигрышей. Очевидно, что возможность выигрыша в пасьянсе определяется только начальной раскладкой, поэтому вероятность почти не будет меняться при возрастании числа игр, а вот максимальные длины полос будут постепенно возрастать.
Напишите программу, которая определит математические ожидания максимальной длины полос из выигрышей и проигрышей после проведения `N` игр.
В первой строке ввода содержатся два числа – количество игр `N` (`1\ ≤\ N\ ≤\ 500`, целое) и вероятность выигрыша `P` (`0\ ≤\ P\ ≤\ 1`, вещественное).
Вывести два числа через пробел – математические ожидания максимальной длины полос из выигрышей и проигрышей после проведения `N` игр с точностью не менее `10^{-5}`.

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

3 0.50000

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

1.37500 1.37500

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

2 1.00000

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

2.00000 0.00000

printC. Подземелье

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

Два спелеолога решили обследовать подземелье, спустившись в него с двух различных входов и встретившись внутри. При этом они договорились, что во время обследования всегда будут находиться на одинаковой глубине, поднимаясь и опускаясь на другой уровень подземелья одновременно.
Напишите программу, которая определит по плану подземелья минимальное время до встречи.
Первая строка ввода содержит два целых числа `N` и `M` – размеры подземелья (`2\ ≤\ N,\ M\ ≤\ 100`), далее следует `N` строк, содержащих по `M` символов '.' или ‘#’ – план подземелья. Символом '.' обозначается проход, а символом '#' – стена. В начальной позиции первый спелеолог находится в левом верхнем углу, а второй – в правом верхнем углу подземелья. Верхние углы подземелья свободны от препятствий. За одну единицу времени спелеолог может перейти в соседнюю клетку по вертикали или горизонтали.
Вывести одно целое число – минимальное время до встречи спелеологов в подземелье. Если встреча не может состояться, вывести число `-1`.

Пример ввода

4 7
.#####.
.#...#.
...#.#.
####...

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

10

printD. Как в 4 приема превратить зиллион цифр в одну?

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

Возьмем последовательность из `n` цифр. На каждом шаге мы можем расставить знаки + в произвольном месте между цифрами и найти сумму получившегося выражения. Если сумма состоит из более чем одной цифры, мы можем применить к ней аналогичный прием. Доказано, что для превращения любой конечной последовательности цифр в одну цифру, нужно выполнить такое суммирование не более чем 4 раза.
Рассмотрим, как это сделать. На первом шаге мы должны расставить знаки + так, чтобы сумма была равна числу вида `a00…00"bc"`, то есть содержала бы не более чем три ненулевых цифр. При этом достаточно разбивать последовательность цифр только на слагаемые из одной или двух цифр. Сумма трех ненулевых цифр не будет превышать 27, и на следующем шаге мы получим сумму либо из одной цифры, либо 10 (для `a+b+c=19`), и в этом случае придется выполнить четвертое суммирование.
Напишите программу, которая разбивает последовательность цифр на слагаемые из одной или двух цифр, сумма которых будет содержать не более чем три ненулевые цифры.
Ввод содержит последовательность из не более чем `10^6` цифр.
Вывести разбиение на слагаемые.

Пример ввода

1234567

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

12+34+5+67

printE. Паук и муха

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

Паук сплел свою паутину на квадратном окне. Для перемещения по паутине паук может выбрать один из углов окна и сделать прыжок в точку, расположенную точно на середине отрезка между его текущим положением и выбранным углом окна. Муха запуталась в паутине, и паук хочет подобраться к ней как можно ближе, сделав не более `K` прыжков.
В первой строке ввода указаны два целых числа – размер стороны окна `S` (`1\ ≤\ S\ ≤\ 10^8`) и количество прыжков `K` (`1\ ≤\ K\ ≤\ 100`). Во второй строке указаны два целых числа – координаты паука `X_s`, `Y_s` (`0\ ≤\ X_s,\ Y_s\ ≤\ S`). В третьей строке указаны два целых числа – координаты мухи `X_f`, `Y_f` (`0\ ≤\ X_f,\ Y_f\ ≤\ S`).
Вывести в первой строке количество прыжков `M` (`0\ ≤\ M\ ≤K`), необходимых пауку, чтобы подобраться к мухе как можно ближе, а во второй строке – последовательность номеров выбираемых углов окна для выполнения прыжков. Угол с координатами `(0,0)` имеет номер 1, угол `(S,0)` – 2, угол `(0,S)` – 3, угол `(S,S)` – 4.

Пример ввода

10 2
5 5
1 6

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

2
1 3

printF. Перепись населения

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

Британские ученые обнаружили в джунглях затерянную деревню и решили выяснить возраст всех жителей. Аборигены из-за отсутствия календаря и письменности не могут указать свой год рождения, но они смогли вспомнить на сколько примерно сезонов дождей один из жителей старше другого для некоторых пар жителей.
Напишите программу, которая на основании полученной информации установит минимально возможный возраст каждого жителя деревни.
Первая строка ввода содержит два целых числа — количество жителей в деревне `N` (`2\ ≤\ N\ ≤\ 1000`) и количество сравнений жителей по возрасту `M` (`1\ ≤\ M\ ≤\ N*(N-1)/2`). Далее следует `M` строк, в каждой строке четыре целых числа — номера жителей `X` и `Y`, сравниваемых по возрасту, (1 ≤ X, Y ≤N), затем минимум и максимум разницы в возрасте между ними `a` и `b` (`1≤\ a\ ≤\ b\ ≤\ 100`). Каждая такая запись означает следующее "Житель `X` старше жителя `Y` не менее чем на `a` лет, но не более чем на `b` лет". Каждая пара жителей встречается в записях не более одного раза.
Вывести `N` строк, на `i`-й строке вывести минимально возможный возраст `i`-го жителя. Если в данных ученых есть противоречия, то вместо возрастов жителей вывести сообщение "No solution" (без кавычек).

Пример ввода

5 3
1 3 10 12
2 1 25 40
4 3 30 40

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

10
35
0
30
0

printG. Good or Bad?

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

Let the sum of the square of the digits of a positive integer `S_0` be represented by `S_1`. In a similar way, let the sum of the squares of the digits of `S_1` be represented by `S_2` and so on. If `S_i\ =\ 1` for some `i`, then the original integer `S_0` is said to be good number. A number, which is not good, is called bad number. For example 7 is a good number since `7\ →\ 49\ →\ 97\ →\ 130\ →\ 10\ →\ 1` and 4 is an bad number since `4\ →\ 16\ →\ 37\ →\ 58\ →\ 89\ →\ 145\ →\ 42\ →\ 20\ →\ 4`.
The input consists of several test cases, the number of which you are given in the first line of the input. Each test case consists of one line containing a single positive integer `N` smaller than `10^9`.
For each test case, you must print one of the following messages:
Case #`p`: `N` is a good number.
Case #`p`: `N` is a bad number.
Here `p` stands for the case number (starting from 1). You should print the first message if the number `N` is a good number. Otherwise, print the second message.

Sample Input

3
7
4
13

Sample Output

Case #1: 7 is a good number.
Case #2: 4 is a bad number.
Case #3: 13 is a good number.

printH. Рикошет

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

12053.png
Абдулла спрятался от выстрелов за забором, но красноармеец Сухов решил применить рикошет пули от цистерны, чтобы попасть в бандита. Известно, что при рикошете угол падения равен углу отражения (см. рис).
Напишите программу, которая рассчитает направление выстрела.
В первой строке ввода содержатся четыре целых числа – координаты цели `X_a`, `Y_a` (`0\ ≤\ X_a,\ Y_a\ ≤\ 10^4`) и координаты стрелка `X_s`, `Y_s` (`0\ ≤\ X_s,\ Y_s\ ≤\ 10^4`). Во второй строке четыре целых числа – координаты концов забора `X_1`, `Y_1`, `X_2`, `Y_2` (`0\ ≤\ X_1,\ Y_1,\ X_2,\ Y_2\ ≤\ 10^4`) В третьей строке три целых числа – координаты центра цистерны `X_c`, `Y_c` (`0\ ≤\ X_c,\ Y_c\ ≤\ 10^4`) и ее радиус `R_c` (`1\ ≤\ R_c\ ≤\ 1000`). Цистерна и забор не пересекаются и не соприкасаются. Координаты цели и стрелка находятся вне цистерны и не рядом с забором. Отрезок между стрелком и целью пересекается (или соприкасается) с отрезком забора.
Вывести одно число – направление выстрела `D` в градусах с точностью не менее `10^{-4}` (`0\ ≤\ D\ <\ 360`). Если попасть в цель невозможно, то вывести сообщение "No solution" (без кавычек).
Примечание. Пуля не может пролететь сквозь забор или соприкасаться с забором. В тестах с существующим решением траектория пули проходит на значительном удалении от забора (не менее 0.1).

Пример ввода

4 4 4 0
3 2 5 2
1 2 1

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

135.0000
loading