Третій тур
Розв’язки задач відправляти з 24.10 по 6.11.2011 р.
Розв’язок задачі розмістити як вкладений текстовий файл з іменем завдання.
скачати файл
1. Паліндроми (20 балів)
Ім’я вхідного файлу: palind.in
Ім’я вихідного файлу: palind.out
Програма: palindr.*
Обмеження часу: 5с
Обмеження пам’яті: 64 мбайт
Паліндром – слово, яке однаково читається в обох напрямках. Підрахуйте, скільки різних паліндромів можна отримати, переставляючи букви в заданому слові. Так як відповідь може бути дуже великим числом – виведіть остачу від його ділення на 1000000000.
Формат вхідного файлу
Один рядок містить слово із рядкових букв латинського алфавіту довжиною від 1 до 100 символів.
Формат вихідного файлу
Вихідний файл повинен містити одне ціле число від 0 до 1000000000-1 – відповідь до задачі.
Приклад
palind.in
|
palind.out
|
ababc
|
2
|
aaa
|
1
|
abc
|
0
|
В першому прикладі можна зробити два паліндроми: abcba, bacab
2. Рядки (100 балів)
Ім’я вхідного файлу: string.in
Ім’я вихідного файлу: string.out
Програма: strings.*
Обмеження часу: 4с
Обмеження пам’яті: 64 мбайт
Маємо два рядка. Із кожного рядка дозволяється видаляти символи, але кількість видалених символів, які йдуть підряд, не повинна перевищувати W. Ваше завдання – видаливши мінімально можливу кількість символів, зробити рядки однаковими (символи різного регістру вважати однаковими).
Формат вхідного файлу
Вхідний файл містить в першому рядку число W (1≤W≤1500), в другому і третьому – два заданих рядка, які складаються із цифр і символів англійського алфавіту від 1 до 1500 символів.
Формат вихідного файлу
Вихідний файл повинен містити один рядок, який можна отримати із обох рядків за правилами задачі. Якщо існує декілька варіантів відповіді, виведіть будь-який. Якщо відповіді не існує виведіть No solution
Приклад
String.in
|
String.out
|
1 xabcd aefdz
|
No solution
|
2 xabcd aefdz
|
ad
|
|