Темы --> Информатика --> Язык программирования
    Процедуры и функции(96 задач)
    Массивы(232 задач)
    Типы данных(356 задач)
    Циклы(177 задач)
    Условный оператор (if)(164 задач)
    Python(260 задач)
    Standard Template Library(2 задач)
---> 105 задач <---
Источники --> Командные олимпиады
    Школьная командная олимпиада ФМШ № 2007 г.Москвы(21 задач)
    Турнир Архимеда(52 задач)
    Кировские командные турниры(8 задач)
    Барнаульские командные турниры(10 задач)
    Московская командная олимпиада(246 задач)
    Командные чемпионаты школьников Санкт-Петербурга по программированию(167 задач)
    ВКОШП(180 задач)
Страница: << 14 15 16 17 18 19 20 >> Отображать по:
#1765
Сапер
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes
Задано поле для игры в сапер. Цифрами 0 помечены пустые клетки, а 1 - клетки, в которых находится мина или число. Требуется найти расстановку мин,чтобы получился заданный рисунок.

Мальчику Васе очень нравится известная игра «Сапер». В нее играет один человек. Игра идет на клетчатом поле размером \(m\)×\(n\) (\(m\) строк, \(n\) столбцов). В некоторых клетках поля стоят мины. В каждой из остальных клеток записано либо число от 1 до 8 – количество мин в соседних с ней клетках, либо ничего не написано – это означает, что в соседних клетках мин нет. Клетки являются соседними, если они имеют хотя бы одну общую вершину. В одной клетке не может стоять более одной мины. Будем называть поле с расположенными на нем минами и числами картой.

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

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

У Васи есть рисунки, нарисованные на клетчатой бумаге следующим образом: некоторые клетки закрашены в черный цвет, а некоторые оставлены белыми. Вася хочет по каждому такому рисунку сделать соответствующее ему поле для игры в «Сапера» по следующему правилу: если на рисунке клетка покрашена в черный цвет, то на этом месте должна быть либо мина, либо число от 1 до 8, если же клетка оставлена белой, то на игровом поле она должна быть пустой.

Напишите программу, которая сделает это за Васю.

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

В первой строке входного файла содержатся числа \(m\) и \(n\) (1 ≤ \(m\), \(n\) ≤ 100) – количество строк и столбцов соответственно. Далее идет таблица из \(m\) строк, по \(n\) чисел в каждой строке, задающая Васин рисунок. Каждое число в таблице равно 0 или 1, число 0 означает, что соответствующая клетка на рисунке белая, 1 – черная. Числа в строках разделяются пробелами.

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

Выходной файл должен содержать \(m\) строк по \(n\) символов – карту игрового поля, \(j\)-ый символ \(i\)-ой строки должен содержать символ «*» (звездочка) если в клетке (\(i\),\(j\)) стоит мина, цифру от 1 до 8, если в этой клетке стоит соответствующее число, либо «.» (точка), если клетка (\(i\),\(j\)) пустая. Символы пробелами не разделяйте. Если построить поле, соответствующее рисунку, невозможно, выходной файл должен содержать одну строку с сообщением «No solution».

Примеры
Входные данные
3 5
1 1 1 1 1
1 1 1 1 1
0 0 0 0 0
Выходные данные
*****
23332
.....
Входные данные
3 3
0 1 0
0 0 0
0 0 0
Выходные данные
No solution
#1768
Два прямоугольника
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes
На прямоугольном поле есть закрашенные и незакрашенные клетки. Требуется определить, можно ли разбить закрашенные клетки на два прямоугольника, со сторонами, параллельными осям координат.

Недавно один известный художник-абстракционист произвел на свет новый шедевр – картину «Два черных непересекающихся прямоугольника». Картина представляет собой прямоугольник \(m\)×\(n\), разбитый на квадраты 1×1, некоторые из которых закрашены любимым цветом автора – черным. Федя – не любитель абстрактных картин, однако ему стало интересно, действительно ли на картине изображены два непересекающихся прямоугольника. Помогите ему это узнать. Прямоугольники не пересекаются в том смысле, что они не имеют общих клеток.

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

Первая строка входного файла содержит числа \(m\) и \(n\) (1 ≤ \(m\), \(n\) ≤ 200). Следующие \(m\) строк содержат описание рисунка. Каждая строка содержит ровно \(n\) символов. Символ «.» обозначает пустой квадрат, а символ «#» – закрашенный.

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

Если рисунок можно представить как два непересекающихся прямоугольника, выведите в первой строке «YES», а в следующих m строках выведите рисунок в том же виде, в каком он задан во входном файле, заменив квадраты, соответствующие первому прямоугольнику на символ «a», а второму – на символ «b». Если решений несколько, выведите любое.

Если же этого сделать нельзя, выведите в выходной файл «NO».

Примеры
Входные данные
2 1
#
.
Выходные данные
NO
Входные данные
2 2
..
##
Выходные данные
YES
..
ab
Входные данные
1 3
###
Выходные данные
YES
abb
Входные данные
3 1
.
#
#
Выходные данные
YES
.
a
b
#1781
Монетки
  
Темы: [Цикл for]
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

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

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

В первой строке входного файла содержится натуральное число \(n\) – количество монет (1 ≤ \(n\) ≤ 100).

В каждой из следующих \(n\) строк содержится одно целое число – 1 если монетка лежит вверх решкой или 0 если вверх гербом.

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

В выходной файл выведите минимальное количество монет, которые нужно перевернуть.

Примеры
Входные данные
5
1
0
1
1
0
Выходные данные
2
#1788
Красивые номера
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

Вы, наверное, замечали, что многие компании используют для рекламы «красивые» номера телефонов, которые удобны для запоминания потенциальными клиентами. Но что делать, если номер вашей компании ничем не примечателен? Можно присмотреться к нему повнимательнее, а вдруг, если перегруппировать цифры номера некоторым образом, номер станет намного красивее? Например, если у вашей компании номер 872-73-33, то его можно сделать красивее, если перегруппировать цифры так: 8727-333.

Введем следующую оценку красоты разбиения номера. Будем разбивать номер дефисами на группы размером от 2 до 4 цифр. Теперь красотой разбиения назовем сумму баллов, которые приносит каждая группа. Эти баллы будем считать, пользуясь следующей таблицей. 

	 
Шаблон группы          Баллы	 
aa                     2	 
aba                    2	 
aab, abb               2	 
aaa                    3	 
abac, baca             2	 
abab                   3	 
aabb                   3	 
abba                   4	 
baaa, abaa, aaba, aaab 3	 
aaaa                   5

В этой таблице символами «a», «b», «c» обозначены различные цифры. Например под шаблон «aab» подходят группы «223», «667», но не подходят «123» и «888».

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

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

Входной файл содержит одну строку из 7 цифр – заданный телефонный номер.

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

Выведите в первой строке выходного файла наиболее красивое разбиение номера, а во второй – величину его красоты.

Если разбиений с максимальной величиной красоты несколько, выведите в выходной файл любое из этих разбиений.

Примеры
Входные данные
8727333
Выходные данные
8727-333
5
Входные данные
8827291
Выходные данные
88-272-91
4
#2515
Космические захватчики
  
Темы: [Цикл for]
Источники: [ Командные олимпиады, ВКОШП, 2009, Задача F ]
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
256 megabytes

Петя написал свой вариант известной игры «Космические захватчики». Игра состоит в следующем. На землю нападают корабли космических захватчиков. Они выстроены рядами в верхней части экрана. Игрок управляет лазерной пушкой, которая находится у нижнего края экрана в одном из столбцов. За одно действие игрок может передвинуть пушку влево или вправо, либо произвести выстрел вертикально вверх. Если игрок производит выстрел, то он уничтожает ближайший корабль пришельцев в том столбце, в котором находится пушка.

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

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

Первая строка входного файла содержит числа \(n\) и \(p\) — число столбцов и номер столбца, в котором изначально находится пушка (\(1 \le n \le 100\), \(1 \le p \le n\)). Вторая строка содержит \(n\) чисел \(a_1, a_2, ..., a_n\), где \(a_i\) — число пришельцев в \(i\)-м столбце (\(1 \le a_i \le 100\)).

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

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

Примеры
Входные данные
5 4
5 3 4 1 2
Выходные данные
20
Страница: << 14 15 16 17 18 19 20 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест