e-olymp 7258. Числовые операции

Условие

На доске записано число $1$. Каждую секунду Петя может провести над числом одну из двух операций: либо прибавить к числу $1$, либо произвольным образом переставить цифры числа (но так, чтобы на первом месте оказался не ноль). После этого Петя вытирает с доски старое число и записывает вместо него получившееся.

Задание

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

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

Первая строка входного файла содержит число $T (1 \leqslant T < 10^4$), которое задает количество чисел во входном файле, для которых требуется найти ответ. В последующих T строках задано по одному натуральному числу $N_i$,$2\leqslant N_i < 10^9$, $1 \leqslant i \leqslant T$. Известно, что среди чисел $N_i, 1 \leqslant i \leqslant T$, нет одинаковых.

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

Выходной файл должен содержать $T$ чисел по одному в строке — в $i$-й строке должно быть записано наименьшее количество секунд, которое понадобится истратить Пете, чтобы, начав с единицы, записать на доске соответствующее число $N_i$.

Тесты

Ввод Вывод
1 3

3

955

21

1

48

12

2 4

137

318

3028

300
39

40

71

50

Код

Решение

Количество цифр в числе никогда не уменьшается, а может увеличиться только при добавлении к числу, состоящее только из девяток и единицы. Поэтому, для достижения числа $N$ сначала нужно дойти до числа $10$, потом до чисел $99$ и $100$ и т.д., пока кол-во цифр в числе не будет таким, как требуется.
Наименьшее кол-во операций,необходимое для того,чтобы перейти от числа $10^{n-1}$ до заданного $n$-значного числа $N=$:
1.Если число $N$ содержит хотя бы одну цифру, отличную от нуля, кроме первой, то кол-во операций можно посчитать по формуле summa(N) + nonzero(N) edinica(N)-1, где summa(N)-сумма цифр числа, nonzero(N)-кол-во цифр,отличных от нуля, на всех позициях числа $N$, кроме последней, edinica(N)-число,которое равно единице,если хотя бы на одной позиции числа $N$, кроме последней,есть единица, или равна нулю, если единиц на этих позициях нет.
2.Если все цифры числа $N$, кроме первой,нулевые,а первая цифра больше единицы, то кол-во операций можно посчитать по формуле summa(N-1)+nonzero(N-1) edinica(N-1).

Доказательство формул

Для дальнейшего удобства обозначим перестановку цифр числа через $\Rightarrow$.
Число $N$-заданное число, число $n$-кол-во цифр числа $N$. Если $n=1$,$N=7$,то для того,чтобы дойти от единицы до заданного числа,потребуется $N-1$ операций. В нашем случае 6 операций
($1+1=2,
2+1=3,

6+1=7$)
Если $n\geq2$,то для этого достаточно привести пример цепочки,подсчитывающая кол-во операций,которая число $10^{n-1}$ превращает в $N$. Но вместо прямого порядка действий будем делать обратный эквивалентный. То есть, $N \Rightarrow 10^{n-1}$: за одну операцию мы можем или уменьшить число на единицу, или переставить в нем цифры так,чтобы на первом месте оказался не нуль. Могут возникнуть следующие случаи:
1.Если $N=10^{n-1}$, то кол-во операций равно summa(N) + nonzero(N)-edinica(N)-1 $= $0.
Например, возьмем число $1000$. Сумма цифр $= 1$, количество ненулевых цифр $= 1$, количество единиц $= 1$, соответственно значение $= 1+1-1-1 =0$.

2.Если $N!=10^{n-1}$ и число первая цифра числа $N$ равна единица:
Сначала отнимаем от числа $N$ столько единиц, чтобы последняя цифра стала нулем,далее
Переставим местами последнюю цифру с какой-нибудь другой,отличной от нуля,кроме первой, и опять отнимем кол-во единиц,чтобы последняя цифра стала нулевой. Повторять будем до тех пор,пока все цифры,кроме первой,станут нулями.
Например,возьмем число $137$.
$137-1=136$, $136-1=135$, $135-1=134$, $134-1=133$ ,$133-1=132$ ,$132-1=131$, $131-1=130$ ,$130 \Rightarrow 103$ , $103-1=102$, $102-1=101$, $101-1=100$
Кол-во операций $= 11$. Проверяем по формуле. summa(137)=11, nonzero(137)=2, edinica(137)=1. Итого получаем $11+2-1-1=11$

3.Если первая цифра числа $N$ больше единицы, но хотя бы на одной позиции числа,кроме последней, есть единица, делаем:
Сначала уменьшаем последнюю цифру,пока она не станет нулем, затем переставляем цифры: поставим на место первой цифры единицу, а первую цифру сделаем последней, а нуль, который стоял в конце числа, поставим на место бывшей первой. После этого будем действовать согласно алгоритму пункта №2.
Например, число $318$.
$318-1=317$, $317-1=316$, $316-1=315$, $315-1=314$, $314-1=313$, $313-1=312$, $312-1=311$, $311-1=310$, $310 \Rightarrow 103$, $103-1=102$, $102-1=101$, $101-1=100$
Итого $12$ операций. Просчитываем по формуле summa(318)+nonzero(318)-edinica(318)-1.
Получаем $12+2-1-1=12$.

4.Если ни на одной из позиций числа $N$, кроме,возможно,последней, нет единиц, но в числе есть хотя бы одна ненулевая цифра,кроме первой, то делаем:
Последнюю цифру делаем нулевой, переставляем последний нуль с любой ненулевой цифрой,кроме первой, пока на последнем месте не окажется последняя ненулевая цифра (не считая первую), последнюю ненулевую уменьшаем не до нуля, а до единицы, переставим единицу с первой цифрой, новую последнюю цифру сделаем нулевой.
Например, число $3028$.
$3028-1=3027$, $3027-1=3026$, $3026-1=3025$, $3025-1=3024$, $3024-1=3023$, $3023-1=3022$, $3022-1=3021$, $3021-1=3020$, $3020 \Rightarrow 3002$, $3002-1=3001$, $3001 \Rightarrow 1003$, $1003-1=1002$, $1002-1=1001$, $1001-1=1000$
Получаем $14$ операций. Проверяем по формуле summa(3028)+nonzero(3028)-edinica(3028)-1 $= 13+2-0-1=14$.

5.Если первая цифра числа $N$ больше единицы, а все другие цифры-нулевые, то делаем:
Отнимем от числа $N$ единицу, а дальше будем использовать один из раннее алгоритмов в пунктах 2-4.
Например, число $300$.
$300-1=299$, $299-1=298$, $298-1=297$, $297-1=296$, $296-1=295$ $=$ … $291-1=290$, $290 \Rightarrow 209$, $209-1=208$ $=$ … $202-1=201$, $201 \Rightarrow 102$, $102-1=101$, $101-1=100$
Итого $22$ операции. summa(300-1)+nonzero(300-1)-edinica(300-1) $= 20+2-0=22$.

6.Подсчет операций от $1$ до $10^{n-1}$.
Для того,чтобы перейти от числа $10^{n-1}$ к $10^n$, понадобится число $10^n – 1$,которое равно $k$. По предыдущим алгоритмам, понадобится:
summa(k)+ nonzero(k) edinica(k) -1 $=$ $9 \cdot n + (n-1) -0 -1=10 \cdot n – 2$ операций, где b $>$ 1.
Если $n=1$, то кол-во операций $= 10 \cdot n – 2 =8$.

Кол-во операций можно посчитать по формуле $(5 \cdot n -1) \cdot (n – 1)$ ,где $n$- кол-во цифр заданного числа.

Ссылки

e-olymp 7233. Отрезки

Задача

Петя очень любит игрушки в форме геометрических фигур. Недавно он заметил, что среди его игрушек нет ни одного треугольника. Это очень огорчило Петю, поэтому он отправился в ближайший магазин с целью покупки новенького треугольника. В магазине Пете сказали, что все треугольники уже давно раскупили, но в наличии есть [latex]N[/latex] прямых отрезков.

Отрезки пронумерованы последовательными натуральными числами, начиная с единицы. Отрезок номер [latex]i[/latex] характеризуется двумя числами — длиной [latex]L_i[/latex] и ценой [latex]C_i[/latex]. Петя очень умный, поэтому знает, что желаемый треугольник он может сложить из трех отрезков. Более того, наш герой знает, что треугольник возможно сложить только из таких трех отрезков, среди которых длина любого отрезка строго меньше суммарной длины двух других. Итак, мальчик решил купить ровно три таких отрезка. Разумеется, он хочет сэкономить как можно больше денег на мороженое, поэтому стремится потратить как можно меньше денег на покупку треугольника.

Задание

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

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

В первой строке входного файла записано единственное число [latex]N[/latex] — количество отрезков. В следующих [latex]N[/latex] строках записана информация о самих отрезках. Каждая такая строка содержит соответствующие [latex]L_i[/latex] [latex](1 \leqslant L_i \leqslant 10^9)[/latex] и [latex]C_i[/latex]. Цены образуют перестановку чисел от [latex]1[/latex] до [latex]N[/latex], то есть являются попарно различными натуральными числами, не превосходящими [latex]N[/latex].

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

Выходной файл должен содержать единственное число — минимальную стоимость трех отрезков, из которых можно сложить треугольник, либо «-1» (кавычки для наглядности) в том случае, если выбрать ровно три таких отрезка невозможно.

Тесты

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

Код

 

 

Решение

Для начала запишем все отрезки в массив в виде структур. Отсортируем их по цене в порядке возрастания, чтобы позже иметь возможность «отсекать» слишком дорогие отрезки. Далее мы начинаем перебирать все возможные тройки отрезков. На первом уровне цикла ставим условный оператор. Если на [latex]n[/latex]-ой итерации цикла будет отрезок с ценой больше текущей наименьшей цены треугольника, то мы можем выходить из массива и выводить текущую минимальную стоимость, т.к. все последующие отрезки будут дороже (пользуемся сортировкой и тем, что цены отрезков образуют перестановку от [latex]1[/latex] до [latex]N[/latex]). Далее на втором и третьем уровнях цикла мы также перебираем все отрезки от дешевых к дорогим и при обнаружении тройки отрезков, цена которых меньше текущей минимальной, записываем их в переменную [latex]cheapest[/latex]. При этом на втором уровне цикла проверяем, не больше ли сумма цен двух отрезков текущей минимальной, чтобы не проверять лишние тройки.

Ссылки

e-olymp 4720. Новая игра Серёжи

Задача

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

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

Помогите Серёже понять, расстроится он или нет.

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

Сначала с клавиатуры вводятся координаты левого верхнего угла чёрного прямоугольника, затем правого нижнего, затем координаты углов белого прямоугольника в том же формате и в конце — координаты точки. Все координаты — целые числа, по модулю не превышающие $10000$.

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

Программа должна выводить слово «SAD», если Серёжа расстроится (когда точка попадает на границу Серёжа считает её принадлежащей чёрному листу, потому что не любит расстраиваться), и «HAPPY» — в обратном случае.

Тесты

Входные данные Выходные данные
1 2 10 5 3 4 4 6 1 2 9 HAPPY
2 2 10 5 3 4 4 6 1 6 3 SAD
3 0 0 0 0 1 1 1 1 0 0 HAPPY
4 1 3 3 1 2 3 4 1 3 2 SAD
5 1 3 3 1 2 3 4 1 2 2 HAPPY

Код

Сокращенный код

 

Решение

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

Ссылки

e-olymp 75. Пираты и монеты

Задача

[latex]n[/latex] пиратам удалось справедливо разделить клад из [latex]m[/latex] золотых монет — каждый получил свою часть согласно своему пиратскому рангу и стажу. Самый молодой пират взял [latex]a[/latex] монет, а каждый следующий пират брал на одну монету больше, чем предыдущий его коллега. Последним был капитан, которому досталось вдвое больше от запланированного, очевидно, что после него монет больше не осталось.

Сколько было пиратов вместе с капитаном, если известны [latex]a[/latex] и [latex]m[/latex]. Так как капитан без команды просто пират, то [latex]n > 1[/latex].

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

Два натуральных числа [latex]a[/latex] и [latex]m[/latex] ([latex]1 \leq a \leq 100, m < 15150[/latex]). Входные данные корректны.

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

Количество пиратов [latex]n[/latex].

Тесты

 #  ВХОДНЫЕ ДАННЫЕ  ВЫХОДНЫЕ ДАННЫЕ
 1  5 25  3
 2  3 24  4
 3  4 38  5
 4  5 55  6
 5  6 75  7

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

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

Для решения задачи воспользуемся формулой арифметической прогрессии, которая в данном случае равна: [latex](2a + n — 1)\frac{n}{2} + a + n — 1[/latex]. Отсюда получаем квадратное уравнение : [latex]\frac{n^{2}}{2} + n(a + \frac{1}{2}) + a — 1 = m[/latex], упростим и получим: [latex]n^{2} + 2an + n + 2a — 2 = 2m[/latex]. В коде задаем чему равно [latex]b[/latex], [latex]c[/latex] и [latex]d[/latex]. Где [latex]b[/latex] и [latex]c[/latex] — коэффициенты квадратного уравнения, а [latex]d[/latex] — дискриминант квадратного уравнения, который вычисляем по формуле: [latex]b^{2} — 4c[/latex]. Они нужны для нахождения корня данного квадратного уравнения. При этом ответом на задачу будет только один корень квадратного уравнения, так как количество пиратов не может принимать отрицательное значение. Поэтому вычисляем корень квадратного уравнения по формуле: [latex]\frac{-b + \sqrt{b}}{2}[/latex], тем самым получаем ответ на нашу задачу.

Код программы (с циклом)

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

В данном способе используем цикл. Как он работает: в условии цикла задаем проверку, когда наступит очередь капитана и будет выполнятся равенство вида [latex]m — 2a = 0[/latex] цикл прекратит свою работу. Пока это равенство не будет выполнятся цикл будет выполнять работу арифметической прогрессии, постоянно увеличивая количество монет [latex]a[/latex] на каждого пирата при этом, вычитая каждый раз из общего клада [latex]m[/latex], также, пока не выполняется данное равенство, считаем количество пиратов [latex]n[/latex], путем прибавления [latex]n + 1[/latex], пока работает цикл. И когда цикл прекращает свою работу, в конце учитываем капитана и к полученному количеству пиратов [latex]n[/latex] прибавляем [latex]n + 1[/latex]. И получаем ответ на нашу задачу.

Код программы (с условным оператором)

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

В данном способе воспользуемся рекурсивной функцией и условными операторами. Как это работает: внутри рекурсивной функции расписываем условные операторы, которые определяют равенством [latex]m — 2a = 0[/latex] — когда наступила очередь капитана, а пока это условие не выполняется, функция будет вызывать сама себя пока это условие не удовлетворится, функция каждый раз вызывается с новыми параметрами соответственно. Где [latex]a[/latex] — количество монет даваемое пиратам, увеличивается по рангу каждого пирата, [latex]m[/latex] — клад, от него отнимаем текущее [latex]a[/latex], и [latex]n[/latex] — количество пиратов, считаем пиратов. И в конце выводит количество пиратов. Задача решена.

Ссылки

e-olymp 1312. Шкаф

Задача

Размеры шкафа [latex] a \times b \times c [/latex]. Возможно ли его пронести через дверной проём с размерами [latex]x \times y[/latex]? Считается, что шкаф проходит в проем, если размеры, которыми его будут вносить сквозь дверь, не больше соответствующих размеров двери.

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

Целые числа [latex] a, b, c, x, y (1 ≤ a, b, c, x, y ≤ 100)[/latex].

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

Вывести строку «YES«, если шкаф пронести возможно, и «NO» если нельзя.

Тесты

Ввод Вывод
1 4 5 6 10 20 YES
2 4 5 6 3 4 NO
3 12 3 4 5 6 YES
4 12 3 6 5 6 YES
5 12 3 7 5 6 NO

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

Либо

Без условных операторов

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

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

Ссылки

e-olymp 2. Цифры

Задача

Вычислить количество цифр целого неотрицательного числа $n$.

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

Одно целое неотрицательное число $n$ [latex](0 \ge n \ge 2\cdot10^9)[/latex].

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

Количество цифр в числе $n$.

Тесты

Входные данные Выходные данные
12345 5
1 1
353628 6
5454 4
0 1

Код программы (с использованием условных операторов)

 

Код программы (без использования условных операторов)

Решение

Для первого решения задачи используем череду условных операторов ( ifelse), сравнивая $n$ с концами промежутков чисел с соответствующим количеством цифр. Обойтись без них можно, задав переменную  string, присвоив ей значение числа $n$ и используя функцию  length()в выводе (перед этим подключив библиотеку  string).

Ссылки

E-Olymp

Ideone (с условными операторами)

Ideone (без условных операторов)

e-olymp 396. Дождь

Задача

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

Как это выглядит на координатной плоскости

Будем рассматривать двумерный вариант (на плоскости) этой задачи. Пусть препятствия – это наклонные непересекающиеся отрезки, а капля имеет точечные размеры. Капля падает вертикально вниз из точки, расположенной выше любого из препятствий. Если капля при падении соприкасается с отрезком-препятствием, то она стекает по отрезку вниз, пока не упадет вертикально вниз с меньшего по высоте конца отрезка.

Напишите программу, которая по координате $X$$0$ точки появления капли над землей вычисляет координату $X$ точки соприкосновения капли с землей $(Y  =  0)$.

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

Во входном файле в первой строке содержатся два целых числа через пробел – координата $X$$0$ точки появления капли $(0  < X$$0$ $<  10000)$ и количество отрезков-препятствий $N (0  ≤ N  ≤  100)$. Далее следует $N$ строк, каждая из которых содержит четыре разделенные пробелами числа $x$$1$,  $y$$1$,  $x$$2$,  $y$$2$ – координаты левого и правого концов отрезка-препятствия (все числа целые и находятся в диапазоне от $0$ до $10000$,  $x$$1$ $ < x$$2$,  $y$$1$ $≠$ $y$$2$$)$. Отрезки не пересекаются и не соприкасаются.

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

В выходной файл вывести одно целое число – координату $X$ точки соприкосновения капли с землей.

Тесты

Входные данные Выходные данные
30 4
25 35 40 30
1 32 20 30
33 22 50 29
18 10 33 19
18
12 5
12 9 13 5
17 8 19 5
13 10 10 7
6 17 4 12
13 4 5 12
 13
40 3
12 30 21 39
41 5 45 70
20 30 25 35
 40
70 6
45 75 598 37
489 48 726 47
673 873 46 36
60 735 373 762
483 73 364 59
462 375 583 457
726

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

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

Сортируем наш динамический массив по наибольшим координатам $y$ и, если $y$ равны, по координатам $x$.

Далее составим алгоритм решения задачи:

  1. Если $X$ $ ∈ [x$$1$$, x$$2$$]$, то наша капля пересечется с данной прямой. В противном случае мы просто игнорируем данное препятствие.
  2. Тогда мы сравниваем координаты $y$$1$ и $y$$2$, выбираем из них наименьшее и присваиваем соответствующую координату $x$$1$ или $x$$2$ координате нашей капли $X$.
  3. Повторяем до тех пор, пока не будут обработаны все препятствия и выводим последнюю присвоенную координату $X$ нашей капли, так как она и будет координатой $x$ соприкосновения капли с зимой.

Ссылки

Условие задачи на e-olymp.com
Решение задачи на ideone.com

e-olymp 43. Количество участников олимпиады

Задача

Как известно, на вопрос о том, сколько у него учеников, древнегреческий учёный Пифагор отвечал так: «Половина моих учеников изучает математику, четвертая часть изучает природу, седьмая часть проводит время в молчаливом размышлении, остальную часть составляют три девы».

Секретарь олимпиады на вопрос: «Сколько зарегистрировано участников олимпиады по информатике?», отвечал подобно Пифагору: «$k$-тая часть участников начала решать первую задачу, $m$-тая часть – вторую, а $n$-ая – третью. В то же время $d$ участников решают проблему: «С чего начать?». Ваша задача определить количество участников олимпиады $s$ или вывести $-1$, если секретарь ошибся.

Входные данные: в одной строке заданы числа $k, n, m, d \left(1 ≤ k, n, m, d ≤ 1000 \right)$.

Выходные данные: вывести количество участников олимпиады $s$, или $-1$, если секретарь ошибся в своём сообщении.

Тесты

$k$
$n$ $m$ $d$ Выходные данные
2 4 7 3 28
4 5 2 1 20
3 7 5 4 -1
6 6 6 1 -1
2 3 6 4 -1
3 2 5 8 -1

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

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

Пусть $x$ — количество учеников Пифагора. Тогда $\frac{x} {2}$ — половина его учеников, тех, которые изучают математику. Следовательно, $\frac{x} {4}$ — ученики, которые изучают природу, а $\frac{x} {7}$ — ученики, которые проводят время в молчаливом размышлении. И, по условию задачи, есть так же три девы.
Получили уравнение вида $\frac{x} {2} + \frac{x} {4} + \frac{x} {7} + 3 = x$, в общем виде $\frac{x} {k} + \frac{x} {m} + \frac{x} {n} + d = x$.
Отсюда выходит, что $\frac{1} {k} + \frac{1} {m} + \frac{1} {n} + \frac{d} {x} = 1;$
$\frac{mnx + knx + kmx + kmnd} {kmnx} = 1;$
$(mn + kn + km)x + kmnd = kmnx;$
Отсюда получаем формулу $x = \frac{kmnd} {kmn — mn — kn — km}$.
Следовательно, если мы получаем целое число, то секретарь оказался прав, а если число дробное, то секретарь ошибся.

Для того, чтобы проверить, является ли переменная $x$ целым числом или нет, используем функцию  floor()  из встроенной библиотеки  <cmath>.

Помимо этого делаем проверку для суммы чисел $\frac{1} {k}$, $\frac{1} {n}$ и $\frac{1} {m}$, так как если оно больше $1$, то количество учеников становится отрицательным, что невозможно. В случае, если $\frac{1} {k} + \frac{1} {n} + \frac{1} {m} = 1$, а $d > 0$, то, это тоже невозможно, а значит, секретарь ошибся.

Так же делаем проверку, которая определяет, не являются ли числа $\frac{q} {k}$, $\frac{q} {n}$ и $\frac{q} {m}$ дробными, так как это бы тоже было ошибкой секретаря (напрмер, если $k = 6$, $m = 6$, $n = 6$, $d = 1$, то при подстановке в формулу мы получаем, что количество участников равно $2$, но тогда получается, что один участник решал сразу три задачи, что, по условию задачи, невозможно).

Если условие не проходит проверки, то выводится «$-1$».

Ссылки

Условие задачи на e-olymp.com
Решение задачи на ideone.com

Skynet: the Virus

Skynet


SKYNET FINALE — LEVEL 1


Вирус

Los Angeles 2029 — Resistance HQ — Review of facts:

В минувшую субботу, сотни отважных бойцов рисковали своей жизнью, чтобы уничтожить Skynet. СТОП

Используя зараженных мото-терминаторов, им удалось привить смертельный вирус к Skynet. СТОП

Проблема: Skynet борется. СТОП

Джон, ещё раз,  нам нужна ваша помощь. СТОП


Задача:

У нас в распоряжении целый граф узлов. Некоторые из них названы шлюзами. Шлюзы надо защищать от злобного Skynet агента, который способен передвигаться по связям между узлами. Способ защиты очень прост: каждый ход можно навсегда заблокировать одну связь, тем самым, через некоторое количество ходов, полностью закрыть шлюз от нежелательных гостей.

Первичная инициализация:

Первая строка: 3 целых числа N L E

  • N — Количество узлов, включая шлюзы
  • L — Количество связей
  • E — Количество шлюзов

Следующие L строк: по два числа на строку (N1, N2), означающие, что между узлами с индексами N1 и N2 присутствует связь.
Следующие E строк: по одному числу на строку, означающие индексы шлюзов.

Инициализация за каждый игровой тик:

Одно число — индекс связи, на которой находится Skynet агент.

Вывод за каждый игровой тик:

Одна строка в которой присутствует два числа C1 и C2. C1 и C2 — это индексы двух узлов, между которыми мы хотим заблокировать переход. Если между ними нет связи, возникает ошибка. В конце строки обязательно должен стоить символ перехода на новую строку.

Программа:

Идея решения: Всё предельно просто: Если агент находится вблизи одного из шлюзов, закрываем переход между агентом и этим шлюзом. Иначе закрываем переход между шлюзом и ближайшим узлом.

Переходы между узлами занесены в двумерный массив N1, далее этот массив был своеобразно отсортирован (для удобства). В игровом цикле объявляем булевую переменную AgentIsNear — агент вблизи шлюза.

Первый цикл: Проверяем каждую клетку вокруг каждого шлюза на присутствие там агента. И если он таки там есть, блокируем переход, меняем первую переменную (отвечающую за шлюз) в массиве переходов (N1) на -1 (значение, которое никогда не встретится), изменяем AgentIsNear на true и прерываем цикл.

Второй цикл: так как агент гуляет где-то далеко, то мы блокируем любой свободный проход любого шлюза.

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

Программа проходит все тесты на MEDIUM и, что удивительно, половину тестов на HARD! Взято с CodinGame

 

Skynet: The Chasm

Вторая по списку игра на сайте codingame.com проверяет умение примата пользоваться условными операторами, интуицией и программой по физике за десятый класс. По легенде, на постапокалиптических просторах Земли будущего раскинулась зловещая империя враждебных человеку роботов, но инженерный гений непокоренных программистов-взломщиков дает человечеству шанс на выживание. Подрывная деятельность начинается с малого: под дистанционный контроль удалось взять кремниевые мозги скоростного робота, внешностью и повадками напоминающего модифицированный мотоцикл. Наша задача — создать алгоритм управления, позволяющий машине преодолевать препятствия.

Инициализация:
Каждый уровень поделен на три этапа:

  1. Движение по стартовой площадке.
  2. Прыжок через пропасть.
  3. Торможение на финишной прямой.

До начала игрового цикла программа считывает данные о длине каждого из элементов уровня и сохраняет соответственно в переменные [latex]R, G, L[/latex].

Игровой цикл
На каждой итерации входной поток содержит:

  1. Координату мотоцикла [latex]X[/latex].
  2. Мгновенную скорость мотоцикла [latex]S[/latex].

В выходной поток необходимо вывести одну из четырех команд:

  1. JUMP — совершить прыжок.
  2. SPEED — увеличить скорость на единицу.
  3. SLOW — уменьшить скорость на единицу.
  4. WAIT — ждать следующего хода.

Прежде чем приступить к решению, проанализируем и формализуем задачу.
Continue reading

Ю3.44

Задача: Леспромхоз ведёт заготовку деловой древесины. Первоначальный объем её на территории леспромхоза составлял [latex]p[/latex] кубометров. Ежегодный прирост составляет [latex]k[/latex]%. Годовой план заготовки — [latex]t[/latex] кубометров. Через сколько лет в бывшем лесу будут расти одни опята?

  1. Тесты:
[latex]p[/latex] [latex]k[/latex]% [latex]t[/latex] [latex]years[/latex] Комментарий
111.50 14.57 16 Никогда Пройден: прирост компенсирует вырубку
0 0 0 0 Пройден: абстрактный случай, но результат верный
20 10 30 1 Пройден
200 30 61 16 Пройден
  1. Программный код:
  1. Формализация задачи:
    Дано начальное значение [latex]p \ge 0[/latex]. На [latex]i[/latex]-м шаге оставшийся объем древесины вычисляется из рекуррентного соотношения: [latex]p_{i} = p_{i-1} (1 + \frac {k}{100})-t[/latex]. (*)
    Определить шаг [latex]i[/latex] такой, что [latex]p_{i}<0[/latex].

  2. Алгоритм решения:
    Шаг 1: Проверка условия [latex]p_{1}[/latex] меньше [latex]p[/latex]. В случае, если если естественный прирост не компенсирует вырубку, начать рассчет. В противном случае лес никогда не опустеет, так как прирост и убыль скомпенсированы.
    Шаг 2: До тех пор, пока [latex]p_{i}>0[/latex], рассчитывать [latex]p_{i}[/latex] по соотношению (*), где [latex]i[/latex] — количество прошедших лет.

  3. Детали реализации:
    В задаче используются два типа данных: целочисленный и с плавающей точкой двойной точности. Выбор продиктован отсутствием указания на конкретный тип входных данных в условии задачи. Протестировать работу программы можно по ссылке.
    Реализация на Java: http://ideone.com/fyuDTg