Додаток C. Приклади задач та їхніх рішень.
Щоб показати, як будуть формулюватися задачі олімпіади і як повиннібути зроблені рішення, ми розглянемо умови двох дуже простих задач і
їхні рішення. Особливу увагу зверніть на введення і вивід даних, тут не
допускається ні найменших відхилень.
Задача 1: "Максимум".
Код задачі: MaximumУмова:
Багато проповідників, психологи і політики називають стан нашої
економіки періодом накопичення початкового капіталу. У цих умовах
надзвичайно актуальна така задача:
Дана послідовність із N цілих чисел: a1, a2, ... , a. Потрібно знайти
найбільше число, що міститься в цій послідовності.
Введення / вивід:
Перший рядок введення містить число N. В другому рядку міститься N
чисел: a1, a2, ... , a. Вивід повинний складатися з одного числа,
максимального в даній послідовності.
Приклад:
input> 5
input> 12 64 -10 88 13
output< 88
Рядок "input>" відзначає рядок, що подається на стандартне введення, а "output<" відзначає вивід програми. Самі рядки "input>" і "output<" не
повинні вводитися або виводитися.
Кінець задачі 1.
Розв'язок цієї задачі на Pascal:
Program Maximum; Const Max = 999; { Максимальне число елементів. }
Var N: Integer; {Число елементів у послідовності. }
A: array[1..Max] of Integer; { Сама послідовність. }
X: Integer; { Необхідне число. }
K: Integer; BEGIN Введення даних. }
Read(N); for K := 1 to N do Read(A[K]); X := A[1]; for K := 2 to N do if A[K] > X then X := A[K]; { Вивід результату. }
WriteLn(X); END.
Розв'язок цієї задачі на C:
/* Maximum */ <#include #define Max 999 /* Максимальне число елементів. *//
int N; /* Число елементів у послідовності. *//
int A[Max]; /* Сама послідовність. *//
int X; /* Необхідне число. */
int main(void) { int K; /* Введення даних. */
int K; scanf("%d", &N); for (K = 0; K < N; K++) scanf("%d", &A[K]); /* Рішення задачі. */
X = A[0]; for (K = 1; K < N; K++) if (A[K] > X) X = A[K]; /* Вивід результату. */
printf("%d\n", X); return 0; }
Ще одна задача:
Задача 2: "Яблучна гра".
Код задачі: ApplesУмова:
Продовжуючи тему, порушену в попередній задачі, запропонуємо таку
цікаву гру. На великому дубовому столі лежить декілька яблук. Два
гравці по черзі з'їдають по яблуку доти, поки усі яблука не будуть з'їдені.
Гравці прагнуть з'їсти якнайбільше яблучної маси. Складіть програму, що грає в цю гру.
Обмеження: 1 < N < 100, де N -- число яблук на дубовому столі.
0 < b < 1000, K=1,2,..,N, де b -- маса K-го яблука (у грамах). b -- ціле
число.
Введення / вивід:
Спочатку Ваша програма повинна прочитати з першого рядка число N, і
з другого -- N чисел b1, b2, ... , b. Потім вона повинна вивести число 1,
якщо вона хоче починати першою, або 2, якщо хоче бути другим гравцем.
Далі, поки залишаються яблука, програма повинна або вивести номер
яблука, що вона хоче з'їсти, або прочитати номер яблука, що з'їв
суперник. По завершенні гри, програма повинна вивести два числа:
скільки грам яблук з'їла вона і її суперник.
Приклад:
input> 4
input> 120 330 470 70
output< 1
output< 3
input> 2
output< 1
input> 4
output< 590 400
Рядок "input>" відзначає рядок, що подається на стандартне введення, а "output<" відзначає вивід програми. Самі рядки "input>" і "output<"
не повинні вводитися або <виводитися.
Кінець задачі 2.
Розв'язок задачі на Pascal:
Program Apples; Const Max = 999; { Максимальне число яблук. }
Var N : Integer; { Число яблук на дубовому столі. }
B : array[1..Max] of Integer; { Маса кожного яблука. }
Eaten: array[1..Max] of Boolean; { чи З'їдене яблуко. }
Remain: Integer; Скільки залишилося яблук на столі. }
MyMove: Boolean; { Чий хід? }
MyApples, HisApples: Integer; { Скільки хто з'їв. }
X, I, K: Integer; BEGIN {Введення даних про яблука}
Read(N); for K := 1 to N do Read(B[K]); { Ми будемо ходити першими. }
MyMove := true; WriteLn(1); { Сама гра. }
for K := 1 to N do Eaten[K] := false; MyApples := 0; HisApples := 0; for Remain := N downto 1 do if MyMove then begin { Наш хід. }
I := 0; X := 0; for K := 1 to N do if (B[K] > X) and (not Eaten[K]) then begin I := K; X := B[K]; end;
MyApples := MyApples + X; Eaten[I] := true; MyMove := false; Writeln(I); end else begin { Хід суперника. }
Read(I); HisApples := HisApples + B[I]; Eaten[I] := true; MyMove := true; end; { Вивід результатів. } WriteLn(MyApples, ' ', HisApples); END.