Морской бой

На прямоугольном поле для игры в морской бой размером M×N

расположено несколько прямоугольных кораблей. Корабли не соприкасаются друг с другом. Ваша задача — определить всевозможные типы кораблей на поле и число кораблей каждого типа. Два корабля относятся к одному типу, если их размеры совпадают (корабли, которые могут быть получены друг из друга поворотом, также относятся к одному типу).

Входные данные
Первая строка входных данных содержит два положительных числа M и N, не превосходящих 1000, задающие размеры поля. Далее идет M строк, каждая из которых состоит из N символов. Символ `1' означает, что соответствующая клетка поля занята кораблем, символ `0' — что свободна. Пробелов в строке нет.

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

Пример входных данных
6 10
0111000011
0000011011
0100011000
0101011011
0100000000
0001111011
Пример выходных данных
1 1 1
2 1 2
2 2 2
3 1 2
3 2 1
4 1 1

Добавлено: 07 Апреля 2018 21:15:45 Добавил: Андрей Ковальчук

7 Ферзя в угол

В левом нижнем углу доски M×N стоит ферзь. Двое игроков по очереди ходят ферзем, перемещая его на любое число клеток по вертикали вверх, по горизонтали вправо, или по диагонали вправо-вверх. Выигрывает тот, кто поставит ферзя в правый верхний угол доски. Определите, какой из игроков имеет выигрышную стратегию.

Входные данные
На вход программе подается два положительных числа M и N, не превосходящих 1000.

Выходные данные
Программа должна вывести номер игрока (1 или 2), который имеет выигрышную стратегию.

Пример входных данных
3 4
Пример выходных данных
1

Добавлено: 07 Апреля 2018 07:03:49 Добавил: Андрей Ковальчук

Макроэкономика. Задача на определение функции потребления

Задача. Среднестатистическая семья в стране состоит из 3 человек, а среднедушевой доход равен 1600 руб. в месяц. Ежемесячные расходы семьи на покупку товаров и оплату услуг – 3800 руб. Из каждых 100 руб. текущего дохода семья помещает на срочный банковский счет 40 руб. Определите, какой формулой задается функция потребления в национальной экономике.

Запишем условие кратко.

Дано:

n = 3

Yi = 1600 руб.

C = 3800 руб.

MPS = 40/100

Решение.

Функция потребления имеет вид: C = Ca + MPC*Yd, где

Ca – автономное потребление, величина которого не зависит от располагаемого дохода;

MPC – предельная склонность к потреблению;

Yd – располагаемый доход (после уплаты налогов).

В условии дана предельная склонность к сбережению MPS = 40/100 = 0,4

А MPS + MPC = 1 => MPC = 1 – MPS = 1 – 0,4 = 0,6;

Доход семьи: Y = Yi*n = 1600*3 = 4800 руб.

Сбережения семьи: S = 0,4 * Y = 0,4 * 4800 = 1920 руб.

Расходы семьи даны в условии: C = 3800 руб.

Автономное потребление: Ca = (C + S) – Y = (3800 + 1920) – 4800 = 920 руб.

Таким образом, функция потребления имеет вид: C = 920 + 0,6*Yd.

Добавлено: 01 Апреля 2018 20:29:19 Добавил: Андрей Ковальчук

Попытка к бегству

Время на тест - 3 секунды.

Узник пытается бежать из замка, который состоит из MN квадратных комнат, расположенных в виде прямоугольника M×N. Между любыми двумя соседними комнатами есть дверь , однако некоторые комнаты закрыты и попасть в них нельзя. В начале узник находится в угловой комнате и для спасения ему надо попасть в противоположную угловую комнату. Времени у него немного, всего он может побывать не более, чем в M+N-1 комнате, включая начальную и конечную комнату на своем пути, то есть с каждым переходом в соседнюю комнату расстояние до выхода из замка должно уменьшаться. От вас требуется найти количество различных маршрутов, ведущих к спасению.

Формат входных данных

Первая строчка входных данных содержит натуральные числа M и N, не превосходящих 1000. Далее идет план замка в виде M строчек из N символов в каждой. Один символ соответствует одной комнате: если символ равен 1, то в комнату можно попасть, если он равен 0, то комната закрыта. Первоначальное положение узника – левый нижний угол (первый символ последней строки), выход находится в правом верхнем углу (последний символ первой строки, оба этих символа равны 1).

Формат выходных данных

Программа должна напечатать количество маршрутов, ведущих узника к выходу и проходящих через M+N-1 комнату, или слово impossible, если таких маршрутов не существует.

Входные данные подобраны таким образом, что искомое число маршрутов не превосходит 2.000.000.000.

Пример

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

3 5
11111
10101
11111


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

3


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

3 5
11101
10101
10111


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

impossible

Добавлено: 16 Мая 2015 19:26:33 Добавил: Андрей Ковальчук

Рациональные дроби

Время на тест - 1 секунда.

Даны две положительные рациональные дроби: a/b и c/d. Найдите их сумму и запишите ответ в виде несократимой дроби.

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

На вход программа получает числа a, b, c и d. Все числа являются положительными и не превосходят 10000.

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

Программа должна вывести два целых положительных числа x и у таких, что дробь x/y — несократима и x/y=a/b+c/d.

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

1
3
2
12


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

1
2

Добавлено: 01 Марта 2015 08:09:36 Добавил: Андрей Ковальчук

Игра в 8

Время на тест - 1 секунда.

Всем хорошо известна "Игра в 15", представляющая собой 15 квадратных фишек, пронумерованных числами от 1 до 15. Фишки уложены в квадрат со стороной в 4 стороны фишки, одна позиция для фишки свободна. Если обозначить свободную позицию за *, то головоломка состоит в том, чтобы получить из произвольной начальной позиции позицию следующего вида:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 *


Единственной разрешенной операцией является обмен * с одной из соседних по ребру фишек. Операции будем кодировать буквами:

r
поменять * с фишкой, которая стоит справа от *
l
поменять * с фишкой, которая стоит слева от *
u
поменять * с фишкой, которая стоит сверху от *
d
поменять * с фишкой, которая стоит снизу от *

Например, решением головоломки

1 2 3 4 5 6 7 8 9 10 12 * 13 14 11 15


является последовательность ldr.

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

От вас требуется решить более простую головоломку "Игра в 8", в которой требуется расположить 8 фишек в виде:

1 2 3 4 5 6 7 8 *


Формат входных данных

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

Например, позиция

1 2 3 * 4 6 7 5 8


задается строкой

1 2 3 * 4 6 7 5 8


Формат выходных данных

На выход программа должна вывести одну строку, состоящцю из букв l, r, u, d, содержащую последовательность операций, разрешающую данную головоломку, в которой одна буква соответствует перемещению одной фишки (см. выше правило кодирования операций). Если же головоломка неразрешима, то требуется вывести одно слово unsolvable.

Пример

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

2 3 4 1 5 * 7 6 8


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

ullddrurdllurdruldr

Добавлено: 01 Марта 2015 08:08:23 Добавил: Андрей Ковальчук

Расписание

Время на тест - 5 секунд.

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

Формат входных данных

Первая строка входных данных содержит целое число n, 0<n<=10000. Далее идет n строк, каждая из которых содержит два целых числа si и ti, 0<=si<ti<=30000. Каждая строка соответствует одной заявке с номером i (1<=i<=n), si является временем начала заявки, ti – временем ее окончания.

Программа должна найти подмножество множества {1, 2, ..., n}, содержащее наибольшее число элементов, такое, что для любых двух элементов i и j из найденного подмножества верно одно из двух неравенств: ti<=sj

или tj<=si. Указанные неравенства означают, что заявки с номерами i и j не пересекаются, то есть одна из них заканчивается не позднее, чем начинается другая. При этом время окончания одной удовлетворенной заявки может совпадать со временем начала другой заявки (один министр на трибуне меняется на другого министра).

Формат выходных данных

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

Пример

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

3
1 3
2 4
3 5


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

1 3


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

5
2 6
1 3
1 4
4 5
5 6


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

2 4 5

Добавлено: 01 Марта 2015 08:05:58 Добавил: Андрей Ковальчук

Банкомат

Время на тест - 30 секунд.

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

Формат входных данных

Первая строка входных данных содержит натуральное число n, 0<n<=100. Вторая строка входных данных содержит n различных натуральных чисел x1, x2, ..., xn, не превосходящих 1.000.000. Третья строчка содержит натуральное число S, не превосходящее 5.000.000.

Формат выходных данных

Программа должна найти представление числа S в виде суммы слагаемых из множества {xi}, содержащее минимальное число слагаемых и вывести это представление на экран (в виде последовательности чисел, разделенных пробелами). Если таких представлений существует несколько, то программа должна вывести любое (одно) из них. Если такое представление не существует, то программа должна вывести слово impossible.

Пример

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

5 1 3 7 12 32 40


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

1 7 32


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

5 10 50 100 500 1000 99


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

impossible

Добавлено: 01 Марта 2015 08:04:49 Добавил: Андрей Ковальчук

Покер

Время на тест: 1 секунда.

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

Формат входный данных

Программа получает на вход 5 целых положительных чисел x1, x2, x3, x4, x5, не превосходящих 109.

Формат выходных данных

Программа должны вывести на экран одну из следующих строк:

poker
если все 5 чисел равны
four of a kind
если ровно 4 числа равны между собой
full house
если три из пяти чисел равны между собой и два оставшихся числа равны
three of a kind
если ровно три числа равны
two pairs
если есть две пары равных чисел
one pair
если только два числа равны
all different
если все числа различны

БУДЬТЕ ВНИМАТЕЛЬНЫ ПРИ ВЫВОДЕ СТРОК, НЕ ОШИБИТЕСЬ В НАПИСАНИИ!

Пример

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

7 3 7 7 3


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

full house


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

1000 999 998 997 996


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

all different

Добавлено: 01 Марта 2015 08:03:52 Добавил: Андрей Ковальчук

Попытка к бегству

Время на тест - 3 секунды.

Идентификатор для autotest: ol001

Узник пытается бежать из замка, который состоит из MN квадратных комнат, расположенных в виде прямоугольника M×N. Между любыми двумя соседними комнатами есть дверь , однако некоторые комнаты закрыты и попасть в них нельзя. В начале узник находится в угловой комнате и для спасения ему надо попасть в противоположную угловую комнату. Времени у него немного, всего он может побывать не более, чем в M+N-1 комнате, включая начальную и конечную комнату на своем пути, то есть с каждым переходом в соседнюю комнату расстояние до выхода из замка должно уменьшаться. От вас требуется найти количество различных маршрутов, ведущих к спасению.

Формат входных данных

Первая строчка входных данных содержит натуральные числа M и N, не превосходящих 1000. Далее идет план замка в виде M строчек из N символов в каждой. Один символ соответствует одной комнате: если символ равен 1, то в комнату можно попасть, если он равен 0, то комната закрыта. Первоначальное положение узника – левый нижний угол (первый символ последней строки), выход находится в правом верхнем углу (последний символ первой строки, оба этих символа равны 1).

Формат выходных данных

Программа должна напечатать количество маршрутов, ведущих узника к выходу и проходящих через M+N-1 комнату, или слово impossible, если таких маршрутов не существует.

Входные данные подобраны таким образом, что искомое число маршрутов не превосходит 2.000.000.000.

Пример

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

3 5
11111
10101
11111


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

3


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

3 5
11101
10101
10111


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

impossible

Добавлено: 01 Марта 2015 08:02:14 Добавил: Андрей Ковальчук