Skip to content
Narrow screen resolution Wide screen resolution Auto adjust screen size Increase font size Decrease font size Default font size default color grey color
         
 | 
VNOI - Olympic tin học Việt Nam

Điểm tin VOJ

Số thành viên:6040
Số bài tập:1001
Số bài nộp:722923
Bài nộp hôm nay:0

Top 10 thành viên xuất sắc

HạngThành viênĐiểm
1mr_invincible587.9
2white_cobra418.6
3hieult403.4
4phaleq384.0
5vodanh9x368.2
6con_nha_ngheo352.0
7flash_mt350.2
8darksabers349.8
9yenthanh132345.3
10rockman9x_94343.1
Frogs - Con ếch In E-mail
(4 votes)
Người viết: Ngô Minh Đức   
21/04/2008

Con ếch

Ở Hàn Quốc, có truyền thuyết về tác hại của cheonggaeguri, Một loài ếch nhỏ. Đó là một điều đáng chú ý vì các con ếch nhảy qua ruộng lúa của bạn vào ban đêm và làm đổ gục các cây lúa. Buổi sáng sau khi ghi nhận những cây lúa bị đổ, bạn muốn biết đường đi của con ếch gây nên thảm hoạ lớn nhất. Một con ếch luôn nhảy qua ruộng lúa theo đường thẳng và mọi bước nhảy có cùng độ dài. Các con ếch khác nhau có thể nhảy với các bước có độ dài khác nhau và theo các hướng khác nhau (xem hình sau)

Ruộng lúa của bạn có các cây lúa ở trên các giao điểm của một lưới ô vuông như trong Hình 1 và các con ếch nhảy qua ruộng lúa bắt đầu từ bên ngoài ở một phía và kết thúc ở bên ngoài phía khác nhau trong Hình 2.

Có thể có nhiều con ếch nhảy qua ruộng lúa bằng cách nhay từ cây lúa này đến cây lúa khác. Mỗi bước nhảy đến một cây lúa và làm đổ gục cây lúa đó nhau trong Hình 3. Chú ý rằng một số cây có thể bị hơn một con ếch nhảy đến trong ban đêm. Tất nhiên, sáng ra bạn không thể nhìn thấy các đường đi của các con ếch và cũng không nhìn thấy được các vết nhảy của các con ếch bên ngoài ruộng lúa; với tình huống trong Hình 3, những gì bạn nhìn thấy được chỉ ra trong Hình 4:

Từ hình 4, ta có thể khôi phục mọi đường đi có thể có mà các con ếch đã nhảy qua ruộng lúa. Bạn chỉ quan tâm đến các con ếch làm đổ gục ít nhất ba cây lúa trong ruộng. Một đường đi của con ếch như vậy được gọi là một đường ếch. Chẳng hạn ba đường đi trong Hình 3 là các đường ếch (cũng có thể còn có các đường ếch khác). Đường thẳng đứng ở cột 1 có thể là một đường đi với bước nhảy độ dài 4 nhưng do chỉ có 2 cây lúa bị đổ nên không là đường ếch. Đường đi chéo gồm các cây lúa trên dòng 2 cột 3, dòng 3 cột 4 và dòng 6 cột 7 có ba cây lúa bị dổ nhưng các bước nhảy không cùng độ dài nên cũng không là một đường ếch. Ta cũng cần chú ý rằng trên đường thẳng chứa một đường ếch có thể có các cây lúa đổ khác nhưng không do con ếch đó gây nên (cây ở dòng 2, cột 6 trên đường nằm ngang đi qua dòng 2 trong Hình 4) và ngoài ra có một số cây đổ có thể không thuộc đường ếch nào.

Nhiệm vụ của bạn là viết một chương trình xác định số lượng nhiều nhất các cây lúa đổ trên một đường ếch (cực đại lấy theo mọi đường ếch có thể có). Trong Hình 4 đáp số là 7 nhận được từ đường ếch qua dòng 6.

INPUT

Chương trình của bạn cần đọc từ input chuẩn. Dòng thứ nhất gồm hai số nguyên R và C, tương ứng là số dòng và số cột trong ruộng lúa của bạn, 1 < R,C > 5000. Dòng thứ hai gồm duy nhất số nguyên N, là số cây lúa bị đổ, 3 < N > 5000. Mỗi một trong Ndòng còn lại chứa hai số nguyên tương ứng là chỉ số dòng và chỉ số cột của một cây lúa bị đổ (1 < chi? so^' do`ng < R), (1 < chỉ số cột < C) hai số này cách nhau một dấu trống. Mỗi cây lúa đổ chỉ liệt kê ra một lần.

OUTPUT

Chương trình của bạn cần viết ra output chuẩn. Output gồm một dòng với một số nguyên duy nhất, đó là số cây lúa đổ của một đường ếch gây thiệt hại lớn nhất nếu có ít nhất một đường ếch, nếu không có đường ếch nào, là số 0.

Ví dụ về input và output

Example 1: input output

(Ví dụ theo Hình 4)

Example 2: input (Ví dụ theo Hình 5)

output

Việc cho điểm

Nếu chương trình của bạn cho đáp số đúng với một test trong giới hạn thời gian thì bạn được toàn bộ điểm của test đó, nếu không, bạn được 0 điểm
 
< Trước   Tiếp >