Комментарии (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
Задача В оказалась не такая уж и сложная, в целом та же задача про рюкзак, только сбоку. Решение заняло около получаса. Нужно, конечно, проверить на больших значениях, но все же. Свое решение, если нужно, могу выложить.

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