admin có thể xem xét nâng time bài này lên 1 chút k ạ , time chặt quá

cho hỏi có 1 người có thể nằm trong phạm vị của hơn 1 nhà hàng không ạ ???

sao lại cho p số nguyên dương p_1 ... p_n ạ 

mấy admin cho em hỏi trang spoj bị dì thế ạ ?

hình như cái hình minh họa có dì đó không đúng :v

Tác giả: Đỗ Mạnh Dũng

Hình học đối với giác quan của con người thì khá quen thuộc và dễ dàng. Nhưng hình học đối với máy tính thì lại là một vấn đề khác. Nhiếu bài toán ta có thể giải ngay lập tức bằng cách “nhìn vào hình vẽ ta thấy”, nhưng để thể hiện trên máy tính thì cần những chương trình không đơn giản chút nào.

Các giải thuật hình học thường là các giải thuật đẹp và đôi khi là rất bất ngờ. Thực vậy, những tưởng có những bài toán ta phải giải quyết với chi phí thuật toán rất lớn (đôi khi không thể chấp nhận được), nhưng nhờ vào chính những tính chất đặc biệt của hình học mà ta lại có thể giải quyết nó một cách dễ dàng và “đẹp mắt”.

I. Biểu diễn hình học trên máy tính.

Đây không phải là một vấn đề khó khăn. Nhưng ta nên có một cách biểu diễn thống nhất cho riêng mình, như vậy sẽ dễ dàng trong việc thể hiện thuật toán. Thông thường người ta có cách biểu diễn như sau:

Điểm:

Point = record
  x, y: Real;
end;

Đường thẳng:

Line = Record
  p1, p2: Point;
end;

Đa giác:

Polygon = array[1..n] of Point;

Để thuận lợi thì khi biểu diễn đa giác ta nên thêm hai đỉnh ở đầu và cuối: đỉnh 0 bằng đỉnh n và đỉnh n + 1 bằng đỉnh 1.

Từ đây ta cũng thống nhất với cách khai báo này cho các đoạn chương trình có thể dùng đến.

Chú ý: Ta dễ dàng nhận thấy rằng các phép toán thực hiện để giải quyết bài toán hình học thì hầu hết là phải làm việc với số thực. Vì vậy ta cũng cần phải chú ý một số mẹo nhỏ khi khai báo dữ liệu và biên dịch. Tuỳ vào kích thước và yêu cầu về độ chính xác của kết quả bài toán ta phải có những chọn lựa hợp lý. Bảng dưới đây là những kiểu số thực mà Pascal có sẵn:

Đặc biệt, mặc dù chỉ khi ta dùng Double hoặc Extended ta mới phải khai báo biên dịch {$N+}, nhưng ta nên lúc nào cũng làm như vậy. Vì khi đó máy tính sẽ dùng bộ đồng xử lý toán học, các phép toán với số thực sẽ thực hiện nhanh chẳng kém gì so với số nguyên (thậm chí còn nhanh hơn nếu ta dùng kiểu số thực Double). Tốt nhất hãy dùng thử và tự so sánh, sẽ thấy ngay sự khác biệt.

Một điều nữa cùng cần chú ý là sai số trong tính toán. Làm việc với số thực bao giờ ta cũng phải chấp nhận với những sai số nhất định. Vì vậy khi so sánh hai giá trị với nhau ta chú ý không được dùng dấu “=”, mà phải xét trị tuyệt đối hiệu hai giá trị với một giá trị Epsilon nào đó. Ở đây, Epsilon là một số tương đối bé, tuỳ vào yêu cầu của bài toán mà ta có chọn lựa về giá trị của nó.

Ví dụ: Không được dùng: if x1 = x2 then …

      mà phải dùng       : if Abs(x1 – x2) < Eps then …

II. Các phương pháp hình học.

1. Điểm, đoạn thẳng - đường thẳng, diện tích đa giác.

a. Quan hệ giữa các điểm - hàm CCW.

Điều gợi nhớ ta nhất khi nhắc đến quan hệ giữa các điểm là khoảng cách giữa chúng. Ta có thể tính khoảng cách giữa hai điểm như sau:

function Dist(p1, p2: Point): Real;

begin
  Dist := Sqrt(Sqr(p1.x – p2.x) + Sqr(p1.y – p2.y));
end;

Nhiều khi ta phải trả lời câu hỏi: “việc đi từ A, B sang C là ta đã rẻ phải hay rẽ trái?”. Điều này tưởng chừng như đơn giản và có cảm giác là vô nghĩa, nhưng thực tế nó lại rất quan trọng trong một số thuật toán cụ thể.

Ta có thể dùng tích có hướng trong không gian để giải quyết vấn đề này. Ta đang làm việc trong không gian 2 chiều (mặt phẳng) vì vậy đối với chiều thứ 3 thì mọi giá trị đều là Zero (nếu ai hỏi tích có hướng là gì thì xin tham khảo ở chỗ khác).

Hàm CCW sau trả ra -1 nếu là rẽ trái, 1 nếu rẽ phải, 0 nếu 3 điểm thẳng hàng. Bạn đọc có thể xử lý cụ thể hơn trong trường hợp 3 điểm thẳng hàng (điểm nào nằm ở giữa), nhưng trong nhiều ứng dụng thì điều đó là không cấn thiết.

function CCW(p1, p2, p3: Point): Integer;

var
  a1, b1, a2, b2, t: Real;

begin
  a1 := p2.x – p1.x;
  b1 := p2.y – p1.y;
  a2 := p3.x – p2.x;
  b2 := p3.y – p2.y;

  t := a1*b2 – a2*b1;
  if Abs(t) < Eps then CCW := 0
  else
    if t > 0 then CCW := 1
    else CCW := -1;
end;

b. Đường thẳng, đoạn thẳng và giao của chúng.

Để biểu diễn đường thẳng ta có thể biểu diễn bằng toạ độ hai điểm trên đường thẳng đó. Nhưng đôi khi để tiện lợi cho tính toán, ta phải có được phương trình dưới dạng tổng quát của nó. Điều này là dễ dàng, bạn đọc có thể tham khảo thủ tục sau.

procedure Extract(p1, p2: Point; var a, b, c: Real);

begin
  a := p1.y – p2.y;
  b := p2.x – p1.x;
  with p1 do c := -(a*x + b*y);
end;

Việc kiểm tra hai đoạn thẳng có cắt nhau không là cần thiết nhưng cũng không phải là một vấn đề khó. Hai đoạn thẳng cắt nhau khi hai đầu của đoạn này thì nằm về hai phía của đường thẳng chứa đoạn kia. Ta có thể dùng chính hàm CCW đã có. Nhưng cách làm thô thiển bình thường có vẻ còn tốt hơn:

function Intersect(l1, l2: Line): Boolean;

var
  a1, b1, c1, a2, b2, c2, t1, t2: Real;

begin
  Extract(l1.p1, l1.p2, a1, b1, c1);
  Extract(l2.p1, l2.p2, a2, b2, c2);

  with l1 do
    t1 := (p1.x*a2+p1.y*b2+c2)*(p2.x*a2+p2.y*b2+c2);

  with l2 do
    t2 := (p1.x*a1+p1.y*b1+c1)*(p2.x*a1+p2.y*b1+c1);

  Intersect := (t1 < Eps) and (t2 < Eps);
end;

Nếu ta muốn tính cụ thể toạ độ giao điểm của hai đường thẳng thì có lẽ vấn đề chỉ thuần tuý toán học thôi. Bạn đọc thử tự cài đặt xem sao.

c. Diện tích đa giác.

Để tính diện tích đa giác ta dùng cách tính diện tích của một hình bị giới hạn bởi các đường bất kỳ (kiến thức vi phân). Trong trường hợp này mọi đường giới hạn đều là đường thẳng nên việc tính toán cũng khá dễ dàng. Ta thử tham khảo thủ tục sau:

function Area: Real;

var
  i: Integer;
  S: Real;

begin
  p[n + 1] := p[1];
  S := 0;

  for i := 1 to n + 1 do
    S := S + (p[i].x – p[i – 1].x)*(p[i].y + p[i – 1].y);

  Area := Abs(S)/2;
end;

Việc ta lấy trị tuyệt đối của S là có lý do của nó. Nếu đi theo thứ tự p[1], p[2],…, p[n] là ngược chiều kim đồng hồ thì ta sẽ có S âm, còn ngược lại ta sẽ nhận được S dương. Điều này cũng khá quan trọng trong một số trường hợp cụ thể.

Chú ý: một định nghĩa chính xác hơn cho khái niệm thuận hay ngược chiều kim đồng hồ là như sau: Nếu ta đang đi thuận chiều kim đồng hồ thì phần trong của đa giác luôn ở bên phía tay phải ta, còn phía bên tay trái là phần ngoài đa giác. Tất nhiên sẽ là ngược chiều kim đồng hồ trong trường hợp còn lại.

2. Điểm nằm trong đa giác.

Bài toán: 

Cho một đa giác không tự cắt, hãy kiểm tra xem một điểm có nằm trong đa giác hay không?

Tư tưởng cho bài toán này nói qua thì rất đơn giản và dễ hiểu: Từ điểm cần kiểm tra ta kẻ một tia bất kỳ, nếu tia đó giao với đa giác một số chẵn lần thì có nghĩa là nó nằm ngoài đa giác, một số lẻ lần thì nó nằm trong đa giác.

Nhưng trên thực tế có rất nhiều trường hợp cần phải được giải quết triệt để:

Vì vậy, thuật giải của bài toán là như sau: Ta đi vòng quanh đa giác, mỗi khi ta đi từ một bên của tia sang một bên khác thì ta tính là một lần giao với đa giác. Dưới đây là một cách cài đặt, bạn đọc có thể cải tiến nó hoặc là tìm ra một cách cài đặt khác hay hơn. Ta dùng lại hàm Intersect đã nói ở phần trước.

Để tiện lợi, ta coi luôn đỉnh 1 là đỉnh thấp nhất của đa giác (có toạ độ y nhỏ nhất). Hơn nữa, việc ta chọn tia là tuỳ thích, vì vậy ta sẽ chọn tia song song và cùng chiều với chiều dương của trục Ox, như vậy sẽ rất dễ dàng cho tính toán.

function Inside(t: Point): Boolean;

var
  Count, i, l: Integer;
  Ray, li: Line;

begin
  if t.y <= p[1].y then
  begin {nếu t nằm dưới điểm thấp nhất của đa giác}
    Inside := False;
    Exit;
  end;

  Ray.p1 := t;
  Ray.p2.y := t.y;
  Ray.p2.x := max; {max là giá trị đủ lớn để lớn hơn mọi giá trị mà ta có thể xét đến}

  p[0] := p[n];
  p[n + 1] := p[1];

  Count := 0;
  l := 1; {biến l luu chỉ số điểm cuối cùng không nằm trên đường thẳng y = t.y}
  i := 1;

  while i <= n + 1 do
  begin
    if (p[i].y = t.y) and (t.x <= a[i].x) then
    begin {nếu điểm i nằm trên tia}
      while p[i].y = t.y do Inc(i);
      {đi tiếp trên đa giác, tìm điểm đầu tiên không thuộc 
       đường thẳng y = t.y. Ta yên tâm vòng lặp luôn dừng vì p[n + 1] = p[1]}
      if (p[i].y - t.y)*(p[l].y - t.y) < 0 then Inc(Count);
    end
    else
    begin
      li.p1 := p[l];
      li.p2 := p[i];
      if Intersect(Ray, li) then Inc(Count);
    end;

    l := i;
    Inc(i);
  end;
  Inside := Odd(Count);
end;

Trường hợp đặc biệt:

Đối với đa giác có toạ độ đỉnh nguyên, ta có thể không phải cài đặt phức tạp như trên. Nếu toạ độ điểm cần xét cũng nguyên, ta “xoay” tia cần xét đi một góc đủ nhỏ để loại đi trường hợp tia đi qua các đỉnh của đa giác. Còn nếu toạ độ điểm cần xét không nguyên thì hiển nhiên là không phải lo tia cần xét đi qua đỉnh của đa giác. Lúc này ta chỉ việc xét tất cả các cạnh của đa giác, cạnh nào cắt tia cần xét thì ta tăng biến đếm lên 1…

Nói chung, để xác định một điểm có nằm trong một đa giác hay không, ta mất một chi phí thuật toán là O(N). Nhưng đấy là trong trường hợp tổng quát, với một đa giác bất kỳ. Nhưng trong thực tế, nhiều khi ta gặp những trường hợp đặc biệt hơn nhiều. Trong những trường hợp đó ta không thể cứ áp dụng một cách thô thiển thuật toán trên vào được vì phải trả giá một chi phí thuật toán quá đắt.

Bài toán: 

Cho một đa giác lồi, hãy xác định xem một điểm có nằm trong đa giác đó hay không?

Ta hãy tận dụng tính “lồi” của đa giác. Vì là đa giác lồi nên nó chỉ giao với một đường thẳng bất kỳ tại không quá hai điểm (chính xác thì là 2 hoặc là 0). Chú ý, “giao” ở đây là khi ta đi vòng quanh đa giác, ta đi từ một bên của đường thẳng sang bên kia của nó.

Đến đây, hẳn nhiều bạn cũng đã rõ thuật toán. Thay bằng việc ta đi vòng quanh đa giác, ta chỉ tìm hai cạnh của đa giác cắt đường thẳng chứa điểm cần xét. Tất nhiên trường hợp không đoạn nào như vậy là tầm thường. Cũng có trường hợp có nhiều hơn hai đoạn như vậy nếu đường thẳng y = t.y đi qua đỉnh của đa giác. Nhưng cũng chẳng đáng chú ý, ta chọn một trong hai đoạn bất kỳ chứa đỉnh đó thôi. Sau khi chọn được hai cạnh của đa giác rồi, ta xét xem có bao nhiêu cạnh (trong hai cạnh) cắt tia cần xét. Để đơn giản, ta cũng trọn đường thẳng là đường y = t.y, và tia có hướng cùng chiều với chiều dương của trục Ox (Với cách trọn bất kỳ cũng không thực sự phức tạp hơn, bạn đọc hãy thử coi nó như là một trò giải trí?)

Chú ý rằng chi phí chủ yếu cho thuật toán này lại là phép tìm kiếm. Vì vậy, nếu ta áp dụng phép tìm kiếm tuần tự vào đây thì đúng là vô nghĩa. Bằng cách chia đa giác làm hai nửa, phân các nhau bởi hai điểm thấp “nhất” và “cao” nhất (hai đỉnh tô đậm trên hình vẽ). Ta chỉ phải tìm kiếm nhị phân (xin đọc phần “cấu trúc dữ liệu và giải thuật”) trên hai nửa này thôi, mỗi nửa sẽ tìm ra một cạnh thoả mãn. Ta tìm điểm i có toạ độ lớn nhất nhưng nhỏ hơn t.y, cạnh (p[i], p[i + 1]) sẽ là cạnh cần tìm. Như vậy, chi phí thuật toán cho bài toán này tỷ lệ với LogN. Đến đây, mọi việc gần như đã được giải quyết, các công việc còn lại là bài tập thực hành của bạn đọc.

Thuật toán chẳng có ý nghĩa gì khi câu hỏi “một điểm có nằm trong đa giác hay không?” chỉ được dùng có một lần. Nhưng trong trường hợp phải trả lời nhiều lần câu hỏi như vậy thì thuật toán thực sự đã phát huy tác dụng.

3. Bao lồi.

Bao lồi của một tập hợp điểm được định nghĩa là một đa giác lồi nhỏ nhất chứa toàn bộ tập điểm này. Một cách tương đương, bao lồi là một đường ngắn nhất bao quanh tập điểm. Bao lồi có một số tính chất dễ dàng nhận ra là: các đỉnh của nó phải thuộc tập điểm đã cho; với một đường thẳng bất kỳ nằm ngoài bao khi rời về phía bao thì sẽ chạm một trong các đỉnh của bao.

Bài toán: 

Cho tập điểm, tìm bao lồi của nó?

Chúng ta tạm bỏ qua một số ví dụ cực đoan như: tất cả tập điểm đếu nằm trên một đường thẳng?!!!...

a. Thuật toán bọc gói.

Đây là một giải thuật rất “con người”. Bắt đầu bằng việc chọn một điểm chắc chắn thuộc bao, dùng một tia quét ngược chiều kim đồng hồ cho đến khi gặp một điểm khác, ta được thêm một đỉnh thuộc bao, lại tiếp tục với điểm vừa tìm được…Quá trình kết thúc khi gặp lại đỉnh đầu tiên.

Các bước của thuật toán

Có nhiều cách chọn điểm đầu tiên, một trong cách đó là ta chọn điểm có hoành độ nhỏ nhất trong các điểm có tung độ nhỏ nhất.

Một điều đáng chú ý ở đây là việc quét một tia ngược theo chiều kim đồng hồ để tìm điểm đầu tiên chạm phải thực chất là ta tìm điểm mà tia nối từ điểm gốc tới nó tạo với trục hoành một góc bé nhất (điều này khá dễ hiểu thôi). Vì vậy chúng ta cũng cần phải biết cách tính góc khi cho điểm gốc và điểm cần xét đã. Nhưng chỉ với việc sắp xếp (tìm góc nhỏ nhất) thôi mà phải làm phức tạp đến vậy thì thật là uổng công. Ta có thể đưa ra một thứ tự hoàn toàn giống với việc tính góc cụ thể mà chương trình thì đơn giản hơn nhiều:

function Angle(p1, p: Point): Real;

var
  dx, dy, ax, ay, t: Real;

begin {p là điểm gốc}
  dx := p1.x – p.x;
  dy := p1.y – p.y;
  ax := Abs(dx);
  ay := Abs(dy);

  if ax + ay < Eps then t := 0
  else t := dy/(ax + ay);

  if dx < 0 then t := 2 – t
  else
    if dy < 0 then t := 4 + t;

  Angle := t;
end;

Sau đây là thủ tục tìm bao lồi theo thuật toán bọc gói.

procedure Wrap;

var
  i, li: Integer;
  min, tmp: Real;
  t: Point;

begin
  t := p[1];
  li := 1;

  for i := 2 to n do
    if (p[i].y < t.y)or(p[i].y = t.y)and(p[i].x < t.x) then
    begin
      t := p[i];
      li := i;
    end;

  p[n + 1] := t; {để phát hiện thời điểm kết thúc}
  m := 0; {m sẽ là số điểm trên bao}

  repeat
    Inc(m);
    p[li] := p[m];
    p[m] := t;

    min := max;

    for i := m + 1 to n + 1 do
    begin
      tmp := Angle(p[i], p[m]);
      if (tmp < min) or ((tmp = min) and
         (Abs(t.x–p[m].x) < Abs(p[i].x–p[m].x))) then
      begin {nếu nhiều điểm thoả mãn, chọn điểm ở xa nhất}
        min := tmp;
        li := i;
        t := p[i];
      end;
    end;
  until li = n + 1;
end;

b. Thuật toán Graham.

Thuật toán bọc gói đòi hỏi một chi phí là O(M*N) (trong đó M là số điểm trên bao). Vì vậy nó chỉ làm việc tốt trong trường hợp số điểm nằm trên bao nhỏ hơn nhiều so với tổng số. Nhưng trong trường hợp xấu nhất (tất cả mọi điểm đều nằm trên bao) thì chi phí thuật toán sẽ lên tới O(N²) - rất tồi tệ! Chúng ta sẽ tiếp cận một phương pháp tốt hơn – phương pháp quét Graham. Phương pháp này có chi phí thuật toán ổn định và không tốn kém lắm. Hầu như tất cả chi phí là dành cho việc khởi một tạo đường khép kín đơn từ tập điểm đã cho.

Chọn điểm chốt có hoành độ x lớn nhất trong các điểm có tung độ y nhỏ nhất (khi hiểu rõ thuật toán các bạn sẽ biết được nguyên nhân). Chuyển điểm chốt về vị trí 1 để tiện cho tính toán. Ta sắp xếp các điểm theo khoá là góc tạo bởi điểm đó và điểm chốt với trục hoành theo thứ tự tăng dần. Khi đi theo thứ tự p[1], p[2], …p[N], p[1] ta thu được một đa giác khép kín đơn.

Ta đi vòng qua đa giác này, thử đặt một điểm vào bao và kiểm tra xem các điểm trước đó có còn nằm trên bao hay không. Nếu không ta chỉ việc loại điểm đó ra khỏi bao thôi.

Việc kiểm ra một điểm có còn nằm trên bao hay không có thể làm như sau: khi cho một điểm mới vào bao, ta sẽ lần ngược lại những điểm đã nằm trong bao. Trong quá trình, nếu gặp một điểm là khúc rẽ phải thì điểm này sẽ không thuộc bao nữa, ta loại nó luôn. Quá trình kết thúc khi ta gặp một điểm là khúc rẽ trái, vì tất cả các điểm từ đó lùi về 1 chắc chắn sẽ thuộc bao.

Cài đặt không phải là một vấn đề khó nhưng phải cảnh giác với sai số và các điểm thẳng hàng.

Việc xây dựng đường khép kín đơn không thực sự phải dùng hàm Angle vì dễ gây sai số và chi phí hơi lớn. Vì tất cả các tia tạo bởi điểm chốt và một điểm bất kỳ đều trong góc phần tư I và II nên ta có thể dùng hàm Lower sau để làm phép so sánh cho việc sắp xếp.

function Lower(p1, p2: Point): Boolean;

var
  a1, b1, a2, b2: Real;

begin
  a1 := p1.x – p[1].x;
  b1 := p1.y – p[1].y;

  a2 := p2.x – p[1].x;
  b2 := p2.y – p[1].y;

  Lower := a1*b2 > a2*b1;
end;

Thực chất ta đã so sánh hai giá trị a1/b1 và a2/b2, tức là cotg của hai góc. Nhưng ta không làm như vậy vì phải xét b1, b2 liệu có bằng 0 hay không.

Sau đây là đoạn chương trình miêu tả phương pháp quét Graham. Ta coi mọi công việc khởi tạo đã xong xuôi. Hàm CCW đã nói tới ở phần trước.

procedure GrahamScan;

var
  i: Integer;

begin
  m := 2;
  for i := 3 to n do
  begin
    while CCW(p[m - 1], p[m], p[i]) <> 1 do Dec(m);
    Inc(m);
    p[m] := p[i];
  end;
end;

Chi phí cho thủ tục trên tỷ lệ thuận với N. Đúng vậy, mặc dù trong vòng lặp có một vòng lặp, nhưng ta để ý là không điểm nào bị loại quá một lần nên vòng lặp này chỉ hoạt động không đến N lần.

Như vậy chi phí cho thuật toán này là O(NlogN) nếu ta dùng phương pháp sắp xếp tốt (như Quick Sort chẳng hạn).

c. Cải tiến.

Ta có thể làm giảm chi phí tính toán đi rất nhiều bằng cách loại bỏ những điểm chắc chắn không thuộc bao.

Ví dụ như ta loại đi những điểm nằm hoàn toàn trong tứ giác có các đỉnh là các điểm có hoành độ lớn nhất, hoành độ nhỏ nhất, tung độ lớn nhất, tung độ nhỏ nhất. Đối với những bộ dữ liệu được tạo một cách ngẫu nhiên thì việc này rất có ích. Nhưng nếu tất cả các điểm đều thuộc bao thì việc này là vô nghĩa. Nói chung mọi cách tham lam thì cũng đều tốt trong một số trường hợp nhất định mà thôi.

4. Cặp điểm gần nhất.

Bài toán: 

Cho tập điểm, hãy tìm cặp điểm có khoảng cách nhỏ nhất trong tập điểm trên.

Một cách thô thiển ta có thể xét tất cả các cặp điểm và lưu lại cặp điểm có khoảng cách nhỏ nhất. Nhưng như vậy thì chi phí thuật toán sẽ là O(N²). Ta hoàn toàn có thể giải quết bài toán này với chi phí là O(NlogN) với việc áp dụng tư tưởng “chia để trị” của thuật toán Merge Sort (xin đọc phần “cấu trúc dữ liệu và giải thuật”). Ý tưởng thuật toán như sau: ta sắp xếp các điểm theo hoành độ (hoặc tung độ cũng được). Tại mỗi bước ta chia tập làm hai phần thì cặp điểm gần nhất sẽ nằm ở một trong hai phần hoặc là cặp điểm mà mỗi điểm thuộc một phần.

Vấn đề là phải xử lý trường hợp mỗi điểm nằm ở một phần, còn trường hợp cả hai điểm đều thuộc một phần thì đã được giải quyết vì lời gọi đệ qui. Ta có thể sử dụng ngay thứ tự sắp xếp và khoảng cách min đã tìm được được để làm cận cho trường hợp xét trên hai phần. Khi xét mỗi điểm ở nửa này, nếu gặp điểm ở nửa kia có hiệu hoành độ đến nó không nhỏ hơn khoảng cách min đã tìm được thì ta dừng luôn vì tập điểm đã được sắp theo x.

Nhưng như vậy vẫn có thể gặp phải trường hợp xấu: các điểm nằm sát hai bên đường phân cách; trong trường hợp đó, nếu xử lý không tốt thì chi phí có thể sẽ là O(N²).

Ta giải quyết vấn đề này bằng cách sắp các điểm theo tung độ y và xét tương tự như trên. Chú ý, nếu tại mỗi bước ta lại gọi thủ tục sắp xếp mỗi nửa thì chi phí thuật toán sẽ là O(Nlog²N), không phải là thực sự tốt lắm. Nhưng để ý một chút, ta thấy mỗi nửa đều được sắp xếp, hơn nữa cách làm của ta cũng đang dựa vào tư tưởng của Merge Sort, như vậy tại sao ta không sắp xếp theo kiểu Merge Sort ngay trong thủ tục đệ quy của mình. Như vậy hai công việc đều được sử lý đồng thời. Chi phí cho bài toán này giống như chi phí sắp xếp bằng Merge Sort, tỷ lệ với NlogN.

Cài đặt thuật toán này không khó nhưng khá tỉ mỉ. Ta bỏ qua bước sắp xếp tập điểm theo hoành độ x. Đầu tiên là thủ tục trộn hai phần, tiếp theo là thủ tục đệ quy tìm cặp điểm gần nhất.

procedure Merge(l, r: Integer);

var
  t: Polygon;
  i, j, m, c: Integer;

begin
  m := (l + r) div 2;
  i := l;
  j := m + 1;

  for c := 1 to r – l + 1 do
    if (j > r) or (p[i].y < p[j].y) then
    begin
      t[c] := p[i];
      Inc(i);
    end
    else
    begin
      t[c] := p[j];
      Inc(j);
    end;

  for c := 1 to r – l + 1 do p[l + c - 1] := t[c];
end;

procedure MinDist(l, r: Integer);

var
  i, j, j1, m: Integer;

begin
  if l = r then Exit;

  m := (l + r) div 2;

  MinDist(l, m);
  MinDist(m + 1, r); {gọi đệ quy tìm min trên hai phần}

  j1 := m + 1;
  for i := l to m do
  begin
    while (j1 <= r)and(p[j1].y – p[i].y >= min) do Inc(j1);

    for j := j1 to m do
      if p[j].y – p[i].y >= min then Break
      else
        if Dist(p[i], p[j]) < min then

        begin {cập nhật kết quả}
          min := Dist(p[i], p[j]);
          Result.x := p[i];
          Result.y := p[j];
        end;
  end;
  Merge(l, r); {trộn hai phần}
end;

Result là biến lưu kết quả, có cấu trúc giống như kiểu Line. Biến min dùng để lưu khoảng cách nhỏ nhất tìm được cho đến thời điểm hiện tại.

Có rất nhiều bài toán cần kiểm tra hoặc buộc phải kiểm tra tính giống nhau của hai thành phần nào đó với yêu cầu tốc độ cao. Muốn 'ăn' hết test bạn cần phải có một thuật giải tốt. Tôi xin nêu ra một cách làm tương đối hay như sau: Trước tiên, ta phát biểu dạng tổng quát của bài toán: 
Cho hai đối tương A, B (là các đồ thị, dãy số...). Hai phần tử A, B gọi là tương thích nếu A, B cùng thoả mãn tính chất nào đó. Bài toán yêu cầu kiểm tra sự tương thích giữa hai đối tương A, B. 
Thuật giải: Xây dựng một quy tắc mã hoá thoả mãn: Tất cả các đối tượng có cùng tính chất thì kết quả mã hoá phải giống nhau. 

Chúng ta hãy cùng xem 1 số ví dụ:

Bài 1: 

Cho hai cây A, B gồm N đỉnh (1 ≤ N ≤ 1000), gốc R1, R2. A, B gọi là tương đương nếu chỉ cần thay đổi nhãn các đỉnh của B thì thu được A. 
Yêu cầu: Hãy xác định A, B có tương đương không? 
Input : TREE.IN 

•  Dòng đầu ghi N. 
•  Dòng hai ghi R1 là gốc cây A. 
•  N - 1 dòng tiếp mô tả các cạnh của cây A. 
•  Dòng tiếp theo ghi R2 là gốc của B. 
•  N - 1 dòng tiếp mô tả các cạnh của cây A. 

Ouput : TREE.OUT 

•  Dòng đầu ghi là YES nếu tương đương, NO nếu không. 
•  Dòng thứ hai gồm N số, số thứ I là nhãn nút của cây B tương ứng với nút I của A. 

Nhận xét: 

•  Theo như đề bài hai gốc sẽ giữ cùng nhãn. 
•  Như vậy ta sẽ phải sắp xếp các nút con theo một trật tự để tương đương. Bạn có thể duyệt đến khoảng 100, nhưng > 1000 một thuật toán tối ưu hơn. 

Thuật giải: 

Xây dựng quy tắc mã hoá một cây sau: 

•  Bắt đầu từ nút gốc. Ta xây dựng đệ quy như sau: Tại mỗi nút, số đầu tiên của dãy mã hoá nút đó là: S là số nút con của đỉnh đó. Tiếp sau là dãy mã hoá nhỏ nhất của các nút con nó, và tiếp tục lớn dần. 
•  Như vậy ta thấy rằng: 1 dạng cây có duy nhất một cách mã hoá, và ngược lại một cách mã hoá xác định 1 dạng cây duy nhất. Hai cây tương đương khi và chỉ khi dãy mã hoá của chúng là giống nhau. 

{$N+,Q+,R+,S+} 
{$M 60384,0,655360} 
Const Tfi = 'TREE.IN'; 
      Tfo = 'TREE.OUT'; 
      MaxN = 1001; 

Type Pnode = ^Tnode; 
     Tnode = Record 
        x : Integer; 
        Next : Pnode; 
      End; 
     Arr1p = Array[0..MaxN] of Pnode; 
     Arr1i = Array[0..MaxN] of Integer; 


Var  Q1, Q2              : Arr1p; 
     Code                : Array [1..2] of Arr1p; 
     Tr1, Tr2            : Pnode; 
     Order, Nson1, Nson2 : Arr1i; 
     Visit               : Array [0..MaxN] of Byte; 
     N, R1, R2           : Integer; 
     Fi, Fo              : Text; 

Procedure Push (x : Integer; Var Last : Pnode); 
  Var p : Pnode; 
  Begin 
     New (p); 
     p^.x := x; 
     p^.Next := Last; 
     Last := p; 
  End; 

Procedure Readlist; 
  Var i, x, y : Integer; 
  Begin 
    Assign (Fi, Tfi); Reset (Fi); 
    Readln (Fi, N); 
    Readln (Fi, R1); 
    For i := 1 to N - 1 do 
       Begin 
         Readln (Fi, x, y); 
         Push (x, Q1[y]); 
         Push (y, Q1[x]); 
       End; 
    Readln (Fi, R2); 
    For i := 1 to N - 1 do 
       Begin 
          Readln (Fi, x, y); 
          Push (x, Q2[y]); 
          Push (y, Q2[x]); 
       End; 
    Close (Fi); 
  End; 

Procedure MakeCode (Root : Integer); 
  Var Q : Arr1p; Var Son : Arr1i; Var Tree : Pnode); 

Procedure InitNumSon (x : Integer); 
  Var p : Pnode; 
  Begin 
    Visit[x] := 1; 
    p := Q[x]; 
    Son[x] := 1; 
    While p <> Nil do 
      Begin 
        If Visit[p^.x] = 0 Then 
          Begin 
             InitNumSon (p^.x); 
             Son[x] := Son[p^.x] + Son[x]; 
          End; 
        p := p^.Next; 
      End; 
  End; 

Procedure Swapi (Var x, y : Integer); 
  Var i : Integer; 
  Begin 
    i := x; x := y; y := i; 
  End; 

Function Kind (r1, r2 : Pnode) : Byte; 
  Begin 
    Kind := 0; 
    While r1 <> Nil do 
      Begin 
        If Son[r1^.x] <> Son[r2^.x] Then 
          Begin 
            If Son[r1^.x] > Son[r2^.x] Then Kind := 1 Else Kind := 2; 
            Exit; 
          End; 
        r1 := r1^.Next; 
        r2 := r2^.Next; 
      End; 
  End; 

Procedure Sort (l, r : Integer); 
  Var i, j : Integer; 
      tr   : Pnode; 
  Begin 
    If l >= r Then Exit; 
    i := l + Random (r - l + 1); 
    tr := Code[1, Order[i]]; 
    i := l; 
    j := r; 
    Repeat 
      While Kind (Code[1, Order[i]], tr) = 1 do i := i + 1; 
      While Kind (Code[1, Order[j]], tr) = 2 do j := j - 1; 
      If i <= j Then 
        Begin 
          Swapi (Order[i], Order[j]); 
           i := i + 1; 
           j := j - 1; 
        End; 
    Until i > j; 
    Sort (i, r); 
    Sort (l, j); 
  End; 

Procedure BuildCode (x : Integer); 
  Var p      : Pnode;
      i, All : Integer; 
  Begin 
    All := 0; 
    Visit[x] := 1; 
    p := Q[x]; 
    While p <> Nil do 
      Begin 
        If Visit[p^.x] = 0 Then BuildCode (p^.x); 
        p := p^.Next; 
      End; 
    Visit[x] := 2; 
    p := Q[x]; 
    While p <> Nil do 
      Begin 
        If Visit[p^.x] = 2 Then 
          Begin 
            Inc (All); 
            Order[All] := p^.x; 
          End; 
        p := p^.Next; 
      End; 
    Sort (1, All); 
    p := Nil; 
    Push (x, p); 
    p^.Next := Code[1, Order[All]]; 
    Code[1, x] := p; 
    For i := All downto 2 do 
    Code[2, Order[i]]^.Next := Code[1, Order[i - 1]]; 
    If All >= 1 Then Code[2, x] := Code[2, Order[1]] Else Code[2, x] := p; 
End; 

Begin 
  Fillchar ( Visit, sizeof (Visit), 0); 
  InitNumSon (root); 
  Fillchar ( Visit, sizeof (Visit), 0); 
  BuildCode (root); 
  Tree := Code[1, Root]; 
End; 

Function Check (R1, R2 : Pnode) : Boolean; 
  Var i : Integer; 
  Begin 
    Check := False; 
    For i := 1 to N do 
      Begin 
        If NSon1[R1^.x] <> Nson2[R2^.x] Then Exit; 
        R1 := R1^.Next; 
        R2 := R2^.Next; 
      End; 
    Check := True; 
  End; 

Procedure Print; 
  Var i      : Integer;
      p1, p2 : Pnode; 
  Begin 
    Assign (Fo, Tfo); Rewrite (Fo); 
    If Check (Tr1, Tr2) Then 
      Begin 
        Writeln (Fo, 'YES'); 
        p1 := Tr1; 
        p2 := Tr2; 
        For i := 1 to N do 
           Begin 
             Order[p1^.x] := p2^.x; 
             p1 := p1^.Next; 
             p2 := p2^.Next; 
           End; 
        For i := 1 to N do 
           Write (Fo, Order[i], ' '); 
           Writeln (Fo); 
      End 
        Else Writeln (Fo, 'NO'); 
    Close (Fo); 
  End; 

Begin 
     Readlist; 
     MakeCode (R1, Q1, Nson1, Tr1); 
     MakeCode (R2, Q2, Nson2, Tr2); 
     Print; 
End. 

Bài 2: 

Cho hai dãy số nguyên {a_n}, {bn} \((1 \le N \le 100000, 1 \le ai, bi \le 8000)\). Hai dãy số gọi là tương thích nếu: 

• nếu vị trí i có hai giá trị ai, bi thì bất kỳ j <> i mà a_i = a_j => b_i = b_j. 
• nếu vị trí i có hai giá trị a_i, b_i thì bất kỳ j <> i mà a_i <> a_j => b_i <> b_j. 

Yêu cầu:   Hãy kiểm tra hai dãy {a_n}, {b_n} có tương thích không? 
Input:   SEQUENCE.IN 

•  Dòng đầu ghi có N 
•  Dòng hai ghi dãy {a_n}. 
•  Dong ba ghi dãy {b_n}. 

Ouput:  SEQUENCE.OUT 

•  Ghi YES nếu tương thích, ghi NO nếu không. 

Lời giải: 

Xây dựng quy tắc mã hoá sau: 

•  Fa (i), Fb(i) = Vị trí xuất hiện trước của a_i, b_i. 
•  {a_n}, b_n} tương thích khi và chỉ khi F_a = F_b với mọi i. 

Const Tfi = 'SEQUENCE.IN'; 
      Tfo = 'SEQUENCE.OUT'; 
      MaxN = 8000; 
Var Fa, Fb     : Array [1..8000] of Longint; 
    N          : Longint; 
    F1, F2, Fo : Text; 

Procedure Print (St : String); 
  Begin 
    Assign (Fo, Tfo); Rewrite (Fo); 
    Writeln (Fo, St); 
    Close (Fo); 
    Close (F1); 
    Close (F2); 
    Halt; 
  End; 

Procedure Main; 
  Var i, x, y : Longint; 
  Begin 
     Assign (F1, Tfi); Reset (F1); 
     Assign (F2, Tfi); Reset (F2); 
     Readln (F1, N); 
     Readln (F2); 
     Readln (F2); 
     For i := 1 to N do 
        Begin 
          Read (F1, x); 
          Read (F2, y); 
          If Fa[x] <> Fb[y] Then Print ('NO'); 
          Fa[x] := i; 
          Fb[y] := i; 
        End; 
     Print ('YES'); 
  End; 
Begin 
  Main; 
End. 

Bài 3: 

Cho hai dãy số {a_n}, {b_m} (1≤ N, M≤1000, 1≤ a_i,b_i ≤ 1000). 
 

Yêu cầu: 

Hãy tìm hai đoạn con liên tiếp của {a_n}{b_m} tương thích có độ dài dài nhất? 

Input: SEQLMAX.IN 

•  Dòng đầu ghi có N, M 
•  Dòng hai ghi dãy {a_n}. 
•  Dòng ba ghi dãy {b_m}. 

Ouput: SEQLMAX.OUT 

•  Ghi Lmax là độ dài lớn nhất tìm được. 

Thuật giải: 

•  Dùng cách mã hoá ở trên và kết hợp quy hoạch động. F[i, j] là độ dài lớn nhất khi hai dãy con đó kết thúc ở i của {a_n} và j của {b_m}. 
•  Nếu \(i-Fa (i) = j - Fb(j)\) thì \(F[i,j] = F[i-1,j-1] + 1\).  Ngược lại: \(F[i,j] = \min (i-Fa (i), \, j-Fb(j), \, F[i-1, j-1] + 1)\). 

Program SEQLMAX; 
Const Tfi = 'SEQLMAX.IN'; 
      Tfo = 'SEQLMAX.OUT'; 
      MaxN = 1001; 
Type Arr1i = Array [0..MaxN] of Integer; 

Var Fa, Fb, Backa, Backb : Arr1i; 
    F                    : Array [1..2] of Arr1i; 
    N, M, lmax           : Integer; 
    Fi, Fo               : Text; 

Procedure Readlist; 
  Var i, x : Integer; 
  Begin 
    Assign (Fi, Tfi); Reset (Fi); 
    Readln (Fi, N, M); 
    For i := 1 to N do 
      Begin 
         Read (Fi, x); 
         Fa[i] := Backa[x]; 
         Backa[x] := i; 
      End; 
    For i := 1 to M do 
      Begin 
        Read (Fi, x); 
        Fb[i] := Backb[x]; 
        Backb[x] := i; 
      End; 
    Close (Fi); 
  End; 


Function Min (x, y, z : Integer) : Integer; 
  Begin 
    If x > y Then x := y; 
    If x > z Then Min := z Else Min := x; 
  End; 


Procedure Dynamic (Var F1, F2 : Arr1i; x : Integer); 
   Var y : Integer; 
   Begin 
     Fillchar ( F2, sizeof (F2), 0); 
     For y := 1 to M do 
        Begin 
          If x - Fa[x] = y - Fb[y] Then F2[y] := F1[y - 1] + 1 Else 
          F2[y] := Min (F1[y - 1] + 1, x - Fa[x], y - Fb[y]); 
          If F2[y] > lmax Then lmax := F2[y]; 
        End; 
   End; 

Procedure Main; 
  Var x : Byte; 
      i : Integer; 
  Begin 
    Readlist; 
    lmax := 0; 
    x := 1; 
    Fillchar ( F, sizeof (F), 0); 
    For i := 1 to N do 
       Begin 
          x := 3 - x; 
          Dynamic (F[3 - x], F[x], i); 
       End; 
  End; 

Begin 
   Assign (Fo, Tfo); Rewrite (Fo); 
   Main; 
   Writeln (Fo, lmax); 
   Close (Fo); 
End.

 

Và các bạn thử làm bài CODE IOI2003 với thuật giải trên. Đây là bài khá hay và khá khó ở IOI 2003, quả thật thật khó ăn 50/100 số điểm bài này, nhưng nếu đưa về thuật giải mã hoá thì hoàn toàn dễ. Bài này, tôi xin chỉ đưa ra code (độ phức tạp là O(N^2)) vì cách quy hoặch động khá giống với bài trên còn hàm mã hoá chỉ khác đôi chút các bạn hãy thử nghĩ xem:
 

Program CODE_; 
Const Tfi = 'CODE.20.IN'; 
      Tfo = 'CODE.OUT'; 
      MaxN = 1001; 
      limit = 1000; 
Type St30 = String[30]; 
     St9 = String[9]; 
     Exp = Record 
       x, y, z : St9;
     End; 
     ReCode = Record 
       x, y, z : Integer; 
     End; 
     Arr1Ex = Array [0..MaxN] of Exp; 
     Arr1code = Array [0..MaxN] of ReCode; 
     Arr1Q = Array [0..3*MaxN] of St9; 
     Arr1i = Array [0..3*MaxN] of Integer; 


Var  C      : Array [1..2] of Arr1Code; 
     Ex     : Array [1..2] of Arr1Ex; 
     Back   : Arr1i; 
     Q      : Array [1..2] of Arr1Q; 
     N, Sod : Array [1..2] of Integer; 
     F      : Array [0..MaxN, 0..MaxN] of Integer; 
     Result : Integer; 
     Fi, Fo : Text; 

Procedure Read_One (Var Ex : Arr1Ex; Var Sod : Integer); 
  Var i  : Integer; 
      St : String; 
  Begin 
    For i := 1 to Sod do 
       With Ex[i] do 
         Begin 
            Readln (Fi, St); 
            While Pos (' ', St) <> 0 do Delete (St, Pos(' ', St), 1); 
            x := Copy (St, 1, Pos ('=', St) - 1); 
            Delete (St, 1, Pos ('=', St)); 
            y := Copy (St, 1, Pos ('+', St) - 1); 
            Delete (St, 1, Pos ('+', St)); 
            z := St; 
         End; 
  End; 

Procedure Readlist; 
  Begin 
    Assign (Fi, Tfi); Reset (Fi); 
    Readln (Fi, N[1], N[2]); 
    Read_One (Ex[1], N[1]); 
    Read_One (Ex[2], N[2]); 
    Close (Fi); 
  End; 

Procedure InitQ (Var Ex : Arr1Ex; Var Q : Arr1Q; Var N : Integer; Var Sod : Integer); 
  Var i : Integer; 
  Begin 
    For i := 1 to N do 
      With Ex[i] do 
        Begin 
          Q[3*i - 2] := x; 
          Q[3*i - 1] := y; 
          Q[3*i ] := z; 
        End; 
    Sod := 3 * N; 
  End; 

Procedure SwapS9 (Var s1, s2 : St9); 
  Var s : St9; 
  Begin 
    s := s1; s1 := s2; s2 := s; 
  End; 

Procedure Sort (l, r : Integer; Var Q : Arr1Q); 
  Var i, j : Integer; 
      d    : St9; 
  Begin 
    If l >= r Then Exit; 
    i := l; 
    j := r; 
    d := Q[l + Random (r - l + 1)]; 
    Repeat 
      While Q[i] < d do i := i + 1; 
      While Q[j] > d do j := j - 1; 
      If i <= j Then 
         Begin 
           SwapS9 (Q[i], Q[j]); 
           i := i + 1; 
           j := j - 1; 
         End; 
    Until i > j; 
    Sort (i, r, Q); 
    Sort (l, j, Q); 
  End; 

Procedure Sort_Del (Var Q : Arr1Q; Var Sod : Integer); 
  Var i, j : Integer; 
  Begin 
    Sort (1, Sod, Q); 
    j := 1; 
    For i := 2 to Sod do 
       If Q[i] <> Q[j] Then 
          Begin 
           Inc (j); 
           Q[j] := Q[i]; 
          End; 
    Sod := j; 
  End; 

Procedure Main_One; 
  Var i : Integer; 
  Begin 
    For i := 1 to 2 do 
      Begin 
        InitQ (Ex[i], Q[i], N[i], Sod[i]); 
        Sort_Del (Q[i], Sod[i]); 
      End; 
  End; 

Function Binary (Cd, Ct : Integer; Var Q : Arr1Q; Var s : St9) : Integer; 
  Var i : Integer; 
  Begin 
    While Cd <= Ct do 
      Begin 
         i := (Cd + Ct) div 2; 
         If Q[i] = s Then 
           Begin 
             Binary := i; 
             Exit; 
           End
        Else 
            If Q[i] > s Then Ct := i - 1 Else Cd := i + 1; 
      End; 
  End; 

Procedure Swapi (Var x, y : Integer); 
  Var i : Integer; 
  Begin 
    i := x; x := y; y := i; 
  End; 

Procedure SwapCode (Var Ex : Arr1Ex; Var Q : Arr1Q; Var C : Arr1Code; Var N, Sod : Integer); 
  Var v1, v2, v3 : Integer; 
      i          : Integer; 
  Begin 
     Fillchar ( Back, sizeof (Back), 0); 
     For i := 1 to N do 
        With Ex[i] do 
          Begin 
            v1 := Binary (1, Sod, Q, x); 
            v2 := Binary (1, Sod, Q, y); 
            v3 := Binary (1, Sod, Q, z); 
            C[i].x := Back[v1]; 
            Back[v1] := 2*i - 1; 
            If Back[v2] > Back[v3] Then Swapi (v2, v3); 
            C[i].y := Back[v2]; 
            Back[v2] := 2*i; 
            C[i].z := Back[v3]; 
            Back[v3] := 2*i; 
            Swapi (C[i].y, C[i].z); 
          End; 
  End; 

Procedure Main_Two; 
  Var i : Integer; 
  Begin 
    For i := 1 to 2 do 
      SwapCode (Ex[i], Q[i], C[i], N[i], Sod[i]); 
  End; 

Function Min (x, y : Integer) : Integer; 
  Begin 
    If x < y Then Min := x Else Min := y; 
  End; 

Function Row (x : Integer) : Integer; 
  Begin 
    If x mod 2 = 0 Then Row := x div 2 Else Row := (x - 1) div 2 + 1; 
  End; 

Function Same (c1, c2 : ReCode; i, j : Integer) : Integer; 
  Var l1, l2, l3 : Integer; 
  Begin 
    If (c1.x mod 2 = c2.x mod 2) and (i - Row (c1.x) = j - Row (c2.x)) Then 
                                                                         l1 := limit 
                       Else l1 := Min (i - Row (c1.x), j - Row (c2.x)); 

    If (c1.y mod 2 = c2.y mod 2) and (i - row (c1.y) = j - row (c2.y)) Then 
                       l2 := limit Else l2 := Min (i - row (c1.y), j - row (c2.y)); 

    If (c1.z mod 2 = c2.z mod 2) and (i - row (c1.z) = j - row (c2.z)) Then 
                       l3 := limit Else l3 := Min (i - row (c1.z), j - row (c2.z)); 

    If l1 > l2 Then l1 := l2; 
    If l1 > l3 Then l1 := l3; 
    If l1 > 0 Then Same := l1 Else Same := 0; 
  End; 

Procedure Main_three; 
  Var i, j : Integer; 
  Begin 
    Fillchar ( F, sizeof (F), 0); 
    Result := 0; 
    For i := 1 to N[1] do 
      For j := 1 to N[2] do 
         Begin 
             F[i, j] := Min (Same (C[1, i], C[2, j], i, j), F[i - 1, j - 1] + 1); 
             If F[i, j] > Result Then Result := F[i, j]; 
         End; 
  End; 

Procedure Print; 
  Begin 
    Assign (Fo, Tfo); Rewrite (Fo); 
    Writeln (Fo, Result); 
    Close (Fo); 
  End; 

Begin 
   Readlist; 
   Main_One; 
   Main_Two; 
   Main_Three; 
   Print; 
End.

Trong toán học, quy nạp là một phương pháp đơn giản nhưng hiệu quả để chứng minh các bài toán. Ở bài viết này tôi xin đưa ra một ứng dụng nhỏ của nó trong việc giải các bài toán tin học:

I. Thuật toán quy nạp: 

Giả sử có bài toán F cần chứng minh đúng với mọi \(n \in N\). Ta chứng minh bài toán đúng bằng cách quy nạp, cần tiến hành các bước sau: 

• n = 1: mệnh đề cần chứng minh đúng. 

• Giả sử n = k: mệnh đề cần chứng minh đúng. 

• n = k + 1: ta cần chứng nó cũng đúng. Vậy theo nguyên lý quy nạp bài toán đúng với mọi N. 

Trong tin học, thuật toán này cũng được áp dụng. Tuy thuật toán đơn giản nhưng nó lại được áp dụng một cách rất linh động và khéo léo trong các bài toán tin. 

II. Phát biểu bài toán tổng quát giải bằng quy nạp: 

Thông thường bài toán giải bằng quy nạp không phải là một bài toán tối ưu hoá. Nó chỉ đơn giản là bài toán cần chỉ ra cách biến đổi theo quy luật cho trước để thu được kết quả mong đợi. Và bài toán đó thường được phát biểu như sau:Cho N đối tượng và một số thao tác biến đổi. Yêu cầu sử dụng các thao tác biến đổi để thu được kết mong đợi. 
Cách làm thông thường: 

• Nếu n = 0; 1: ta luôn có cách biến đổi đúng. 

• Nếu có n > 1 mà ta luôn chỉ ra một cách biến đổi sao cho giản bớt được số đối tượng mà điều kiện bài toán vẫn không thay đổi. 

• Như vậy vì số đối tượng trong một bài toán tin học luôn là hữu hạn nên sau một số hữu hạn bước thì số lượng đối tương bằng 1 hoặc 0. Suy ra bài toán được giải quyết một cách hoàn toàn.

III. Các ví dụ cụ thể: 

P1.  

     Cho N vecto v1, v2, …, vn độ dài nhỏ hơn L cho trước. Cần đặt trước các vecto một dấu cộng hoặc trừ sao cho vecto tổng thu được có độ dài nhỏ hơn căn 2 nhân L.

Input: Segment.In 

•  Dòng đầu ghi số N ( 1 < N ≤ 10,000) và L (0 < L ≤ 15,000.00) 

•  N dòng tiếp theo mỗi dòng ghi một cặp số xi, yi là toạ độ của vecto thứ i. (|xi|, |yi| ≤ 10000). 

Ouput: Segment.out 

•  Dòng thứ nhất ghi YES nó có thể đặt các dấu cộng trừ thoả mãn yêu cầu bài toán, NO trong trường hợp ngược lại. 

•  Nếu là YES dòng thứ hai ghi N kí tự cộng hoặc trừ cần đặt trước các vecto sao cho tổng vecto nhỏ hơn \(\sqrt{2} * L\). 

Thuật giải: 

•  n = 1 bài toán đã đúng. 

•  n = 2 có trường hợp xảy ra với hai vecto: 

  • góc giữa hai vecto nhỏ hơn 90 độ, lấy vecto 1 trừ cho vecto 2 lúc đó ta thu được 1 vecto co độ dài nhỏ hơn \(\sqrt{2} * L\).

  • góc giữa hai vecto lớn hơn hoặc bài một 90 độ, lấy vecto 1 cộng cho vecto 2 lúc đó ta thu được 1 vecto có độ dài nhỏ hơn \(\sqrt{2} * L\). 

•  n ≥ 3 suy ra luôn có 2 vecto mà góc giữa hai phương của vecto nhỏ hơn hoặc 60 bằng độ có hai trường xảy ra: 

  • góc giữa hai vecto đó nhỏ hơn hoặc bằng 60 độ, trừ vecto 1 cho vecto 2 thay hai vecto bằng vecto mới nhận được. 

  • góc giữa hai vecto đó lớn hơn hoặc bằng 120 độ, cộng vecto 1 cho vecto 2 thay hai vecto bằng vecto mới nhận được. Lưu ý sau này nếu trừ vecto mới nhận được phải trừ (đổi dấu) toàn vecto bộ hình thành lên nó, vecto mới nhận được có độ dài nhỏ hơn L, số đoạn thẳng giảm 1. 

Như vậy đây là bài toán luôn có lời giải, độ phức tạp O(N^2) nếu xử lý khéo có thể giản xuống O(n*log(n)). Chương trình mô tả thuật giải: 
 

Procedure Xuly (n: integer //* số đối tượng *//);
  Begin
       If n <= 1 then exit else
       If n = 2 then 
          Begin
               If goc (v1, v2) <= 90 độ Then đổi dấu (v2);
               //* đổi dấu tức là đổi dấu toàn bộ vecto thành phần *//
               Thay hai vecto bằng 1 vecto (v1 + v2);
               //* vecto mới gồm các thành phần của v1 và v2 *//
               //* lúc này v2 nếu cần thiết đã đổi dấu rồi *//
               Exit;
          End 
            else
              Begin
                  lấy 3 vecto bất kỳ;
                  chọn ra được 2 vecto v1, v2 sao cho góc nhỏ giữa phương 2 vec to nhỏ 60;
                  if goc (v1, v2) <= 60 then đổi dấu (v2);
                  Thay hai vecto này bằng (v1 + v2);
              End;
  End;

P2: Utopia (IOI 2002) 

Đất nước Utopia tươi đẹp bị chiến tranh tàn phá. Khi chiến tranh tạm ngừng, đất nước bị chia cắt thành bốn miền bởi một đường kinh tuyến (đường theo hướng Bắc-Nam) và một đường vĩ tuyến (đường theo hướng Đông-Tây). Giao điểm của hai đường này xem như điểm (0, 0). Tất cả các miền này đều muốn mang tên Utopia, theo thời gian các miền này được gọi là Utopia 1 (phía Đông Bắc), Utopia 2 (phía Tây Bắc), Utopia 3 (phía Tây Nam), Utopia 4 (phía Đông Nam). Một điểm trong bất kỳ miền nào cũng được xác định bởi khoảng cách theo hướng Đông và khoảng cách theo hướng Bắc của nó so với điểm (0, 0). Bộ hai khoảng cách này được gọi là toạ độ của điểm. Các thành phần của toạ độ có thể là số âm; do đó một điểm miền Utopia 2 có toạ độ (âm, dương), một điểm miền Utopia 3 có toạ độ (âm, âm), một điểm miền Utopia 4 có toạ độ (dương, âm), một điểm miền Utopia 1 có toạ độ (dương, dương) (Giống như các góc phần tư trong hệ toạ độ đề các). 
Một vấn đề là các công dân không được phép đi qua biên giới giữa các miền. May thay, một số thí sinh tham dự IOI của Utopia sáng chế ra một loại máy an toàn để vận chuyển từ xa. Máy này cần các số mã, mỗi số mã chỉ có thể được dùng một lần. Bây giờ, nhóm thí sinh tham dự và bạn phải hướng dẫn máy vận chuyển từ xa xuất phát từ vị trí ban đầu (0, 0) đến các miền của Utopia theo một trình tự cho trước. Khi bạn nhận được một dãy N số hiệu miền mà theo trình tự đó máy vận chuyển từ xa phải hạ cánh, với mỗi miền, bạn không cần phải quan tâm đến việc hạ cánh tại điểm nào của miền đó miễn là điểm đó thuộc miền yêu cầu. Người ta có thể yêu cầu máy hạ cánh liên tiếp hai lần hay nhiều lần hơn ở cùng một miền. Sau khi rời khỏi điểm ban đầu (0, 0), bạn không được hạ cánh trên các đường biên giới. 
Bạn sẽ nhận được input là một dãy 2N số mã và phải viết chúng thành một dãy gồm N cặp mã, sau khi đặt một dấu + hoặc một dấu - thích hợp trước mỗi số. Nếu hiện tại bạn ở điểm (x,y) và sử dụng cặp mã số (+u,-v), bạn sẽ được chuyển tới điểm (x+u,y-v). Bạn có 2N số và bạn có thể sử dụng các số này theo thứ tự bạn muốn, mỗi số kèm theo một dấu + hoặc một dấu -. 
Giả sử bạn có các số mã 7, 5, 6, 1, 3, 2, 4, 8 và phải hướng dẫn máy vận chuyển từ xa lần lượt đến các miền thuộc dãy miền 4, 1, 2, 1. Dãy các cặp mã (+7, -1), (-5, +2), (-4, +3), (+8, +6) đáp ứng yêu cầu này vì nó đưa bạn từ (0,0) lần lượt đến các vị trí (7, -1), (2, 1), (-2, 4) và (6, 10). Những điểm này nằm tương ứng ở Utopia 4, Utopia 1, Utopia 2 và Utopia 1.

Nhiệm vụ:

Cho 2N số mã khác nhau và một dãy N số hiệu miền là dãy các miền mà máy vận chuyển từ xa phải lần lượt hạ cánh. Hãy xây dựng một dãy các cặp mã từ các số đã cho để hướng dẫn máy vận chuyển từ xa lần lượt đi đến các miền thuộc dãy đã cho. 

Input 

Chương trình của bạn phải đọc từ input chuẩn. Dòng đầu gồm một số nguyên dương N (1 ≤ N ≤ 10000). Dòng thứ hai gồm 2N số mã nguyên khác nhau, tất cả đều là các số nguyên dương không lớn hơn 100000. Dòng cuối cùng gồm một dãy N số hiệu miền, mỗi một trong các số đó là 1, 2, 3 hoặc 4. Hai số liên tiếp trên một dòng cách nhau đúng một dấu trống. 

Output 

Chương trình của bạn phải viết ra output chuẩn. Ouput gồm N dòng, mỗi dòng chứa một cặp số mã mà trước mỗi số có dấu + hoặc dấu -. Đó là các cặp mã sẽ hướng dẫn cho máy vận chuyển đến dãy miền đã cho. Chú ý rằng không được có dấu trống sau dấu + hoặc dấu - nhưng phải có một dấu trống sau số mã thứ nhất.Nếu có nhiều lời giải, chương trình của bạn có thể đưa ra một lời giải bất kỳ trong số đó. Nếu không có lời giải, chương trình của bạn phải đưa ra một số 0 duy nhất. 

Thuật giải: 

Đây cũng là bài toàn luôn giải được để giải bài toán trên ta cần giải bài toán nhỏ sau:Cho một gồm N số nguyên dương khác nhau a1 < a2 < … < an. Cần sắp xếp lại và thêm các dấu vào các số ai sao cho tổng các số từ 1 đến vị trí i là dương hoặc âm biết trước: 

Ví dụ: 

Dãy 3 số: 1 2 3 
Dấu cần xây dựng: + - + 
Một cách thêm dấu và sắp xếp: +1 -2 + 3 

Bổ đề: 

Nếu dãy có dãy {ai} dương tăng và một chuỗi dấu cần biến đổi thì ta luôn có cách thêm dấu và thay đổi vị trí sao cho tổng cách số từ 1 đến i mang đấu của chuỗi dấu biết trước. 

Chứng minh: 

• số an mang dấu cuối cùng của chuỗi trên, các số còn lại đan dấu. (điều kiện về dấu để luôn xây được dãy) Ví dụ: {ai} = {1, 5, 10}; S = ‘++-‘; suy ra dãy {ai} được đánh dấu như sau: -1, +5, -10; 

• nhận xét rằng: tổng của n số trên cuối cùng sẽ mang dấu của S[n] 

• với n = 1 ta nhận được dãy cần tìm. 

• Giả sử n = k ta xây dựng được chuỗi như trên. 

• n = k + 1 chia hai trường hợp: 

  • s[n-1] cùng dấu s[n]: đặt a[1] vào vị trí cuối cùng và lấy phần tử a[1] và s[n] ra khỏi dãy, nhưng còn là (n - 1) số và (n-1) dấu và dấu cuối cùng với số cuối, dãy đan dấu (vẫn thoả mãn điều kiện về dấu) 

  • s[n - 1] và s[n] khác dấu: đặt a[n] vào vị trí cuối cùng và lấy phần tử a[n] và s[n] ra khỏi dãy, nhưng còn là (n - 1) số và (n-1) dấu và dấu cuối cùng với số cuối, dãy đan dấu. Theo giả thiết quy nạp thì dãy còn lại luôn xây dựng được. 

Chương trình: 
 

Procedure Xuly (Var a, dau, q: array [1…10000] of integer; n, cd, ct : integer);
//*ta đang xử lý dãy các số từ a[cd] đến a[ct] có dấu từ dấu[1] đến dấu[n] *//
Begin
   If n <= 1 then exit;
   If dau[n - 1] = dau[n] then
       Begin
          q[n] := a[cd];
          Xuly (a, dau, q, n - 1, cd + 1, ct);
       End 
         else
            Begin
               q[n] := a[ct];
               Xuly (a, dau, q, n - 1, cd, ct - 1);
            End;
End;
//* mảng q thu được là kết quả cần tìm*// 

Ở bài toán trên các dấu tọa độ x, y là đã xác định: Chia dãy 2N phần tử khác nhau thành hai gồm N phần tử làm hoành độ và tung độ, sau đó sắp tăng. Tiến hành thuật giải trên ta thu được hai dãy toạ độ thoả mãn điều kiện về dấu, đó cũng chính là dãy toạ độ cần tìm.

P3: (Bài tập tự giải) 2N point (POI) 

Cho 2N diểm trên mặt phẳng gồm N diểm màu xanh và N điểm màu trắng sao cho không có ba điểm nào thẳng hàng. Hãy tìm N đoạn thẳng mà mỗi đoạn thẳng nối giữa một điểm màu xanh và một điểm màu trắng và các doạn nay không cắt nhau. 

Input: 2Npoint.Int 

•  Dòng dầu ghi số N. (1 ≤ N ≤ 5000) 

•  N dòng tiếp theo mỗi dòng ghi toạ độ xi, yi của điểm màu xanh \((|x_i|, |y_i| ≤ 10,000)\).

•  N dòng tiếp theo mỗi dòng ghi toạ độ xi, yi của điểm màu trắng \((|x_i|, |y_i| ≤ 10,000)\). 

Output: 2Npoint.Out 

•  Gồm N dòng mỗi dòng ghi hai số a, b để chỉ điểm màu xanh thứ a, nối với điểm màu trắng thứ b. 

Bạn có thể đọc bài viết trong Thư viện mới.

Các trò chơi đối kháng giữa hai người đã được hình thành từ lâu. Và những người chơi luôn cố gắng tìm mọi cách để mình giành được phần thắng. Và bạn có biết rằng các trò chơi đã được đoán trước là thắng, thua hay hoà không? Ý tôi muốn nói rằng, nếu một trò chơi cho trước vị trí ban đầu thì kết quả tốt nhất mà người chơi đầu tiên đạt được đã được biết từ trước(ở đây tôi giả thiết cả hai người chơi đều chơi tối ưu). Vấn đề là các trò chơi thường quá phức tạp lên không có một ai có thể đảm bảo rằng mọi nước đi của mình là tối ưu. Do vậy cho đến nay, chỉ một số lượng nhỏ bài toán đó đã được giải quyết. Và trong bài viết này tôi xin giới thiệu một cách khá đầy đủ về trò chới đối kháng hai người. Bài toán đó được phát biểu tổng quát dưới dạng đồ thị như sau:

Cho đồ thị có hướng G=(V,E) (Đồ thị G có tập đỉnh V, tập cạnh là E). Với mỗi đỉnh \(v \in V\), ta định nghĩa \(E(v) = \{ u \, | \, (u,v) \in E \} \)

Một trò chơi hai người được định nghĩa là một đồ thị có hướng G = (V, E) trong đó mỗi trạng thái chơi tương ứng với một đỉnh của đồ thị, hàm E(v) là qui tẵc chơi tức là E(v) chứa các đỉnh hay trạng thái chơi mà từ v có thể đi đến. Hai người luân phiên nhau đi , ở thế chơi u người chơi chỉ có thể đi sao cho nước v nhận được thoả mãn \(v \in E(u)\). Trò chơi kết thúc khi đến lượt đấu mà không thể đi tiếp được nữa. (Thông thường thì người không thể đi tiếp là người thua cuộc). 

Tôi xin chia bài toán này thành hai loại bài toán: loại thứ nhất là, mỗi trạng thái chơi chỉ có một đối tượng mỗi đối tượng là một đỉnh của đồ thị. Loại thứ hai là mỗi trạng thái chơi có nhiều đối tượng. (Sự khác nhau căn bản các bạn sẽ được rõ ở phần sau). 

I. Loại thứ nhất: 

P1. Xét bài toán cụ thể - GAME 

Một trò chơi đối kháng giữa hai người A và B diễn ra như sau: Hai người luôn phiên nhau điều khiển một con tốt theo một số con cho trước. Một người có thể di chuyển con tốt từ vị trí u đến v nếu có một đường nối trực tiếp có  hướng từ u đến v. Trò chơi kết thúc không thể tiếp tục di chuyển. Người không thể tiếp tục đi là người thua cuộc. Hỏi nếu cho trước vị trí ban đầu và danh sách các đường nối hỏi người đi trước thắng hay ngươì đi sau thắng  hay hoà? Giả hai người này rất thông minh các bước đi của họ là tối ưu (tức học không bao giờ đi các nước không có loại cho mình). 
Input: Game.In 

•  Dòng đầu ghi số N là số vị trí con tốt có thể đừng, và số M là số đường đi (có hướng) mà con tốt có thể đi (1≤ N ≤ 200, 1 ≤ M ≤ N*(N-1)). 
•  Dòng thứ hai ghi u là trạng thái bắt đầu. 
•  M dòng tiếp theo mỗi dòng ghi hai số u, v mô tả một đường đi từ u đến v. 

Output: Game.Out 

• Ghi một số duy nhất 1, 2, hoặc 0. 1 nghĩa là người 1 thắng, 2 là người hai thắng, 0 là hoà. 

Nhận xét:

•  Những vị trí không có đường ra thì chắc chắn sẽ thua. 
•  Những vị trí nào có một đường ra nối với vị trí chắc chắn thua thì chắc chắn thắng. 
•  Những vị trí nào tất đường ra nối với các vị trí chắc chắn thắng thì chắc chắn thua. 
•  Những vị trí nào mà trạng thái thắng thua không thể xác định thì là vị trí hoà.- Bài toán có trạng thái hoà: VD: có các đường nối 1 → 2, 2 → 3, 3 → 1, 1 → 4, 4 → 5.Các vị trí 1,2,3 sẽ hòa, 5 thua, 4 thắng. 

Thuật toán: 

• Lúc đầu coi tất cả các vị trí v đều hoà gán giá trị đỉnh F[v] = 0. Tìm các vị trí không có đường ra thì gán lại F[v] = 2 (tức là nếu người chơi ở vị trí này sẽ thua). - Khi thay trạng thái một vị trí từ hoà sang thắng hoặc thua thì kiểm tra các vị trí có đường đi đến nó: Những vị trí u nào có một đường ra nối với vị trí v chắc chắn thua (F[v] = 2) sẽ thì chắc chắn thắng (thay F[u] = 1); Những vị trí u nào tất đường ra nối với các vị trí v (F[v] = 1) chắc chắn thắng thì chắc chắn thua (thay F[u] = 2). 
• Quá trình này ngừng khi không có sự chuyển trạng nào nữa. 

Chương trình mô tả thuật toán: 

Procedure gan_nhan (u: byte); 
  Var td, v : byte; 
  Begin 
      td := 0; 
      If Noi_dinh_thuău) then td := 1 Else 
      If Noi_toan_dinh_thang_hoac_khong_co_dinh_ra (u) Then td := 2; 
      F[u] := td; 
      If td <> 0 Then 
           For v := 1 to N do 
             If F[v] = 0 Then 
                  If C[v, u] Then gan_nhan (td); 
  End; 

Procedure Main; 
  Var u : Integer; 
  Begin 
    Fillchar (F, sizeof (F), 0);
    For u := 1 to N do 
        If Khong_Co_Canh_Ra (u) Then Gan_nhan(u); 
  End; 

P2. (Bài tập tự giải) LGAME (BOI 2002) 

Cho một bảng kích thước 4*4 ô vuông, trên đó đặt hai thanh thước thợ hình L kích thước 4 ô vuông và hai hình tròn như hình vẽ, các hình này nằm trên bảng và không được đè lên nhau. Hình kẻ ca rô là của người chơi A, hình kẻ sọc của người chơi B. Hai người sẽ chơi luôn phiên, tại mỗi nước đi, một người sẽ phải nhấc thanh hình L của mình lên, xoay, lật tuỳ ít và di chuyển đến vị trí mới (khác ít nhất một ô so với vị trí ban đầu), như vậy hình đầu tiên có hai cách di chuyển. Và người chơi có thể thực hiện thêm một bước đi không bắt buộc là di chuyên một ô tròn đến một ô mới. 
Trò chơi kết thúc khi không thể di chuyển được nữa, người không thể di chuyển được sẽ thua cuộc. Tuy nhiên, trò chơi vẫn có thể hoà vì trong trạng đó cả hai người đều không muốn thua.

Yêu cầu: Cho một trạng thái trò chơi, hỏi trò chơi đó sẽ kết thúc như thế, (hoà, A thắng hay B thắng, ở đây A là người đi trước) 
Input: Lgame.In 

•  Gồm 4 dòng mỗi dòng ghi 4 kí tự, ‘.’ thể hiện ô trống(có 6 ô), ‘x’ là ô chứa miếng hình tròn (2 ô), ‘#’ biều thị ô bị miếng hình L của người chơi A đặt lên (có 4 ô), còn lại bốn ô biểu thị ô bị miếng hình L của người chơi B đặt lên. 

Output:Lgame.out 

•  Có ba trường hợp:  
  • A thắng: ghi trạng thái sau khi A đi nước đI đầu tiên dẫn đến trạng tháI thắng đó. 
  • A thua: ghi ra xâu “No winning move Losing”. 
  • Hoà: ghi ra xâu “No winning Draw”.

Gợi ý:  Có không quá 18 000 trạng thái, giải bằng Freepascal. 
Bổ sung: Đôi khi không phải lúc nào cũng có thể lưu được tất cả các trạng thái vì có một số bài toán có số trạng thái rất lớn. Vì vậy, thay vì tính trạng thái thắng thua hiện thời ta thay bằng trạng thái tương đương có cùng tính chất thắng thua. 
Khái niệm: trạng thái A được gọi là tương đương với B khí và chỉ khi A và B có cùng thắng, cùng thua hoặc cùng hoà. 
Để hiểu sâu hơn ta xét một bài toán cụ thể:

P3. Stones (ACM) 

Một trò chơi bốc sỏi diễn ra trên một bảng ngang kích thước 1*N ô vuông. Trên một số ô có đặt một số viên sỏi. Tại một bước đi người cầm một viên sỏi ở một ô và di chuyển viên sỏi sang bên trái một hoặc hai ô với điều kiện là ô di chuyển tới phải không có sỏi và đường di chuyển không được qua ô có sỏi. Người nào không di chuyển được sẽ là người thua cuộc. Cho trước trạng thái ban đầu hỏi người di trước có bao nhiêu nước đi đầu tiên mà người thứ luôn thua với giả thiết cả hai người đều chơi tối ưu. 
Input: Stones.in 

• Dòng đầu ghi số N(1 ≤ N ≤ 50). 
• Dòng thứ hai ghi một xâu gồm N kí tự thể hiện trạng thái lúc bắt đầu trò chơi, ‘.’ thể hiện ô trống, ‘X’ thể hiện có sỏi (số viên sỏi không vượt quá 10). 

Output: Stones.out 

• Ghi một số là số đi mà có thể thắng.

Nhận xét:

Nếu coi mỗi trạng thái là một đỉnh đồ thị rõ ràng bài toán theo lý thuyết có thể tính được kết quả cần tính. Nhưng trên thực tế số trạng thái rất lớn(có thể lên đến Tổ hợp chập 10 của 50 phần tư). Như vậy bài toán không thể lập trình được vì thiếu bộ nhớ và tốc độ tính toán rất chập. - Vì vậy người ta đã nghĩ ra một cách giảm số lượng trạng thái đang xét xuống. Đầu tiên ta thấy trạng thái của người chơi được đặc trưng bởi tập có thứ tự ở đằng trước các ô tự do của mỗi viên sỏi Ví dụ: xâu “...XX.X” ↔ {3, 0, 1}. Nếu cứ để như vậy thì không giải quyết được và thay vì xét sự thắng thua của dãy đó ta xét sự thắng thua của dãy khi lấy đồng dư 3 của tất cả các phần tử trong dãy: {3,0,1} ↔ {0,0,1}, vì ta có thể chứng minh được hai dãy này là tương. Chứng minh: 
Gọi dãy ban đầu là A, dãy sau khi giảm ước là B=f(A) (f là hàm rút gọn). 
Vì B là dãy giảm ước của A nên với mọi B đi một nước đến B’ thì Acũng đi một nước đến A’ (cùng vị trí và số ô) sao cho f(A’) = f(B’). (I) 
Ví dụ: B{0,0,1} sau một nước đi vị trí 3 với số ô đi bằng 1 đến B’{0,0,0} thì A cũng đi tại 3 với số ô bằng 1 đến A’{3,0,0}. Lúc đó ta có: f(A’) = f(B’) = {0,0,0}. 
Vì mọi bước chơi của đối thủ hòng có lợi cho mình. Nếu người chơi thứ nhất thực hiện một nước đi từ A đến A’ hòng thay đổi sự thua ->thắng (vốn theo lý thuyết là xác định), tức f(A) thua, f(A’) thua mà B = f(A), suy ra B không đi được đến B’ (vì B=f(A) suy ra B thua, B’ cũng thua) suy ra người chơi đã thực hiện trên một ô có số ô tự do ở đằng trước lớn hơn bằng 3, suy tiếp ra người thức hai có thể đi tiếp một nước trên cùng ô đấy với số ô bằng (3 - số ô người một đã đi). Suy ra người 1 vẫn ổ vị trí f(A’’) thua. (II) 
(I)(II) => người chơi trạng thái cuối. 

Thuật giải: 

• Mỗi trạng thái chơi hay mỗi đỉnh của đồ thị là một số viết trong hệ cơ số 3, sau mỗi một bước đi thì chơi đến một trạng tháI chơi khác, ta làm động tác rút gọn lấy modun 3 thì lại được một trạng thái khác được biểu diễn dưới dạng cơ số ba khác. Ta tính sự thắng thua trên đồ thị này. Ví dụ: {0, 0, 1} chỉ đi đến {0,0,0}; {1,2,1} nếu ta đi viên sỏi thứ hai sang trái hai ô ta đến trạng thái {1,0,3} ↔ {1,0,0}.(lưu ý: nếu biểu diển theo này ta chỉ đi đến trạng thái có giá trị cơ số 3 nhỏ hơn, trong đó vị trí có giá trị lớn nhất nằm bên phải}. 
• Nếu một trạng thái chơi mà thắng khi chỉ khi trạng tương đương là thắng. 

Chương trình mô tả 

Var ketqua : array [0..59060] of byte; 

Procedure Thang_thua (x : longint); {0<= x <=59049 = 3^10} 
   Var thang, i : byte; 
       a, b     : array [0..10] of byte; 
       y        : longint; 
   Begin 
      Doi_x_sang_co_so_3 (x, a); 
      //* x=16 => a[0]=3(số chữ số trong hệ cơ số 3 của x); 
      //*a[1] = 1, a[2]=2, a[3]=1; 
      For i := 1 to a[0] do 
          For ci:= 1 to 2 do 
            If (a[i] >= ci) then 
              Begin 
                 Thuc_hien_buoc_di_o_vi_tri_i(i, ci, a, b); 
                 //* có thể có tới hai cách, ci =1 hoặc 2 
                 //* ví dụ: i=2, ci=2, a={3, 1, 2, 1} 
                 //* b={3,1,0,3} 
                 Rut_gon_b(b); 
                 //*b={3,1,0,0} 
                 Doi_b_sang_y(b); 
                 //* đổi sang cơ số 10 
                 //* y=9 
                 If (ketqua[y] = 0) then 
                       Begin 
                          Ketqua[x] := 1; 
                          Exit; 
                       End; 
              End; 
      Ketqua[x] := 0; 
   End; 

Procedure Chuong_trinh; 
    Var a, b  : array [0..10] of byte; 
        Xau   : string[50]; 
        x     : longint; 
        dem   : byte; 
    Begin 
       Dem := 0; 
       Nhap_N_va_xau( N, Xau); 
       Doi_xau_sang_co_so_3(Xau, a); 
       Vong lap: Di_cac_buoc_di_thu_(a, b) 
       Doi_b_sang_x (b, x); 
       If ketqua[x] = 0 then inc (dem); 
       Ket_thuc_vong_lap; 
       Print (dem); 
    End; 

P4. Trò chơi chuyển đá (đề thi thử ioicamp lần 2)

Nguồn: Topcoder – Sưu tầm: Nguyễn Văn Hiếu 
Vào một ngày đẹp trời, A nghĩ ra một trò chơi và rủ B cùng tham gia. Có n ô, mỗi ô chứa một số viên đá. Các ô được đánh số từ 0 đến n-1. Để thực hiện một nước đi, A/B chọn 3 ô với chỉ số i, j, k thoả mãn i < j, j ≤ k và ô i chứa ít nhất 1 viên đá, sau đó bỏ đi 1 viên đá ở ô i đồng thời thêm hai viên đá vào ô j và ô k (mỗi ô một viên). Chú ý là j có thể bằng k, và sau mỗi bước tổng số viên đá luôn tăng lên 1. Ai không thể thực hiện nước đi coi như bị thua. A đi trước. Nhiệm vụ của bạn là xác định xem A có thể chiến thắng hay không? (giả sử B chơi tối ưu). Nếu có thể hãy in ra 3 số i, j, k mô tả nước đi đầu tiên của A. Nếu có nhiều kết quả hãy in ra kết quả có i nhỏ nhất, nếu vẫn có hơn một kết quả chọn kết quả có j nhỏ nhất, nếu vẫn có hơn một kết quả chọn kết quả có k nhỏ nhất. 
Input: STONES.INP 

•  Dòng đầu gồm số nguyên n là số ô. 
•  Dòng thứ hai gồm n số, số thứ i thể hiện số viên đá ở ô i. 

Output: STONES.OUT 

•  Nếu A thắng thì in ra 3 số i, j, k trên một dòng duy nhất. 
•  Nếu A thua thì in ra một số –1 duy nhất.

Giới hạn: 

• Kích thước: 

            + 1 ≤ n ≤ 15 
              + Số viên đá ở một ô không vượt quá 1000. 

• Thời gian: 1 s/test 
• Bộ nhớ: 1 MB

Gợi ý: Trạng tương đương là trạng thái rút lấy modun cho 2, như vậy có nhiều nhất là 2^15 trạng thái. 
Tóm lại: Tư tưởng của lại trò chơi này rất đơn giản, bước đi tốt nhất của mình là bước đi dồn đối thủ đến tình trạng xấu nhất hay có lợi cho mình nhất: F(v) = max{G(v) - F(u); u | (v,u) Î E}. Trong đó: F(v) là giá trị tốt nhất tại đỉnh v của người đi từ đỉnh đấy, G(v) là giả trị của đỉnh v.