e-olymp 2371. Черный квадрат

Условие

Вдохновленный шедевром Казимира Малевича «Черный квадрат», Петр Палевич решил создать собственную версию картины. Он приготовил полотно в виде прямоугольной сетки с $m \times n$ белыми квадратами — $m$ строк по $n$ ячеек каждая.

Петр покрасил некоторые клетки в черный цвет так, что черные ячейки сформировали квадрат размером $s \times s$ ячеек. Но на следующий день Петр разочаровался в своем творении и уничтожил его, разрезав полотно горизонтальными полосами размера $1 \times n$, после чего сжег их в камине.

На следующее утро Петр передумал и решил восстановить картину. Он попытался найти ее останки в камине, и, к счастью, одну из полос, а именно $k$-ую сверху, огонь не тронул.

Теперь Петр задумался, можно ли восстановить картину на основе этой полосы. Помогите ему сделать это.

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

Первая строка содержит четыре целых числа: $m$, $n$, $s$ и $k$ $ \left( 1 \leqslant m, n \leqslant 5000, 1 \leqslant s \leqslant \min \left( m, n \right), 1 \leqslant k \leqslant m \right) $.

Вторая строка содержит $n$ символов и описывает $k$-ую строку картины, ‘.’ означает белую клетку, ‘*’ означает черную клетку.

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

Если изображение может быть однозначно восстановлено, то следует вывести «Unique». Если существует несколько вариантов восстановления картины, то вывести «Ambiguous». Если ни одной соответствующей картины не существует, вывести «Impossible».

Тесты

Ввод Вывод
$3$ $4$ $2$ $3$
..**
Unique
$4$ $4$ $2$ $3$
*.*.
Impossible
$3$ $5$ $2$ $2$
.**.
Ambiguous
$2$ $8$ $1$ $2$
……*.
Unique

Код

String

C-string

Решение

Основная сложность задачи заключается в аккуратном рассмотрении всех возможных вариантов. После прочтения строки символов, которую представляет собой вытащенная из огня полоска, исследуем ее на количество подряд идущих символов ‘*’. Если последовательностей из звездочек в одной строке несколько, то никакие добавленные полоски не смогут сделать из нее квадрат, и тогда решений нет. Иначе дальнейшее решение делится на два случая:

  1. Спасенная из огня полоска не содержит звездочек. Тогда мы проверяем, может ли поместиться квадрат из звездочек хотя бы в одну из двух частей, на которые эта полоска делит картину. Если да, проверяем, однозначно ли определяем этот квадрат, или же имеется несколько вариантов его возможного расположения в них.
  2. Спасенная из огня полоска содержит звездочки. Тогда, если количество звездочек не совпадает с длиной стороны квадрата, то построить его невозможно, а иначе проверяем, однозначно ли определяем этот квадрат. Здесь необходимо аккуратно рассмотреть все «особенные» случаи, такие как квадрат, состоящий из одной звездочки, а также первая и последняя полоски картины. Очевидно, что в этих случаях расположение квадрата определяется единственным образом.

Если сравнивать, что выгоднее использовать в данной задаче для задания спасённой из огня полоски — строку или массив символов, — то использование строки способствует немного более быстрому решению задачи, чем массив символов; объём используемой памяти при этом не изменяется.

Ссылки

Условие на e-olymp.com
Код с использованием string на ideone.com
Код с использованием c-string на ideone.com

e-olymp 108. Среднее число

Задача

Дано три различных числа [latex]a[/latex], [latex]b[/latex], [latex]c[/latex]. Вывести среднее из них.

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

Числа [latex]a[/latex], [latex]b[/latex], [latex]c[/latex] целые и по модулю не превышают 1000.

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

Вывести среднее среди трех чисел.

Тесты

Входные данные Выходные данные
10 4 9 9
2 256 8 8
1 2 3 2

Код программы:

Решение задачи

Я рассмотрел все возможные случаи, а именно 2 на каждую переменную, в которых она может оказаться «средней», удовлетворяя условию. [latex]a[/latex] средняя, если она лежит между [latex]b[/latex] и [latex]c[/latex] или между [latex]c[/latex] и [latex]b[/latex], [latex]b[/latex] если она лежит между [latex]a[/latex] и [latex]c[/latex] или между [latex]c[/latex] и [latex]a[/latex], и [latex]c[/latex] — остальных случаях.

Ссылки

  • Задача на сайте e-olymp
  • Код решения в Ideone

A60г

Задача:
Пусть [latex]D[/latex] — заштрихованная часть плоскости и пусть u определяется по [latex]x[/latex] и [latex]y[/latex] следующим образом: [latex] u=\begin{cases}x^{2}-1, ; \text{ if } (x, y)\in D \\sqrt{\left| x-1 \right| } ; \text{ another case }\end{cases}[/latex] (запись [latex] (x, y)\in D [/latex] означает, что точка с координатами [latex]x, y[/latex] принадлежит [latex]D[/latex]).

Даны действительные числа [latex]x[/latex] и [latex]y.[/latex] Определить [latex]u.[/latex]

a60%d0%b3
Тесты:

Вход Выход
[latex]x[/latex] [latex]y[/latex] [latex]u[/latex]
1 0.3 0.3 0.836660
2 1 1 0.000000
3 2 2 1.000000
4 0 0 -1.000000

Код на языке C++:

Код на языке Java:

Решение:
Для решения задачи проверим не принадлежит ли выбранная точка полуплоскости [latex] y<0 [/latex].Затем следует проверить не лежит ли выбранная точка вне полукруга, радиус которого равен 1 . Следующим действием нужно проверить не находиться ли точка в вырезанной четвертине маленького круга, радиус которого равен 0.3 .
Ссылки:
Онлайн компилятор ideone C++ .
Онлайн компилятор ideone Java .

e-olymp 902. Уровень учебных достижений

Задача взята с сайта e-olimp

Задача. Установить уровень учебных достижений ученика (начальный, средний, достаточный, высокий) соответственно к заданной оценки (от 1 до 12).

Тесты

В тестах нужно отобразить следующее:

  • Оценки от 1 до 3 —  начальный уровень;
  • от 4 до 6 — средний;
  • от 7 до 9 — достаточный;
  • от 10 до 12 — высокий.
Оценка \ Уровень Intial

(начальний)

Average

(средний)

Sufficient

(достаточний)

High

(высокий)

1, 2, 3 +
4, 5, 6 +
7, 8, 9 +
10, 11, 12 +

Решение

Оценки могут быть строго от 1 до 12 (по условию). Примем оценку за число [latex]a[/latex]. Оценка это число больше или равно 1 и меньше либо равно 12. Мы разбиваем сегмент [1, 12] на 4 сегмента — [1, 3], [4, 6], [7, 9], и [10, 12].  В каждом сегменте будет свое условие — [latex]a\leq3[/latex], [latex]a\leq6[/latex], [latex]a\leq9[/latex], и [latex]a\leq12[/latex].  Мы берем условие [latex]a\leq3[/latex], и, если это правда — пишем Intial.  Если ложь проверяем  [latex]a\leq6[/latex], если это правда — результат Average. Если ложь, то мы проверяем [latex]a\leq9[/latex]. В случае правды — результат Sufficient. Но если это все, начиная от [latex]a\leq3[/latex] заканчивая [latex]a\leq9[/latex] ложь, тогда  в решении будет слово High.

Код 

Код на IDEONE можно увидеть здесь.

Проверить правильность задачи можно здесь.

Skynet — The Chasm

Вторая по счету игра на сайте называется Skynet — The Chasm. В игре мы будем управлять мотоциклистом, который изо всех сил пытается попасть на другую сторону пропасти и остановиться на конечной платформе.

Ни о чем не подозревающий мотоциклист

Ни о чем не подозревающий мотоциклист

Инициализация

В начале нам сообщают всевозможные данные о будущем пути: расстояние от мотоциклиста до пропасти (int R), длину пропасти (int G), длину платформы для приземления (int L).

Игровой цикл

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

Вход

Каждый новый ход (т.е. после каждого следующего выполненного действия в самом цикле while) нам сообщают скорость мотоциклиста (int S) и его позицию на дороге (int X).

Выход

В выходной поток необходимо вывести одну строку. Тут разработчики представляют нам 4 варианта:

  • ускоряться (SPEED);
  • тормозить (SLOW);
  • ехать вперед без ускорения (WAIT);
  • прыгать (JUMP).

Перевод строки на новую обязателен.

Тест 1

В начале нам представлен базовый код программы.

 

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

Спасательный код
Мы, с чувством выполненного долга, наблюдаем как мотоциклист, с улыбкой на лице, наконец перепрыгивает первую пропасть, а затем и вторую и третью. Понимая, что мотоциклист должен прыгнуть в момент, когда пропасть будет перед ним (т.е. за 1 шаг до нее), приказываем ему ускоряться до того момента (пока расстояние до пропасти не станет равным 1 (X == R — 1)). То есть пока положение мотоциклиста Х меньше, чем расстояние до пропасти R минус длинна пропасти G (X < R — G) мотоциклист будет ускоряться. После прыжка нам нужно затормозить, то есть если положение мотоциклиста X будет уже за пропастью (X > R — G), но меньше чем конец самой дороги (X < R + G + L), он будет тормозить.

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

Еще более спасательный код

И тут вступает в игру переменная, которую до этого момента нам не приходилось использовать в программе, а именно, скорость мотоциклиста S.

После тысячи непройденых тестов начинаешь понимать, что ты что то упустил. Вот тут то и вступает в игру всеми любимый «любимый» magic number равный, в данном случае, единице. И вправду, для того, чтобы перелететь пропасть нам потребуется скорость всего лишь на 1 больше, чем длинна этой пропасти. То есть если скорость будет равна длине пропасти + 1, то мы будем ехать с этой постоянной скоростью, в противном случае будем ускоряться. С этим замечанием программа позволяет с легкостью останавливаться на конечной платформе любой длинны.

Кажется, что мы предусмотрели все варианты развития событий, но не тут то было. Разработчики устанавливают новую, увлекательную задачу. Что будет, если начальная скорость будет не равна 0, спрашивают они? И мы пускаемся в глубокие размышления.

Код дающий, в прямом смысле, крылья

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

На С++:

На Java:

 

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

А 42

Задача

Даны действительные числа [latex]x,y[/latex]  [latex](x\neq y)[/latex]. Меньшее из этих двух чисел заменить их полусуммой, а большее — их удвоенным произведением.

Тесты

Было дано Стало после проверки Комментарий
x y x y
38.76 -24.33 -1886.0615999  7.215 Пройден
11.346 23.228 17.287 527.0898 Пройден
-2444.2 1231.444 -606.378 -6019790.8496 Пройден
767.2 -1455.24 -2232920.256 -344.02 Пройден
0 213.4 106.7 0 Пройден
1111 0 0 555.5 Пройден
123.4 123.4 Ничего не выйдет, х=у Не пройден
0 0 Ничего не выйдет, х=у Не пройден

Код программы:

 

Для получения ответа переменной необходимо преодолеть критерий [latex](x\neq y)[/latex].

Если же [latex](x\neq y)[/latex], то программа сравнивает сами переменные. Тут может быть два случая:

  • Если  [latex]x>y[/latex], то начальные значения переменных мы должны изменить на [latex]x=\frac{x+y}{2}[/latex], a [latex]y=2*x*y[/latex].
  • Если [latex]y>x[/latex], то начальные значения переменных мы должны изменить на [latex]y=\frac{x+y}{2}[/latex], a [latex]x=2*x*y[/latex].

Программа вначале высчитывает конечные х и у по формулам и при выполнении условий просто присваивает переменным значения. Тем самым мы упрощаем программу (т.к. расчет значений идет только один раз вместо двух).

Второй вариант решения.

Код программы:

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

Код на Java