Приложение C. Примеры задач и их решений.
Чтобы показать, как будут формулироваться задачи олимпиады и как должны быть сделаны решения, мы рассмотрим условия двух очень простых задач и их решения. Особое внимание обратите на ввод и вывод данных, здесь не допускается ни малейших отклонений.
Задача 1: "Максимум".
Код задачи: MaximumУсловие:
Многие проповедники, психологи и политики называют состояние нашей экономики периодом накопления начального капитала. В этих условиях чрезвычайно актуальна следующая задача:
Дана последовательность из N целых чисел: a1, a2, ..., aN. Требуется найти наибольшее число, содержащееся в этой последовательности.
Ограничения: 1 < N < 1000; -1000 <= aK <= 1000, K=1,2,..,N.Ввод / вывод:
Первая строка ввода содержит число N. Во второй строке содержится N чисел: a1, a2, ..., aN. Вывод должен состоять из одного числа, максимального числа в данной последовательности.
Пример:
input> 5
input> 12 64 -10 88 13
output< 88
Строка "input>" отмечает строку, которая подается на стандартный ввод, а "output<" отмечает вывод программы. Сами строки "input>" и "output<" не должны вводиться или выводиться.
Конец задачи 1.
Решение этой задачи на Pascal-е:
Program Maximum;
Const
MaxN = 999; { Максимальное число элементов.}
Var
N: Integer; {Число элементов в последовательности.}
A: array[1..MaxN] 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 MaxN 999 /* Максимальное число элементов. *// int N; /* Число элементов в последовательности. *// int A[MaxN]; /* Сама последовательность. *// 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 ", X); return 0; }
Еще одна задача:
Задача 2: "Яблочная игра".
Код задачи: ApplesУсловие:
Продолжая тему, затронутую в предыдущей задаче, предложим следующую занимательную игру. На большом дубовом столе лежит несколько яблок. Два игрока по очереди съедают по яблоку до тех пор, пока все яблоки не будут съедены. Игроки стремятся съесть как можно больше яблочной массы. Составьте программу, которая играет в эту игру.
Ограничения: 1 < N < 100, где N -- число яблок на дубовом столе.
0 < bK < 1000, K=1,2,..,N, где bK -- масса K-го яблока (в граммах). bK -- целое число.
Ввод / вывод:
Сперва Ваша программа должна прочитать с первой строки число N, и со второй -- N чисел b1, b2, ..., bN. Затем она должна вывести число 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
MaxN = 999; { Максимальное число яблок. }
Var
N : Integer; { Число яблок на дубовом столе. }
B : array[1..MaxN] of Integer; { Масса каждого яблока. }
Eaten: array[1..MaxN] 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.