Добро пожаловать, гость
:: алгоритмы  и методы :: :: олимпиадные задачи :: :: связь :: :: о сайте :: :: форум ::

Форум работает в режиме архива, только для чтения и поиска.
Архив 2004 Архив 2007 Архив 2013

 
 
Опции темы Поиск в этой теме Опции просмотра
  #1  
Старый 14.03.2009, 11:03
гость

 
Сообщений: n/a

Задачка на дп
Помогоите, плиз, не проходит 10 тест.....
На доске написана последовательность n целых чисел. Играют двое. На очередном ходе игрок выбирает число с правого или с левого края последовательности, затем это число стирается и последовательность становится на одно число меньше, а ход переходит к противнику. Выигрывает тот, кто наберет в сумме больше. Написать программу, определяющую победителя в конкретной игре, при условии, что игроки будут играть оптимально.
Входные данные
В первой строке входного файла INPUT.TXT записано целое число n (0 < n < 100). Во второй строке через пробел заданы n натуральных чисел, не превосходящих 1000.
Выходные данные
В единственную строку выходного файла OUTPUT.TXT нужно вывести 1, если победит первый игрок, 2 – если победит второй игрок и 0 – в случае ничьей.

type mas=array [1..100] of integer;
var n1,i,k,n,s,d,l,s1,s2,d1,d2,q1,q2,kk:integer;
a,b:mas;
f,tf:text;
procedure sm(a:mas;n:integer;var s,d:integer);
var i:integer;
begin
s:=0;d:=0;
for i:=1 to n do
if i mod 2 = 1 then s:=s+a[i] else d:=d+a[i];
end;


begin
assign(f,'input.txt');
assign(tf,'output.txt');
reset(f);rewrite(tf);
readln(f,n);
for i:=1 to n do
read(f,a[i]);
close(f);
s:=0;d:=0;
if n mod 2 = 0 then begin
for i:=1 to n do
if i mod 2 = 0 then s:=s+a[i] else
d:=d+a[i];
if s=d then write(tf,0) else write(tf,1);
close(tf);end else


begin
kk:=0;i:=1;
n1:=n;
b:=a;l:=0;
if a[1]>a[n] then begin l:=1;for i:=1 to n-1 do b[i]:=b[i+1];end else l:=n;
n1:=n1-1;
sm(b,n1,s1,d1);
q1:=0;
if s1<d1 then begin q1:=1;s1:=s1+a[l] end else begin q1:=2 ;d1:=d1+a[l];end;

i:=1;
while (i<=n-1) and (kk=0) do begin
if a[i]=a[i+1] then kk:=i; i:=i+1;end;
if kk=1 then begin
s:=a[2]; a[2]:=a[3];a[3]:=s;s:=0;end else
if kk=n then begin
s:=a[n-1]; a[n-1]:=a[n-2];a[n-2]:=s;s:=0;end else if kk<>0 then begin
s:=a[kk];
a[kk]:=a[kk-1];
a[kk-1]:=s;
s:=0;
end;

n1:=n;b:=a;l:=0;
if a[1]>a[n] then begin l:=1;for i:=1 to n-1 do b[i]:=b[i+1];end else l:=n;
n1:=n1-1;
sm(b,n1,s2,d2);
q2:=0;
if s2<d2 then begin q2:=1;s2:=s2+a[l] end else begin q2:=2 ;d2:=d2+a[l];end;

if (q1=1)and(q2=1)then if d1>=d2 then begin d:=d1;s:=s1 end else
begin d:=d2;s:=s2 end else
if (q1=2)and(q2=1)then if s1>=d2 then begin d:=s1;s:=d1 end else
begin d:=d2;s:=s2 end else
if (q1=2)and(q2=2)then if s1>=s2 then begin d:=s1;s:=d1 end else begin
d:=s2;s:=d2 end else
if (q1=1)and(q2=2)then if d1>=s2 then begin d:=d1;s:=s1 end else begin d:=s2;
s:=d2 end;
if s<d then write(tf,2) else if s>d then write(tf,1) else write(tf,0);
close(tf);
end;end.
 


Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск
Опции просмотра


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
задачка коммивояжера il33 Реализация, исходники, языки 9 04.10.2010 14:31
Задачка на строки NeiroN Задачи 2 31.05.2007 04:38
задачка незарегистрированный Задачи 4 04.03.2007 19:12
задачка про переключатели @Alex@ Задачи 12 27.12.2006 22:31