ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила
вернуться в форум

Обсуждение задачи 1064. Бинарный поиск

Why it doesn't work? (but passes all 2000-2001 real ACM test) - program inside
Послано Arkadiy 19 ноя 2001 16:49
type
 interv = record
  a,b:integer;
 end;
var
 A:array[0..9999] of integer;
 IX,j,N,LX: integer;
 otvet: array[1..5001] of interv;
 num_otv: integer;
 no_curr_interval:boolean;
 t:integer;
{ g,f:text;}

function BinarySearch(x:integer):integer;
var p,q,i,L:integer;
begin
 p:=0;
 q:=N-1;
 L:=0;
 while p<=q do begin
   i:=(p+q) div 2;
   inc(L);
   if A[i]=x then begin
     BinarySearch:=L;
     exit;
   end;
   if x<A[i] then q:=i-1 else p:=i+1; end;
end;

begin
{assign(f,'in');
assign(g,'out');
reset(f);
rewrite(g);}

 readln({f,}IX,LX);
 num_otv:=0;
 no_curr_interval:=true;

 for j:=0 to 9999 do A[j]:=j;

 for j:=0 to 9999 do
 begin
  N:=j+1;
  t:=BinarySearch(IX);
  if (t<>LX) and no_curr_interval then continue;
  if (t<>LX) then begin otvet[num_otv].b:=N-1;
no_curr_interval:=true; continue; end;
  {t=LX}
  if not(no_curr_interval) then continue;
  no_curr_interval:=false;
  inc(num_otv);
  otvet[num_otv].a:=N;
 end;
 if not no_curr_interval then otvet[num_otv].b:=10000;

 writeln({g,}num_otv);
 for j:=1 to num_otv do
 begin
  writeln({g,}otvet[j].a,' ',otvet[j].b);
 end;
{ close(f);
 close(g);}

end.
Re: Why it doesn't work? (but passes all 2000-2001 real ACM test) - program inside
Послано Flyer 22 ноя 2001 20:15
 Hi. Did you take part in that contest? &#1052;&#1086;&#1078;&#1085;&#1086; &#1103; &#1087;&#1086;-&#1088;&#1091;&#1089;&#1089;&#1082;&#1080;
&#1073;&#1091;&#1076;&#1091;? :) &#1052;&#1085;&#1077; &#1082;&#1072;&#1078;&#1077;&#1090;&#1089;&#1103;, &#1095;&#1090;&#1086; &#1090;&#1099; &#1085;&#1077; &#1091;&#1095;&#1080;&#1090;&#1099;&#1074;&#1072;&#1077;&#1096;&#1100; &#1082;&#1072;&#1082;&#1086;&#1081;-&#1090;&#1086; &#1082;&#1088;&#1072;&#1081;&#1085;&#1080;&#1081;
&#1089;&#1083;&#1091;&#1095;&#1072;&#1081;... &#1052;&#1086;&#1103; &#1087;&#1088;&#1086;&#1075;&#1088;&#1072;&#1084;&#1084;&#1072; &#1090;&#1086;&#1078;&#1077; &#1085;&#1077; &#1080;&#1076;&#1077;&#1090; :( &#1053;&#1086; &#1074;&#1077;&#1076;&#1100; &#1091; &#1076;&#1088;&#1091;&#1075;&#1080;&#1093;-&#1090;&#1086;
&#1087;&#1088;&#1086;&#1093;&#1086;&#1076;&#1080;&#1090;. &#1050;&#1089;&#1090;&#1072;&#1090;&#1080;, &#1090;&#1099; &#1073;&#1091;&#1076;&#1077;&#1096;&#1100; &#1085;&#1072; &#1101;&#1090;&#1086;&#1084; &#1087;&#1086;&#1083;&#1091;&#1092;&#1080;&#1085;&#1072;&#1083;&#1077;? &#1045;&#1089;&#1083;&#1080; &#1076;&#1072;, &#1090;&#1086;
&#1089;&#1082;&#1072;&#1078;&#1080; &#1074; &#1082;&#1072;&#1082;&#1086;&#1081; &#1082;&#1086;&#1084;&#1072;&#1085;&#1076;&#1077; :)
Re: Why it doesn't work? (but passes all 2000-2001 real ACM test) - program inside
Послано Scythe (Berinde Radu) 24 ноя 2001 10:23
Because binarysearch doesnt return any valid value in case
it doesnt find anything. You should add a line before end;
of proc binarysearch something like binarysearch := 1000;
(LX <= 14)
Re: Why it doesn't work? (but passes all 2000-2001 real ACM test) - program inside
Послано Arkadiy 24 ноя 2001 21:41
I am captain of KubanState University, Krasnodar
(KubanSU#1)..
&#1076;&#1072; &#1085;&#1072; &#1087;&#1086;&#1083;&#1091;&#1092;&#1080;&#1085;&#1072;&#1083;&#1077; &#1103; &#1073;&#1091;&#1076;&#1091;... &#1079;&#1072;&#1074;&#1090;&#1088;&#1072; &#1074;&#1099;&#1083;&#1077;&#1090;&#1072;&#1102; &#1089; &#1082;&#1086;&#1084;&#1072;&#1085;&#1076;&#1086;&#1081; &#1085;&#1072;
&#1089;&#1072;&#1084;&#1086;&#1083;&#1077;&#1090;&#1077; ;-)
&#1055;&#1086;&#1076;&#1086;&#1081;&#1076;&#1080; &#1082;&#1086; &#1084;&#1085;&#1077; &#1085;&#1072; &#1089;&#1086;&#1088;&#1077;&#1074;&#1085;&#1086;&#1074;&#1072;&#1085;&#1080;&#1080;, &#1087;&#1086;&#1079;&#1085;&#1072;&#1082;&#1086;&#1084;&#1080;&#1084;&#1089;&#1103;...
Thanks!!! Of course!!!
Послано Arkadiy 24 ноя 2001 22:03
Only binarysearch:=-1 before 'end;' needed!!!
And all work fine!!!