Задача тижня 13.02.12 – 19.02.12
Казкова країна
Маленький хлопчик потрапив до казкової країни й побачив там дорогу, уздовж якої розкладено мішечки з цукерками. На кожному мішечку написана кількість цукерок. Хлопчик може взяти в кожну руку по два мішечка, що лежать поряд.
1. Створіть програму, що знайде найбільшу кількість цукерок, яку зможе взяти хлопець.
Вхідні дані
Значення N – натуральне число не більше 100 (кількість мішечків з цукерками), вводиться з клавіатури або задається як константа;
значення Ri (i = 1, 2, …, N) – натуральні числа не більше 1000 (кількість цукерок у кожному мішечку), вводяться з клавіатури або з файлу.
Вихідні дані (виводяться на екран)
Значення W– найбільша кількість цукерок, яку зможе узяти хлопець.
2. Заповніть тестову таблицю за результатами роботи програми:
| № | N | Ri (i = 1, 2, …, N) | W |
| 1 | 5 | 5 5 5 5 5 | 20 |
| 2 | 20 | 4 5 6 8 9 7 2 3 5 8 9 4 1 5 2 8 2 9 7 6 | 34 |
| 3 | 16 | 21 2 13 5 8 9 5 13 1 15 12 8 9 10 6 19 | |
| 4 | 20 | 5 8 9 12 13 15 1 5 9 11 2 15 1 12 1 9 5 8 19 21 | |
| 5 | 20 | 23 45 12 18 2 5 13 1 15 1 18 3 23 2 25 1 15 9 5 4 | |
| 6 | 15 | 5 2 21 4 9 8 6 12 16 9 15 15 1 6 3 | |
| 7 | 8 | 10 35 30 4 1 4 1 2 | |
| 8 | 10 | 5 2 10 7 20 27 12 1 4 11 |
Аналіз розв’язку задачі «Казкова країна»
Для зберігання кількості цукерок у N мішечках створюємо масив R з N елементів.
Спочатку треба розглянути варіант, коли 4-и елементи, що дають максимальну суму розташовані поряд. Та знайти шукану максимальну суму 4-х елементів, що попарно розташовані в масиві.
кінець циклу
Після чого, треба розглянути варіант, коли попарно розташовані елементи в масиві, що дають шукану максимальну суму, не розташовані поряд. Для цього масив необхідно переглянути двічі. У результаті першого перегляду знайдемо максимальну суму двох поряд розташованих елементів і «візьмемо» їх, тобто додамо цю суму до шуканої суми, а в масиві відповідним елементам присвоїмо нульові значення. У результаті другого перегляду знайдемо другу пару елементів з найбільшим значенням суми і повторимо з ними ті самі дії.
Нам знадобляться допоміжні змінні: S – для зберігання поточного (потім найбільшого) значення суми пари елементів, Pos – для зберігання індексу першого елемента відповідної пари.
кінець циклу
А тепер треба порівняти результати першого та другого варіанту, та вибрати максимальний.
Таблиця за результатами роботи програми:
| № | N | Ri (i = 1, 2, …, N) | W |
| 1 | 5 | 5 5 5 5 5 | 20 |
| 2 | 20 | 4 5 6 8 9 7 2 3 5 8 9 4 1 5 2 8 2 9 7 6 | 34 |
| 3 | 16 | 21 2 13 5 8 9 5 13 1 15 12 8 9 10 6 19 | 52 |
| 4 | 20 | 5 8 9 12 13 15 1 5 9 11 2 15 1 12 1 9 5 8 19 21 | 68 |
| 5 | 20 | 23 45 12 18 2 5 13 1 15 1 18 3 23 2 25 1 15 9 5 4 | 98 |
| 6 | 15 | 5 2 21 4 9 8 6 12 16 9 15 15 1 6 3 | 58 |
| 7 | 8 | 10 35 30 4 1 4 1 2 | 79 |
| 8 | 10 | 5 2 10 7 20 27 12 1 4 11 | 66 |
Журі оцінило надіслані розв’язки наступним чином:
| № | Учасник | Кількість балів |
| 1 | forsh3 | 2 |
| 2 | Юрий Дончик | 4 |
| 3 | SERGEY | 2 |
| 4 | Макс Синкевич | 1 |
| 5 | ALEX Z | 1 |
| 6 | RomaN | 4 |
