Комментарии (11) свернуть  |  развернуть

  • avatar
  • belan
  • 25 мая 2013, 19:56
+1
— спасибо Вадиму, Насте, Володе ( порядок случайный — мой метод решения задач комбинаторных :) — кто знает, то поймет :) ) — команде по программированию от нашего вуза!!!
— выступили успешно, обошли ряд команд из ведущих вузов (и из политеха и из классического универа и из вышки) — список участников и результаты прилагаю:
— за три часа подготовили шесть задач и четыре из них смогли провести через контестер — очень хороший результат, учитывая, что практически не готовились
— в голове списка команда, которая выступает на международных соревнованиях и другие команды, которые имеют совсем иной уровень подготовки — так что результат очень хороший — я рад!!! :)
0
Задача A
{$APPTYPE CONSOLE}

uses
  SysUtils;

var
  n,k,i,j: Integer;
  s: string;

begin
  AssignFile(input, 'input.txt');
  Reset(input);
  readln(n,k);
  i := 0;
  while not(Eof(input)) do
    begin
      readln(s);
      inc(i);
      if pos('rainy',s)=0 then
        writeln(i);
    end;
  close(input);
end.

Задача E
{$APPTYPE CONSOLE}

uses
  SysUtils;

var
  a:array [1..1000,1..1000] of integer;
  n,k,l,i,j,m,ch: Integer;
  p:boolean;

begin
  AssignFile(input, 'input.txt');
  Reset(input);
  readln(n,k);
  for i:= 1 to n do begin
    for j := 1 to n do
      read(a[i,j]);
      readln;
  end;
  ch:=0;
  for i:= 1 to n-k+1 do
    for j := 1 to n-k+1 do begin
    ch:=a[i,j];
    for m:= i to i+k-1 do
      for l := j to j+k-1 do
      if (a[m,l]<>ch) then p:=false;
    if (p=true) then begin write('Yes');exit;end;
    p:=true;
  end;
  write('No');
  close(input);
end.

Задача F
{$APPTYPE CONSOLE}

uses
  SysUtils;

var
  i,n,S,x,y: integer;

begin
  AssignFile(input, 'input.txt');
  Reset(input);
  ReadLn(n);
  S:=0;
  for i:=1 to n do
  begin
    read(x);
    read(y);
    S:=S+x*y;
  end;
  writeln(S);
  close(input);
end.

Задача G - Time Limit
{$APPTYPE CONSOLE}

uses
  SysUtils, Math;

var
  n,k,i,j,maxi,s,a,Sum: Integer;
  max,ch10:extended;
  str: string;

begin
  AssignFile(input, 'input.txt');
  Reset(input);
  read(n);
  max := 0;
  maxi := 0;
  str := '';
  for i := 1 to n do
  begin
    j := i;
    while (j>=2) do
    begin
      str := str + IntToStr(j mod 2);
      j := j div 2;
    end;
    str := str + intToStr(j);
    ch10 := 0;
    s := 0;
    Sum:=0;
    for k := 1 to length(str) do
      begin
         Sum:=Sum*2+strToInt(str[k])
      //  if (strToInt(str[k])=1) then ch10 := ch10 + power(2,s);
        //inc(s);
      end;
      Sum:=Sum*2;ch10:=Sum;
    str := '';
    if ch10 >= max then
      begin
        max := ch10;
        maxi := i;
      end;
  end;
  write(maxi);
  close(input);
end.

Задача I
{$APPTYPE CONSOLE}

uses
  SysUtils;

var
  n,temp,i,j,maxi,max: integer;
  a: array of integer;

begin
  AssignFile(input, 'input.txt');
  Reset(input);
  read(n);
  setLength(a,n);
  for i := 0 to n-1 do
    read(a[i]);
  max:=1001;
  maxi:=0;
  for i := 0 to n-1 do
  begin
    if max>a[i] then begin maxi:=i; max:=a[i]; end;
  end;
  write(max,' ');
  max:=1001;
  a[maxi]:=1001;
  for i := 0 to n-1 do
  begin
    if max>a[i] then begin maxi:=i; max:=a[i]; end;
  end;
  write(max);
  close(input);
end.

Задача J - Time Limit
{$APPTYPE CONSOLE}

uses
  SysUtils;

var
  a,b: array [1..100000] of integer;
  f,l,k,i,j,n: Integer;
begin
  AssignFile(input, 'input.txt');
  Reset(input);
  readln(n);
  for i := 0 to n - 1 do
  read(a[i]);
  readln;
  for i := 0 to n - 1 do
  read(b[i]);
  readln;
  readln(k);
  for i := 1 to k do
  begin
    read(f);
    read(l);
    readln;
    for j := f to l do
      b[j]:=a[j];
  end;
  for i:= 0 to n - 1 do
  write(b[i],' ');
  close(input);
end.
+2
— мои решения, без проверки в контестере, с лишним оформлением выходного файла (это оставил для проверки самому или вами :) ) и без приукрас, то есть как сделал сразу так и оставил пока:

Задача A
program P_A;
{$APPTYPE CONSOLE}
uses SysUtils;
var n, k , i: Integer;
  s: string;
begin
  AssignFile(input, 'input.txt'); Reset(input);
  AssignFile(output, 'output.txt'); Rewrite(output);
  ReadLn(n, k);
  for i:=1 to n do
  begin
    readln(s);
    if pos('r',s)=0 then writeln(i);
  end;
  close(input); close(output);
end.

Задача E
program P_E;
{$APPTYPE CONSOLE}
uses SysUtils;
var n,k,x,y,d,j,i: Word;               // j,i
    m: array[1..1000,1..1000] of byte; // y,x
    bd,bn: boolean;
begin
  AssignFile(input, 'input.txt'); Reset(input); close(input);
  AssignFile(output, 'output.txt'); Rewrite(output);
  ReadLn(n,k);
  for y:=1 to n do
  begin
    for x:=1 to n-1 do read(m[y,x]);
    readln(m[y,n]);
  end;

  for d:=0 to 9 do
  begin

    for y:=1 to n-k+1 do
      for x:=1 to n-k+1 do
      begin
        bn:=true;
        for j:=y to y+k-1 do
          for i:=x to x+k-1 do
            if m[j,i]<>d then bn:=false;
        if bn then begin write('Yes'); close(output); halt; end;
      end;

  end;

end.

Задача F
program P_F;
{$APPTYPE CONSOLE}
uses SysUtils;
var n,i,a,b: Integer;
    sum: Longword;
begin
  AssignFile(input, 'input.txt'); Reset(input);
  AssignFile(output, 'output.txt'); Rewrite(output);
  ReadLn(n);
  sum:=0;
  for i:=1 to n do
  begin
    readln(a,b);
    sum:=sum+a*b;
  end;

  write(sum);
  close(input); close(output);
end.

Задача I
program P_I;
{$APPTYPE CONSOLE}
uses SysUtils;
var n,i,a,m1,m2: LongWord;
begin
  AssignFile(input, 'input.txt'); Reset(input);
  AssignFile(output, 'output.txt'); Rewrite(output);
  ReadLn(n);
  read(m1); read(m2);
  if m2<m1 then begin a:=m2; m2:=m1; m1:=a; end;
  for i:=3 to n do
  begin
    read(a);
    if a<m2 then m2:=a;
    if m2<m1 then begin a:=m2; m2:=m1; m1:=a; end;
  end;

  write(m1,' ',m2);
  close(input); close(output);
end.

Задача J
program P_J;
{$APPTYPE CONSOLE}
uses SysUtils;
var
  a,b: array [0..99999] of LongInt;
  f,l,k,i,n: LongInt;
  za,zb: array [0..99999] of LongInt; // кол-во открыв и закрыв скобок
  u: LongInt; // хранит сколько скобок открыто
begin
  AssignFile(input, 'input.txt'); Reset(input);
  AssignFile(output, 'output.txt'); Rewrite(output);

  readln(n);
  for i := 0 to n-1 do read(a[i]); readln;
  for i := 0 to n-1 do read(b[i]); readln;

  readln(k);
  for i := 1 to k do
  begin
    read(f); readln(l);
    za[f]:=za[f]+1; zb[l]:=zb[l]+1;
  end;

  for i:= 0 to n-1 do
  begin
    inc(u,za[i]);
    if u>0 then write(a[i],' ') else write(b[i],' ');
    dec(u,zb[i]);
  end;

  close(input); close(output);
end.

Про задачу J.
Для того, чтобы ускорить работу алгоритма нужно отказаться от многократного копирования одних и тех же элементов… Можно вообще ничего не копировать, а выводить элемент первого или второго массива… Сразу мне пришла мысль что нужно просто запоминать интервалы от и до — левый и правый края интервалов называю открывающей и закрывающей скобками… Каждая открывающая скобка всё более открывает интервал (inc(u,za[i]);) и каждая закрывающая всё более закрывает (dec(u,zb[i]);), вплоть до нуля. Запускаю цикл по количеству элементов массива и проверяю условие: если для текущей позиции интервал открыт, то пишу элемент первого массива, иначе второго. Никакого копирования вообще нет…
if u>0 then write(a[i],' ') else write(b[i],' ');
  • avatar
  • belan
  • 13 апреля 2014, 16:36
+1
— нашел время вернуться к задачкам прошлого года — задача B, как видите, была сдана только двумя командами…
— задача комбинаторная -> возможна большая размерность или долгая протяженность :) перебора и зашкаливание за отведенные рамки размышлений при максимально больших входных файлах…
— к сожалению провести через контестер нет возможности, поэтому, объективности ради, следует отметить, что я проверял только на небольших входных файлах мною же и подготовленных…
— пока решение не публикую, так как есть ещё самостоятельноеёпытающиеся одолеть :)
— конечно, основано решение на побитной операции OR…
-
+1
— да, забыл отметить — потратил на задачу B не менее часа (может часа 1,5)… как-то не удосужился засекать, раз так мало команд её решали, то подумал, что будет сложная очень…
+1
Задача В оказалась не такая уж и сложная, в целом та же задача про рюкзак, только сбоку. Решение заняло около получаса. Нужно, конечно, проверить на больших значениях, но все же. Свое решение, если нужно, могу выложить.
комментарий был удален
комментарий был удален
комментарий был удален
комментарий был удален
комментарий был удален

Прокомментировать