Третій тур

Розв’язки задач відправляти з 24.10 по 6.11.2011 р.

Розв’язок задачі розмістити як вкладений текстовий файл з іменем завдання.

скачати файл

1. Паліндроми (20 балів)

Ім’я вхідного файлу: palind.in

Ім’я вихідного файлу: palind.out

Програма: palindr.*

Обмеження часу: 5с

Обмеження пам’яті: 64 мбайт

Паліндром – слово, яке однаково читається в обох напрямках. Підрахуйте, скільки різних паліндромів можна отримати, переставляючи букви в заданому слові. Так як відповідь може бути дуже великим числом – виведіть остачу від його ділення на 1000000000.

Формат вхідного файлу

Один рядок містить слово із рядкових букв латинського алфавіту довжиною від 1 до 100 символів.

Формат вихідного файлу

Вихідний файл повинен містити одне ціле число від 0 до 1000000000-1 – відповідь до задачі.

Приклад

В першому прикладі можна зробити два паліндроми: abcba, bacab

2. Рядки (100 балів)

Ім’я вхідного файлу: string.in

Ім’я вихідного файлу: string.out

Програма: strings.*

Обмеження часу: 4с

Обмеження пам’яті: 64 мбайт

Маємо два рядка. Із кожного рядка дозволяється видаляти символи, але кількість видалених символів, які йдуть підряд, не повинна перевищувати W. Ваше завдання – видаливши мінімально можливу кількість символів, зробити рядки однаковими (символи різного регістру вважати однаковими).

Формат вхідного файлу

Вхідний файл містить в першому рядку число W (1≤W≤1500), в другому і третьому – два заданих рядка, які складаються із цифр і символів англійського алфавіту від 1 до 1500 символів.

Формат вихідного файлу

Вихідний файл повинен містити один рядок, який можна отримати із обох рядків за правилами задачі. Якщо існує декілька варіантів відповіді, виведіть будь-який. Якщо відповіді не існує виведіть No solution

Приклад