Задача 1. Шаблон и слово

Задача 1. Шаблон и слово

Имя входного файла:	input.txt
Имя выходного файла:	output. txt
Максимальная оценка:	10 баллов

Требуется определить подходит ли заданное слово под заданный шаблон. Шаблон задается большими латинскими буквами, знаками «?» - любой символ, «*»- любая последовательность символов (даже пустая)

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

В первых двух строках записаны шаблон и слово. В первой строке записан шаблон - последовательность больших латинских букв, «?», «*».Во второй строке – слово, состоящее только из больших латинских букв.

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

Вывести YES, если слово подходит или NO, если нет.

Пример

input. txt	output. txt
A*CDA ABBCDA	YES
A*DA*AA* AADA*VA	NO

Задача 2. Резервное копирование

Имя входного файла:	input.txt
Имя выходного файла:	output. txt
Максимальная оценка:	25 баллов

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

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

Во входном файле задаются число N (1≤ N ≤ 500000) — количество чисел в последова­тель­ности. На следующей строке, через пробел, расположены N чисел, составляющих последовательность резервной копии, каждое из которых не превосходит N и не меньше 0.

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

В выходной файл должна быть выведена через пробел последовательность из N чисел, с которой была сделана копия, либо слово «IMPOSSIBLE», если восстановить ее невозможно.

Примеры

input. txt	output. txt
5
1 1	IMPOSSIBLE
5

Задача 3 . SMS счастья

Имя входного файла:	input.txt
Имя выходного файла:	output.txt
Максимальная оценка:	35 баллов

Студенты факультета информационных технологий Урюпинского государственного университета разрабатывают систему оповещения о различных событиях, таких, например, как назначение даты экзамена. В качестве транспортной среды для этой системы оповещения были выбраны SMS.  Все студенты курса имеют сотовые телефоны, которые постоянно включены. Каждый студент в своей адресной книге помимо других записей имеет номера, по крайней мере, половины своих однокурсников. А те однокурсники, которые записаны в его адресной книге, имеют его номер тоже.

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

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

1.  Маршрут должен быть замкнутым

2.  Маршрут должен проходить через телефон каждого из студентов ровно один раз.

3.  Следующим звеном в маршруте всегда должен быть телефон, записанный в адресной книге текущего телефона.

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

В первой строке входного файла задано количество студентов на курсе N (2<N≤300).

В следующих N блоках задается информация о содержимом адресной книги каждого из студентов курса. В первой строке i-го блока записаны фамилия i-го студента и через пробел целое число — количество записей в адресной книге его телефона ((N+1)/2≤ Ki ≤ 100, 1 ≤ i ≤ N).  В следующих Ki строках перечислены записи его адресной книги.  Заданы только фамилии, по одной в строке. Все фамилии имеют длину не более 16 символов латиницы, большие и маленькие буквы не различаются.

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

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

В выходной файл необходимо вывести один из возможных маршрутов рассылки, удовлетворяющий указанным в условии задачи требованиям.  Маршрут выводится в виде списка N фамилий, по одной фамилии в строке.

Пример

input. txt	output. txt
4 Ivanov 3 Petrov Sidorov Pentyushkin Petrov 2 Sidorov Ivanov Sidorov 3 Pentyushkin Ivanov Petrov Pentyushkin 3 Ivanov Kuznetsov Sidorov	Ivanov Petrov Sidorov Pentyushkin

Задача 4. Жадные дарители подарков

Имя входного файла:	input.txt
Имя выходного файла:	output.txt
Максимальная оценка:	50 баллов

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

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

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

В первой строке входного файла записано целое число N — количество членов в группе (1 £ N £ 10).

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

Все имена записаны маленькими латинскими буквами, их длина не превышает 12. У каждого человека сумма денег — это неотрицательное целое число, не превышающее 2000.

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

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

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

Примеры

input. txt	output. txt
5 dave laura owen vick amr dave 200 3 laura owen vick owen 500 1 dave amr 150 2 vick owen laura 0 2 amr vick vick 0 0	dave 302 laura 66 owen -359 vick 141 amr -150
3 liz steve dave liz 30 1 steve steve 55 2 liz dave dave 0 2 steve liz	liz -3 steve -24 dave 27