Вхідні та вихідні тести

Вхідний файл на першому рядку містить ціле число - кількість людей, що живуть на острові, на наступних рядках файлу знаходиться матриця, така що номер рядку - це житель острова, а номер стовпчика партія. Якщо на перетині -того рядка та -того стовпчика знаходиться цифра , то це значить, що -тий житель є членом -тої партії, в іншому випадку ставиться цифра . Цифри та записуються буз пробілів і роздільників. Програма виводить довжину мінімального шляху комівояжера та сам шлях на екран.

Приклад 1:

Кількість жителів:

Матриця приналежності жителів до партій:

1 1 1 1

0 1 1 0

1 1 1 1

0 1 0 1

Мінімальна кількість людей в парламенті:

Номера представників парламенту:

Представники партій в парламенті

Партія № 0:

Партія № 1:

Партія № 2:

Партія № 3:

Приклад 2:

Кількість жителів:

Матриця приналежності жителів до партій:

1 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0

0 1 0 0 0 0 0 0 0 1 1 0 0 0 0 0

0 0 1 0 0 0 0 0 0 0 0 1 1 0 0 0

0 0 0 1 0 0 0 1 1 1 0 0 0 0 0 0

0 0 0 0 1 0 0 0 0 0 1 1 1 0 0 0

0 0 0 0 0 1 0 1 1 1 1 0 0 0 0 0

0 0 0 0 0 0 1 0 1 1 1 1 1 0 0 0

1 0 0 1 0 1 0 1 0 0 0 0 0 1 0 0

1 0 0 1 0 1 1 0 1 0 0 0 0 0 1 1

0 1 0 1 0 1 1 0 0 1 0 0 0 0 0 0

0 1 0 0 1 1 1 0 0 0 1 0 0 0 0 0

0 0 1 0 1 0 1 0 0 0 0 1 0 0 0 0

0 0 1 0 1 0 1 0 0 0 0 0 1 0 0 0

0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0

0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 1

0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 1

Мінімальна кількість людей в парламенті:

Номера представників парламенту:

Представники партій в парламенті

Партія № 0:

Партія № 1:

Партія № 2:

Партія № 3:

Партія № 4:

Партія № 5:

Партія № 6:

Партія № 7:

Партія № 8:

Партія № 9:

Партія № 10:

Партія № 11:

Партія № 12:

Партія № 13:

Партія № 14:

Партія № 15:

Опис алгоритму методу

Задачу комівояжера можна розв’язати алгоритмом перебору з поверненням. Для цього треба додавати до парламенту нового жителя і дивитися, чи стане парламент повним? Якщо утворений повний парламент менший за запам`ятований, то запам`ятовуємо його склад, та кількість жителів . Якщо на деякому кроці в неповному парламенті вже знаходиться людей, то це значить, що немає можливості знайти менший за запам`ятований повний парламент для цієї комбінації жителів, отже переходимо на крок назад і намагаємося додати іншого жителя. Дана схема є схемою роботи алгоритму перебору з поверненням.

Алгоритм програми

1. Зчитати кількість жителів та таблицю членів партій

2. Кількість людей в найменшому парламенті дорівнює нескінченності

3. Виконати пункт 4 враховуючи що на даний момент в парламенті людей

4. Спробувати утворити парламент, додавши до нього нового члена:

   1. Якщо в парламенті містяться представники всіх партій та кількість людей в цьому парламенті менша за кількість людей в найменшому парламенті, то:

      1. Кількість людей в найменшому парламенті дорівнює поточній кількості людей в даному парламенті

      2. Запам’ятати склад даного парламенту

   2. Якщо поточна кількість членів в парламенті менша кількості членів в мінімальному парламенті , то:

      1. Для всіх жителів, що не були додані на даному кроці:

         1. Якщо -того жителя ще немає в парламенті, то:

            1. Додати -того жителя до парламенту

               1. Для всіх партій які представляє даний житель

                  1. Збільшити кількість жителів які представляють дану партію в парламенті на одиницю

            2. Запам’ятати, що на цьому кроці вже намагалися додати даного жителя до парламенту

            3. Виконати пункт 4 для наступного члена парламенту

            4. Перейти до пункту 4.3.

   3. Якщо жодного жителя на даному кроці додати неможна та в парламенті є представники, то:

      1. Видалити останнього доданого жителя з парламенту

         1. Для всіх партій які представляє даний житель:

            1. Зменшити кількість жителів які представляють дану партію в парламенті на одиницю

      2. Позначити що на даному кроці не було спроби додати ні одного жителя до парламенту

      3. Виконати пункт 4 для попереднього кроку

5. Вивести результат на екран

   1. Вивести кількість жителів в парламенті на екран

   2. Вивести номера жителів, що входять до парламенту

   3. Для всіх партій:

      1. Вивести жителів які представляють дану партію

Відеокопії екрана

Аналіз достовірності результатів

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

Задача про автозаправку

Умова задачі [2]

Вздовж кільцевої дороги розташовано міст, в кожному з яких розташована автозаправка. Відома вартість заправки в місті з номером i та , вартість проїзду між першим і -м містами. Для жителів кожного міста знайти місто, в яке їм необхідно з`їздити, щоби заправитись найдешевшим способом, і напрям - "за годинниковою стрілкою" або "проти годинникової стрілки", міста пронумеровані за годинниковою стрілкою.