Сайт Льва Волкова
  
Если девушка плохо танцует, она ругает оркестр. Пословица
 
      На главную  
 Личное
  Статьи
  Задачи 
 Ссылки
 АТ-531
www.levvol.ru    
 

Муниципальный этап Всероссийской олимпиады по информатике. Московская область. 29 ноября 2009 г.

Задача № 4. Карточки

Оценка 25 баллов.

Один популярный развлекательный телевизионный канал запускает новую игру.

Цель игры — набрать максимально возможное количество очков. Изначально игрок имеет 0 очков, а на столе перед ним лежат две стопки карточек, на каждой карточке написано целое число (не обязательно положительное). Каждым ходом он выбирает одну из двух стопок (если она не пустая), берёт сверху одну карточку и прибавляет число на карточке к количеству набранных очков. Затем карточка откладывается в сторону и больше не используется. Во время любого хода, вместо того чтобы взять карточку, игрок может сказать «достаточно» и игра закончится. Если в какой-то момент текущее количество очков у игрока становится отрицательным, то он проигрывает и игра заканчивается.

Во время шоу с игроком общается известный телеведущий, который сеет в душе игрока сомнения: к акую стопку выбрать на этот раз, или, быть может, уйти с текущим выигрышем. Перед началом игры ведущему необходимо знать, какую максимальную сумму может выиграть игрок.

Требуется написать программу, которая по известным значениям карточек в двух стопках определит максимальную сумму очков, которую можно выиграть в данной игре.

Формат входных данных

Во входном файле input.txt содержится 4 строки. В первой — число карточек в первой стопке N (1 ≤ N ≤ 100), во второй строке через пробел записано N целых чисел в диапазоне от -1000 до 1000 — числа, записанные на карточках первой стопки, в порядке с верхней по нижнюю.

В третьей строке записано число карточек во второй стопке К(1 ≤К≤ 100), в четвертой через пробел указаны числа, записанные на карточках второй стопки, в порядке с верхней по нижнюю — К целых чисел в диапазоне от -1000 до 1000.

Формат выходных данных

На экран вывести одно число — максимальную сумму очков, которую может выиграть игрок.

Примеры входных и выходных данных

Ввод Вывод
3
1 -3 4
3
1 1 -4
4
4
1 2 3 4
5
-10 20 -5 2 2
20

Ршение

Случайным образом перебираются карточки в двух кучках. Разыгрывается 10000 переборов. Фиксируется максимальная положительная сумма.


Program Olimp4(input);
Uses CRT;
Var x,y:array [1..100] of integer;
a,n,m,i,j,k,max,sum,msum:integer;
Begin
ClrScr;
Assign(input,'input.txt');Reset(input);
randomize;
{Вввод данных из файла}
readln(n);
for i:=1 to n do read(x[i]);
readln;
readln(m);
for j:=1 to m do read(y[j]);
for k:=1 to 10000 do begin
sum:=0; i:=1; j:=1;
{Пока сумма не отрицательна и кучки не закончились}
while (sum>=0) and (i<=n) and (j<=m) do
begin
{Случайное число 0,1}
a:=random(2);
{Если 0, то выбор из первой кучки, если 1, - то из второй}
if (a=0) then begin
{Подсчет суммы}
sum:=sum+x[i];
i:=i+1;
end
else begin
{Подсчет суммы}
sum:=sum+y[j];
j:=j+1;
end;
{Максимальная сумма}

if sum>msum then msum:=sum;
end;
{Закончилась вторая кучка, продолжаем брать из первой}

if i<=n then begin
while i<=n do begin
{Подсчет суммы}
sum:=sum+x[i];

{Если сумма отрицательна, то выход из цикла}
if sum<0 then i:=n+2;

{Максимальная сумма}

if sum>msum then msum:=sum;
inc(i);
end;
end

{Закончилась первая кучка, продолжаем брать из второй}

else begin
while j<=m do begin

{Подсчет суммы}

sum:=sum+y[j];

{Если сумма отрицательна, то выход из цикла}

if sum<0 then j:=m+2;
j:=j+1;

{Максимальная сумма}

if sum>msum then msum:=sum
end;
end;

{Максимальная сумма по всем 10000 испытаний}

if msum>max then max:=msum;
end;
writeln(max);
Close(input);
End.


Скачать эту программу

<<<Задача 3 | Назад |