Встреча 23.04.2012
Дабы разгрузить немного основной топик давайте в этом топике обсуждать решения задач со встречи 23.04.2012. Сами задачи находятся здесь.
-
Chiliec,
- 23 апреля 2012, 23:43
- рейтинг: +1
- belan
- 24 апреля 2012, 00:23
— моё решение задачи про «Магнитные бури»
— решил даже функцию max_mas сделать без параметров, а значения в ней оказываются просто ввиду наличия глобальных переменных :)
— писал на скорую руку, оптимизацией не занимался, но формальную проверку этот код прошел :)
— решил даже функцию 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.
— сегодня специально выкроил время, чтобы решить задачу про «Охота на зайцев»
— контестер прошел с первой попытки, но до этого было затруднение
— время засекал — чистое время решения 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;
Эту проблему я обсуждал в соответсвующей теме ранее: Обработка малых чисел.
— контестер прошел с первой попытки, но до этого было затруднение
— время засекал — чистое время решения 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.- belan
- 28 апреля 2012, 23:07
— что то участники турнира молчат…
— какие сложности выявили при решении задач?
— я подозреваю (опубликуйте своё решение), что у команды «Настя-Вадим» программа «Охота на зайцев» могла не выдавать всех правильных решений по причине ограниченной типом точности вычислений — см. коммент. к моему решению выше
— столкнулся с проблемой, которая могла бы, если бы встретилась на олимпиаде, привести к глобальным потерям времени — начал решать задачу про «Шифр Бэкона», ну как обычно в лоб и без бумажки… накрутил что-то совсем неоптимальное, но при запуске на у себя на машине программа вроде работала — запустил на формальную проверку — ответ: «Time Limit» — потратил некоторое время на оптимизацию — но результат всё тот же — и только по прошествии значительного времени и ПОДГЛЯДЫВАНИЯ В ИНТЕРНЕТ понял, что подобные задачи решаются с использованием специального подхода, так что ВЫВОД: решение в лоб может привести к большим ПОТЕРЯМ ВРЕМЕНИ
— моё решение было таким:
— рекомендую игрокам прорешать все задачи и опубликовать своё решение, было бы неплохо и с анализом как делал, что не прошло, что исправил…
— какие сложности выявили при решении задач?
— я подозреваю (опубликуйте своё решение), что у команды «Настя-Вадим» программа «Охота на зайцев» могла не выдавать всех правильных решений по причине ограниченной типом точности вычислений — см. коммент. к моему решению выше
— столкнулся с проблемой, которая могла бы, если бы встретилась на олимпиаде, привести к глобальным потерям времени — начал решать задачу про «Шифр Бэкона», ну как обычно в лоб и без бумажки… накрутил что-то совсем неоптимальное, но при запуске на у себя на машине программа вроде работала — запустил на формальную проверку — ответ: «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.
— рекомендую игрокам прорешать все задачи и опубликовать своё решение, было бы неплохо и с анализом как делал, что не прошло, что исправил…
Похожие записи для топика «Встреча 23.04.2012»