|
Розв'язки слід надіслати не пізніше 0 годин 28 грудня 2009 року.
Чат-консультації //www.vinnica.ua/netoi
9.12.09 з 18-00 до 18-30
16.12.09 з 18-00 до 18-30
Увага !!!! з 26 грудня доступ до сайту ускладнений через проблеми з каналами зв'язку. З 15-00 28 грудня ціною надзусиль відновлено за тимчасовою схемою.
термін прийняття рішень подовжено до 0 годин 4 січня 2010 року.
Задача Queen
На узагальненій шахівниці (розмірами не обов’язково 8×8) стоїть ферзь. Відомо, на якій клітинці він перебуває зараз, та в яку клітинку йому потрібно дістатись. Задача ускладнюється тим, що деякі клітинки зайняті ворожими фігурами, але спрощується тим, що зараз вони міцно сплять, так що ферзь може тихенько зробити скільки завгодно ходів підряд. Ні перестрибувати через ворожі фігури, ні бити їх не можна (бо тоді вони попросинаються). Напишіть програму, яка знаходитиме мінімальну кількість ходів, необхідних ферзеві для такого переміщення.
Технічні умови. Програма читає з клавіатури розміри шахівниці — спочатку кількість вертикалей w (2 ≤ w ≤ 26), потім кількість горизонталей h (2 ≤ h ≤ 99), потім координати стартової та фінішної клітинок, потім кількість ворожих фігур К (0 ≤ K ≤ w×h–2), далі K пар чисел – координати чергової ворожої фігури. Всі числа розділено пропуском. Координати всіх клітинок – натуральні числа, що не перевищують відповідно w та h. Спочатку вводиться вертикаль, потім горизонталь. Клітинки, вказані як початкова та кінцева, не містять ворожих фігур; різні ворожі фігури не можуть перебувати в одній і тій самій клітинці. Програма має вивести на екран єдине ціле число — або мінімальну кількість ходів, необхідних, щоб дійти від вказаної початкової клітинки до вказаної кінцевої, або -1 на позначення того, що дійти неможливо.
Приклади
Введення
8 8 5 2 5 4 1 5 3
Виведення 2
Введення 20 20 1 20 3 3 3 1 19 2 19 2 20
Виведення-1
Задача Beads
Намисто складається з намистин 4-х кольорів. Власниця вирішила залишити лише 3 кольори. Яку мінімальну кількість намистин треба для цього зняти з нитки, якщо розріз на ній можна зробити лише один, а намистини знімати лише підряд, повертати намистини назад не можна, а після розрізу нитку зв’язують.
Технічні умови. Програма Beads читає з клавіатури число намистин N (4≤N≤5000), а далі в тій же стрічці N чисел через пропуск, що визначають колір бусинок (1 – жовтий, 2-синій, 3- червоний, 4-зелений). Програма виводить на екран єдине число – мінімальну кількість знятих намистин.
| Приклад |
Введення 10 1 2 4 2 3 1 3 4 3 4
Виведення 3 |
| |
Задача Smarand
Значенням S(k) функції Смарандаша є таке найменше число m, що m! ділиться на k націло. Наприклад, S(9) = 6 тому, що число 6! = 720 ділиться на 9, а ніякий менший факторіал на 9 не ділиться. Напишіть програму, яка обчислюватиме функцію Смарандаша.
Технічні умови. Програма Smarand читає з клавіатури натуральне число k (1≤ k ≤109). Програма виводить на екран значення функції Смарандаша для цього числа.
Приклад
Введення9
Виведення6
Задача Palindrom2
Дано натуральне число n. Знайдіть мінімальне число-паліндром, більший за n. Паліндром – це число, яке читається зліва направо так само, як справа наліво.
Технічні умови. Програма читає з клавіатури натуральне число n (1<=n<1018). Програма виводить на екран шуканий паліндром.
Приклад
Введення131
Виведення141
Задача Word2
Під час уроку інформатики два учні, не слухаючи пояснень вчителя, грають в таку гру. Кожен з них в своєму зошиті записує два обраних ними разом слова і намагається за певну кількість ходів з першого слова отримати друге. Виграє той, хто зробить мінімальну кількість ходів. Хід – це одна з таких операцій:1.замінити якийсь символ з першого слова якимось символом другого слова;2. викреслити якийсь символ з першого слова;3. ставити якийсь символ з другого слова після або перед якимось символом першого слова. Наприклад, для перетворення слова “limuzin” в слово “buzina” необхідно виконати такі дії:
| Перетворення |
Номер операції |
limuzin
imuzin
ibuzin
ibuzina |
=>
=>
=>
=> |
imuzin
ibuzin
ibuzina
buzina |
2
1
3
2 |
| |
|
|
|
Спробуйте написати програму, яка знаходить мінімальну кількість ходів для перетворення одного заданного слова в інше.
Технічні умови Програма читає з клавіатури дві стрічки довжиною не більше 104 символів кожна і виводить на екран єдине число – мінімальну кількість ходів.
| Приклад |
Введення |
Виведення |
| |
limuzin buzina
|
4
|
Звдання підготували А.Коротков, Г.Непомнящий, І.Порубльов, Ю.Пасіхов
|
