Поиск по этому блогу

суббота, 26 ноября 2016 г.

Калитка в заборе (задача)

Задача взята из этапа Всероссийской олимпиады школьников по информатике. Буду рад если ее решение будет полезно моим коллегам в подготовке учеников  к подобным соревнованиям.

Дядя Фёдор, кот Матроскин и Шарик решили обновить забор вокруг своего сада в Простоквашино. Матроскин и Шарик, недолго думая, вкопали столбов вдоль одной из сторон участка. Это очень сильно расстроило Дядю Фёдора, так как его друзья забыли о самом главном — калитка должна находиться именно на этой стороне, и для неё необходимо было оставить проём шириной как минимум WТеперь им придётся выкапывать некоторые столбы.
Чтобы работа не пропадала даром, выкопать надо как можно меньше столбов. Помогите Дяде Фёдору определить, какие именно столбы надо выкопать. После выкапывания столбов должен найтись промежуток (между двумя оставшимися столбами, или между оставшимся столбом и концом стороны участка, или между двумя концами стороны участка) ширины больше или равной W.



Формат входных данных
Первая строка содержит два целых числа и W— количество вкопанных столбов и минимально необходимую ширину проёма для калитки соответственно. Га­рантируется, что 0 <= <= 30 000 и что 0 <= W< =60 000.
Будем считать, что вдоль интересующей нас стороны участка введена ось координат. Во второй строке входного файла находятся два числаLи R— координаты левого и правого конца этой стороны (L < R). Далее следуют чисел — координаты вкопанных столбов. Все координаты (включая Lи R— различные целые числа, по модулю не превосходящие 30 000. Гарантируется, что все столбы вкопаны между левым и правым концами стороны.
Формат выходных данных
В первой строке выходного файла должно быть минимальное число столбов, которые надо выкопать. Далее должны следовать номера этих столбов. Столбы нумеруются в том порядке, как они указаны во входном файле, начиная с 1.

Если решений несколько, то вы можете вывести любое. Если решения нет, то выведите в выходной файл одну строку, содержащую число -1.
Пример
Входной файл
Выходной файл
3 2
2 6
3 4 5
1 2
3 2
1 6
4 3 5
0
3 5 1 7 5 3 4
3 2 1 3

Решение.

Описываем массив а, где будут храниться денные о столбах - в первой строке и их номерах - во второй строке.
{1}Считываем из входного файла первые две строки, в которых указано  - количество столбов, ширина калитки, координаты крайних столбов.
{2} Проверяем хватает ли калитки места. Если нет, в специальную переменную t присваиваем значение -1. Если хватает, считываем координаты оставшихся столбов, присваивая им номера.
{3} Упорядочиваем массив столбов по их координатам, сохраняя нумерацию.
{4}  Выбираем какие столбы надо выкопать.

program calitka;
uses crt;
var f,f1:text;
    a:array [0..3001,1..2] of integer;
    i,n,j,w, o,d,g,t,x,y:longint;

   begin
clrscr;
  assign(f,'input.txt');
  assign(f1,'output.txt');
  reset(f);
  rewrite(f1);
{1}
  readln(f,n,w);
   readln(f,a[0,1],a[n+1,1]);
{2}
if a[n+1,1]-a[0,1]<w then t:=-1 else begin
  for i:=1 to n do  begin
   read(f,a[i,1]); a[i,2]:=i; end;
{3}
 for i:=1 to n-1 do
   begin
    d:=a[i,1];  o:=i;
    for j:=i+1 to n do
    begin
     if d> a[j,1] then begin d:=a[j,1]; o:=j; end;
    end;
      g:=a[i,1];
      a[i,1]:=a[o,1];
      a[o,1]:= g;
      g:=a[i,2];
      a[i,2]:=a[o,2];
      a[o,2]:= g;
    end;
      writeln;
{4}
 t:=-1; j:=0;
 while (j<=n) and(t=-1) do
   begin
    i:=1;
    repeat
      if abs(a[i-1,1]-a[i+j,1])>= w then
      begin t:=0; x:=i-1; y:=i+j;  end;
      i:=i+1;
    until (i+i>n) or (t=0);
   j:=j+1;
   end;
 end;
   if t=0 then
     if y-x=1 then writeln(f1,t) else for i:=x+1 to y-1 do write(f1,a[i,2],' ')
     else
writeln(f1,t) ;

 close(f);
 close(f1);
 end.

Комментариев нет:

Отправить комментарий