Встреча 23.04.2012

Дабы разгрузить немного основной топик давайте в этом топике обсуждать решения задач со встречи 23.04.2012. Сами задачи находятся здесь.

Похожие записи для топика «Встреча 23.04.2012»

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

  • avatar
  • belan
  • 24 апреля 2012, 00:23
+1
— моё решение задачи про «Магнитные бури»
— решил даже функцию max_mas сделать без параметров, а значения в ней оказываются просто ввиду наличия глобальных переменных :)
— писал на скорую руку, оптимизацией не занимался, но формальную проверку этот код прошел :)
program P_MB;
{$APPTYPE CONSOLE}
uses SysUtils;
var m,n,kon,i: integer;
    mas: array of integer;

function max_mas: integer;
var max,j: integer;
begin
  max:=mas[i];
  for j:=i+1 to i+m-1 do
    if mas[j]>max then max:=mas[j];
  max_mas:=max;
end;

begin

  readln(m); n:=0;
  while not eof(input) do
  begin
    readln(kon);
    if kon<>-1 then
    begin
      inc(n); setlength(mas,n);
      mas[n-1]:=kon;
    end;
  end;

  for i:=0 to n-m do
    writeln(max_mas);

end.
+2
— сегодня специально выкроил время, чтобы решить задачу про «Охота на зайцев»
— контестер прошел с первой попытки, но до этого было затруднение
— время засекал — чистое время решения 30 минут + 10 минут исправлял ошибку + 5 минут проверка разных вариантов, ну и, кончено, мне никто особенно не мешал (только чуть-чуть) и я знал задачу заранее
— ошибка была невынужденная — просто там где нужно было считать sqr(x1-x2) и sqr(y1-y2) я набросал заготовку sqr(x1) и sqr(y1) и минусовать вторую точку забыл :(
— писал в лоб программу, без продумывания алгоритма, без бумажки, без набросков кода — поэтому есть неоптимальности :)
— основная идея, которая может быть отличается от других реализций, состоит в оригинальном способе проверки третьей точки — лежит ли она на одной прямой с двумя базовыми — суть способа вот в чем: чтобы точка 3 лежала на одной прямой с точками 1 и 2 сумма расстояний 1-2 и 2-3 должна быть равна расстоянию 1-3
— плюс я ещё сделал попытку защиты кода от невынужденных ошибок связанных с ограниченной точностью вычислений и вместо того чтобы написать так:
b1:= distance(t1,t2) + distance(t2,t3) = distance(t1,t3);
я написал так:
b1:=(distance(t1,t2)+distance(t2,t3)-distance(t1,t3))<gr;
Эту проблему я обсуждал в соответсвующей теме ранее: Обработка малых чисел.
program P_MB;
{$APPTYPE CONSOLE}
uses SysUtils;
type my=record
  x,y: integer;
end;
const gr=0.0000000001;
var n,i: integer;
    mas: array of my;

function distance(d1,d2: integer): real;
begin
  distance:=sqrt(sqr(mas[d1].x-mas[d2].x)+sqr(mas[d1].y-mas[d2].y));
end;

function proverka(t1,t2,t3: integer): boolean;
var b1,b2,b3: boolean;
begin
  b1:=(distance(t1,t2)+distance(t2,t3)-distance(t1,t3))<gr;
  b2:=(distance(t1,t3)+distance(t2,t3)-distance(t1,t2))<gr;
  b3:=(distance(t1,t2)+distance(t1,t3)-distance(t2,t3))<gr;
  proverka:= b1 or b2 or b3;
end;

function max_z: integer;
var a,b,c,max,temp: integer;
begin
  max:=2;
  for a:=0 to n-1 -1 do
    for b:=a+1 to n-1 do
    begin
      temp:=2;
      for c:=0 to n-1 do
        if (c<>a) and (c<>b) then
          if proverka(a,b,c) then inc(temp);
      if temp>max then max:=temp;
    end;
  max_z:=max;
end;

begin
  readln(n); // кол-во зайцев
  setlength(mas,n);
  for i:=0 to n-1 do
    readln(mas[i].x,mas[i].y);
  write(max_z);
end.
  • avatar
  • belan
  • 28 апреля 2012, 23:07
0
— что то участники турнира молчат…
— какие сложности выявили при решении задач?
— я подозреваю (опубликуйте своё решение), что у команды «Настя-Вадим» программа «Охота на зайцев» могла не выдавать всех правильных решений по причине ограниченной типом точности вычислений — см. коммент. к моему решению выше
— столкнулся с проблемой, которая могла бы, если бы встретилась на олимпиаде, привести к глобальным потерям времени — начал решать задачу про «Шифр Бэкона», ну как обычно в лоб и без бумажки… накрутил что-то совсем неоптимальное, но при запуске на у себя на машине программа вроде работала — запустил на формальную проверку — ответ: «Time Limit» — потратил некоторое время на оптимизацию — но результат всё тот же — и только по прошествии значительного времени и ПОДГЛЯДЫВАНИЯ В ИНТЕРНЕТ понял, что подобные задачи решаются с использованием специального подхода, так что ВЫВОД: решение в лоб может привести к большим ПОТЕРЯМ ВРЕМЕНИ
— моё решение было таким:
uses Strings;
{$X+}
type my=array[0..2000] of char;
var s,temp: my;
    ots,i,slen: integer;
    str: array of my;
    x: LongInt;
function proverka: boolean;
var y: integer;
    b: boolean;
begin
  b:=true;
  for y:=0 to x do
    if strcomp(str[y],temp)=0 then
      begin b:=false; break; end;
  proverka:=b;
end;

begin
  assign(input,'input.txt');   reset(input);
  assign(output,'output.txt'); rewrite(output);

  read(s);
  slen:=StrLen(s)-1;
  x:=-1;
  for ots:=0 to slen do
  begin

    for i:=0 to StrLen(s)-1 do
    begin
      temp:=strlcopy(temp,s,i+1);
//      writeln(temp);//вывод всех подстрок
      if proverka then
      begin
        inc(x);
        SetLength(str,x+1);
        str[x]:=temp;
      end;
    end;
    for i:=0 to StrLen(s)-1 do
      s[i]:=s[i+1];
  end;
//  for i:=0 to x do  writeln(str[i]);//вывод неповторяющихся подстрок
//  writeln;
  write(x+1);
  close(input); close(output);
end.

— рекомендую игрокам прорешать все задачи и опубликовать своё решение, было бы неплохо и с анализом как делал, что не прошло, что исправил…

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