3. Радиолюбитель Ограничение времени 1 секунда
Ограничение памяти 244Mb
Ввод grass.in
Вывод grass.out
Джон решил заняться радиолюбительством, прочитал в сети Интернет о технологии ЛУТ (лазерно-утюжная технология) и решил попробовать. Суть технологии упрощённо состоит в следующем: сначала на лазерном принтере печатают маску (схему проводников), которую накладывают на заготовку платы, покрытую медью, и травят кислотным раствором. В результате, медь растворяется там, где нет маски (т.е. чернил).
Однако, принтер у Джона очень старый, в результате чего некоторые дорожки перетравились и оказались разорванными. Он решил их дорисовать дорогим контактным клеем "Контактол". Естественно, он хочет потратить как можно меньше этого клея.
Джон раньше занимался математикой, поэтому быстро формализовал и упростил задачу. Во-первых, каждый раз достаточно рассматривать только два целых участка повреждённого проводника. Во-вторых, если для соединения каждой пары таких участков потратить минимум клея, то минимум клея уйдёт и на весь проводник.
Осталось дело за малым - научиться оптимально соединять два участка проводника. Участок платы представлен массивом символов N*M, например, так:
Здесь каждый символ 'X' обозначает сохранившийся участок проводника, на котором медь осталась. Два символа 'X' принадлежат одному и тому же участку, если они вертикально или горизонтально соседние (диагонально соседние таковыми не считаются). Гарантируется, что в выбранном участке имеется только два участка проводника.
Джон хочет использовать как можно меньше клея, чтобы объединить два участка проводника в один. В примере выше, он может сделать это, закрасив только три дополнительных клетки (они помечены символами ‘*’ на рисунке ниже).
Джону определить минимальное количество клеток, которые нужно закрасить, чтобы объединить два участка в один.
Формат ввода
Строка 1: Два разделенных пробелом целых числа, N и M (1 ≤ N, M ≤ 50).
Строки 2..1+N: Каждая строка содержит строку из M символов 'X' и '.', указывающих состояние проводника.
Формат вывода
В единственной строке требуется вывести минимальное количество новых символов 'X', которые необходимо добавить.
Пример
Ввод Вывод
6 16
..XXX...
...XX...
.XXX..
...
XXX
3
Примечания
На рис. участки проводника показаны цифрами 1 и 2:
Три дополнительных символа ‘X’ объединяют участки в один.
17. num = 23
# 1 вариант - преобразуем число в строку, разбиваем на цифры
string = str(num)
if int(string[0]) < int(string[1]): # если первая цифра меньше второй
string = string[1] + string[0] #меняем их местами
num = int(string)
# 2 вариант - остатком от деления на степени 10
# остаток от деления на 10 - первая цифра числа, остаток от деления на 100 - вторая и так далее
if num % 10 < num % 100: #если первая цифра меньше второй
num = num % 10 * 10 + num % 100
21.
num = 1234
# 1 вариант - преобразуем число в список и находим сумму цифр
string = str(num)
lst = [int(n) for n in string] # учили списковое включение? если нет, смотри следующий код
lst = []
for n in string:
lst.append(int(n)) # это все если не учили списковое включение
# второй вариант - остатки от деления на 10 суммируем вручную
first = num % 10
sec = num % 100
th = num % 1000
four = num % 10000
result = first + sec + th + four
result = sum(n)
Объяснение:
Функция sum() возвращает сумму элементов списка
Если будут вопросы - пиши
Если пригодилось - оцени ответ ;)
program jumping;
var
i, j, temp: integer;
B: array [1..10] of integer;
begin
for i := 1 to 10 do
read(B[i]);
for i := 1 to 9 do
for j := 1 to 10 - i do
if (B[j] < B[j + 1]) then
begin
temp := B[j];
B[j] := B[j + 1];
B[j + 1] := temp;
end;
writeln('Первое место: ', B[1]);
writeln('Второе место: ', B[2]);
writeln('Третье место: ', B[3]);
end.
Объяснение:
program jumping; // Название программы
var
i, j, temp: integer; // Целочисленные переменные:
i - переменная счетчик для цикла forj - переменная счетчик для цикла fortemp - переменная для временного хранения значений массиваB: array [1..10] of integer; // Целочисленный массив из 10 чисел
begin // Начало программы
for i := 1 to 10 do // Идём с первого по десятый элементы массива
read(B[i]); // Ввод значений массива
// Сортировка массива в порядке убывания
for i := 1 to 9 do // Идём с первого по девятый элементы массива
for j := 1 to 10 - i do // Идём с первого по 10 - i элементы массива
if (B[j] < B[j + 1]) then // Если последующий элемент больше предыдущего
begin // Начало цикла
temp := B[j]; // Временная переменная = значению массива B с индексом j
B[j] := B[j + 1]; // Значение массива B с индексом j = значению массива B с индексом j + 1
B[j + 1] := temp; // Значение массива B с индексом j = значению временной переменной
end; // Конец цикла
writeln('Первое место: ', B[1]); // Вывод ответа
writeln('Второе место: ', B[2]); // Вывод ответа
writeln('Третье место: ', B[3]); // Вывод ответа
end. // Конец программы