Phủ đoạn 2

Cho n đoạn thẳng <a_i , b_i> với các điểm đầu a_i và điểm cuối b_i là những số nguyên trong khoảng -1000..1000,
 a_i < b_i và thuộc một trong 4 dạng sau đây:

[d,c] - đoạn đóng: chứa điểm đầu d và điểm cuối c,

(d,c] - đoạn mở trái: không chứa điểm đầu d, chứa điểm cuối c,

[d,c) - đoạn mở phải: chứa điểm đầu d, không chứa điểm cuối c,

(d,c) - đoạn mở: không chứa điểm đầu d và điểm cuối c.

Hãy chỉ ra ít nhất K đoạn thẳng sao cho khi đặt chúng trên trục số thì có thể phủ kín đoạn <x, y> với tọa độ nguyên cho trước.

DOAN.INP	DOAN.OUT		Dữ liệu vào: tệp văn bản DOAN.INP Dòng đầu tiên: số tự nhiên 1 < N £ 1000. Dòng thứ hai: Đoạn  x  y Từ dòng thứ ba liệt kê các đoạn, mỗi dòng có thể chứa nhiều đoạn, mỗi đoạn được ghi trọn trên một dòng. Dữ liệu ra: tệp văn bản DOAN.OUT Dòng đầu tiên: số  K, nếu vô nghiệm K=0. Tiếp theo là K số tự nhiên biểu thị chỉ số của các đoạn thẳng phủ kín đoạn x  y.
6 (4,10 ) (-2, 5) [ 5 , 7]  [6, 7) [7, 8)  (8,9)  (7 , 10 ]	3 1 2 6

Kết quả trên cho biết ít nhất là 3 đoạn 1, 2 và 6 sẽ phủ kín đoạn (4,10).

Chú ý: Giữa các số và các ký tự trong file input có thể chứa các dấu cách.

Thuật toán

Phương pháp: Tham

                Để ứng dụng thuật toán của bài Phủ đoạn 1 ta đưa các đoạn về cùng một dạng đóng bằng cách chỉnh lại các đầu mở. Cụ thể là thêm/bớt điểm đầu mở của mỗi đoạn một lượng e = 0.3 như sau, 

[d,c] giữ nguyên

(d,c] ® [d + e, c],

[d,c) ® [d, c - e],

(d,c) ® [d + e, c - e].

                Qui tắc trên khá dễ hiểu.  Bạn hãy giải thích vì sao chọn e = 0.3 mà không chọn e = 0.5?

                Hai trường a và b thể hiện các điểm đầu và cuối mỗi đoạn cần được khai báo kiểu real (float). Các biến liên quan đến các trường này trong thủ tục xử lí cũng cần được khai báo theo các kiểu trên.

                Ta đọc tất cả các đoạn và ghi vào mảng d[0..N], trong đó d[0] sẽ chứa đoạn x, y.

                Cách đọc các đoạn được tổ chức trên cơ sở giả thiết là các đoạn được viết đúng cú pháp. Mỗi lần ta đọc một kí tự ch từ tệp input. Nếu (ch = ‘(‘) hoặc (ch = ‘[‘) thì ta gặp kí tự đầu đoạn: ta tiến hành đọc một đoạn. Để đọc một đoạn ta lần lượt đọc số thứ nhất, bỏ qua dấu phảy (‘,’) ngăn cách giữa hai số rồi đọc số thứ hai. Thủ tục đọc một đoạn kết thúc khi gặp một trong hai dấu đóng ngoặc là ‘]’ hoặc ‘)’. Căn cứ vào các dấu mở và đóng ngoặc đầu và cuối mỗi đoạn ta xác định lượng  e cần thêm hoặc bớt cho mỗi điểm đầu hoặc cuối đoạn, đương nhiên các điểm này cần được biểu diễn dưới dạng số thực.

            Độ phức tạp: N².

Chú ý

                Bạn có thể dùng kỹ thuật đồng dạng chuyển trục số sang trục số "phóng đại" gấp 3 lần. Khi đó các đoạn tương ứng sẽ được chuyển như sau:

[d,c] ® [3d - 1, 3c + 1],

(d,c] ® [3d + 1, 3c + 1],

[d,c) ® [3d - 1, 3c - 1],

(d,c) ® [3d + 1, 3c - 1].

Tức là giữ lại kiểu nguyên và chọn e = 1. Cách làm này có đơn giản hơn trong trường hợp giới hạn của d và c là nhỏ.

 (*  Pascal  *)

(*========================================

                Phu doan 2

  =========================================*)

program PhuDoan2;

uses crt;

const

  mn = 2002; bl = #32; nl = #13#10;

  fn = 'doan.inp'; gn = 'doan.out';

  MoVuong = '['; DongVuong = ']'; MoTron = '('; DongTron = ')';

  NgoacMo = [MoVuong, MoTron]; NgoacDong = [DongVuong, DongTron];

  ChuSo = ['0'..'9']; CongTru = ['+','-']; eps = 0.3;

type

  KieuDoan = record

a,b: real;

id: integer; { chỉ số đoạn }

 end;

  md1 = array[0..mn] of KieuDoan;

  mi1 = array[0..mn] of integer;

var n: integer; { n - so luong doan }

    d: md1;

    f,g: text;

    t: mi1;

    xy: KieuDoan;

    ch: char;

    k: integer; {dem so doan da doc}

    Ngoac: char;

(* Doc 1 so nguyen tu input file *)

function DocSo: integer;

var s,dau: integer;

begin

  s := 0; dau := 1;

  while not (ch in (CongTru + ChuSo)) do read(f,ch);

  if (ch in CongTru) then

  begin

    if (ch = '-') then dau := -1;

    read(f,ch);

  end;

  while not (ch in ChuSo) do read(f,ch);

  repeat

    s := 10*s + ord(ch) - ord('0');

    read(f,ch);

  until not (ch in ChuSo);

  DocSo := dau * s;

end;

procedure DocDoan;

begin

  k := k + 1; d[k].id := k; Ngoac := ch; d[k].a := DocSo;

  if (Ngoac = MoTron) then d[k].a := d[k].a + eps;

  while (ch <> ',') do read(f,ch);

  d[k].b := DocSo;

  while not(ch in NgoacDong) do read(f,ch);

  if (ch = DongTron) then d[k].b := d[k].b - eps;

end;

procedure Doc;

 var i: integer;

begin

  assign(f,fn); reset(f); readln(f,n); k := -1;

  while (k < n) and (not eof(f)) do

  begin

    read(f,ch);

    if (ch in NgoacMo) then DocDoan;

  end;

  close(f); xy.a := d[0].a; xy.b := d[0].b;

end;

procedure Qsort(l,r: integer): xem bài phủ đoạn 1;

function Tim(id,ic: integer; x: real): xem bài phủ đoạn 1;

procedure Ket(k: integer): xem bài phủ đoạn 1;

procedure XuLi: xem bài phủ đoạn 1;

BEGIN

  Doc; Qsort(1,n); XuLi;

END.

Nguồn:

SÁNG TẠO

TRONG THUẬT TOÁN

VÀ

LẬP TRÌNH