Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

VMCROSS - Crossword

Hiện tại, bài tập này đã có trên online judge chính thức của VNOI, bạn có thể truy cập ở đây: https://oj.vnoi.info/problem/vmcross


Trò chơi ô chữ là một trong những trò chơi lâu đời nhất được con người phát minh ra. Ở trò chơi này, bạn được cho một bảng chữ nhật kích thước N*M (N hàng M cột), được chia thành cách hình vuông nhỏ kích thước 1*1. Ô ở hàng u, cột v được ký hiệu là ô (u, v). Có một số ô trống tạo thành các từ hàng ngang và hàng dọc. Bạn được cho một số gợi ý, và cần phải điền các chữ cái vào bảng dựa theo những gợi ý được cho.

Hình minh họa

Ở trong hình minh họa, bạn có một bảng kích thước 15*15 (M = N = 15). Bạn cần điền những chữ cái vào các ô màu trắng. Chú ý rằng mỗi ô trắng thuộc ít nhất một từ hàng ngang hoặc một từ hàng dọc. Mỗi gợi ý có dạng:

  • Từ hàng ngang bắt đầu từ ô đánh số 1 là tên 1 quốc gia
  • Từ hàng dọc bắt đầu từ ô đánh số 2 là tên một thành phố
  • ...

Một vài chú ý:

  • Ô 23 là điểm bắt đầu của 2 từ: một từ nằm dọc, 1 từ nằm ngang. Trong bài này, một ô có thể là điểm bắt đầu của 2 từ (2 từ đó phải có hướng khác nhau).
  • Từ ngắn nhất bắt đầu từ ô 1, và có độ dài 4. Trong bài này, từ ngắn nhất hợp lệ có thể xuất hiện trên bảng cũng có độ dài là 4.

Trong bài toán này, nhiệm vụ của bạn là tạo ra một bảng ô chữ. Bạn được cho một bảng trống kích thước N*M và một danh sách gồm K từ (các từ đôi một khác nhau). Nhiệm vụ của bạn là điền các từ này lên bảng sao cho:

  • Mỗi từ được điền vào một dãy các ô liên tiếp theo chiều ngang từ trái sang phải hoặc chiều dọc từ trên xuống dưới.
  • Các từ có cùng hướng với nhau và nằm trên cùng một hàng (hoặc cùng một cột) không được có ô chung hay chạm nhau (2 ô được gọi là chạm nhau khi có chung một cạnh).
  • Nếu một từ hàng ngang và một từ hàng dọc giao nhau, thì ô giao nhau phải có cùng chữ cái.
  • Mỗi từ trong danh sách chỉ được điền đúng một lần lên bảng.

Input

Dòng đầu tiên chứa 3 số tự nhiên N, M, K. (1 ≤ N, M ≤ 50; 1 ≤ K ≤ 1000)

K dòng tiếp theo, mỗi dòng chứa một từ (4  độ dài từ  30). Các từ chỉ gồm các chữ cái in thường từ a tới z.

Output

Dòng đầu tiên ghi ra một số tự nhiên X là số từ điền được vào bảng.

X dòng sau, mỗi dòng ghi 4 số tự nhiên: id u v t với ý nghĩa: từ thứ id được điền vào vị trí (u, v) trên bảng. Nếu t=0 thì từ được điền từ trái sang phải, nếu t=1 thì từ được điền từ trên xuống dưới. Chú ý rằng các từ của bạn phải được điền hoàn toàn vào bên trong bảng (không chữ cái nào được điền ra ngoài bảng).

Cách tính điểm

  • Với mỗi test, nếu output của bạn không hợp lệ, bạn được 0 điểm. Nếu output hợp lệ:
    • Gọi X là số từ nằm ngang mà bạn điền được lên bảng.
    • Gọi Y là số từ nằm dọc mà bạn điền được lên bảng.
    • Gọi Z là số ô thuộc 2 từ (1 từ nằm ngang và 1 từ nằm dọc).
    • Gọi T là số ô thuộc ít nhất 1 từ.
    • Điểm của bạn là (X * Y + Z^1.5 + T) / (M * N).
  • Vì đây là bài challenge, nên điểm chung cuộc của bạn trong kỳ thi VM14 được tính theo công thức:
    • Giả sử bạn đứng thứ i trong bảng xếp hạng của bài (nghĩa là có i-1 người điểm cao hơn bạn).
    • Điểm mà bạn nhận được là
      max(log(100.0 / (i+1)) * (100.0 / log(100.0 / 2)), 0)
      với log là log cơ số e.
  • Bài này gồm 20 test. Trong quá trình thi, bài của bạn sẽ được chấm với 10 test.

Example

Input:
4 4 4
abcd
xyzt
buyv
dwtz

Output:
4
1 1 1 0
2 3 1 0
3 1 2 1
4 1 4 1

Với output này:

  • X = 2
  • Y = 2
  • Z = 4
  • T = 12

Được gửi lên bởi:VOJ Team
Ngày:2014-08-27
Thời gian chạy:1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ASM64 GOSU PERL6 PYPY RUST SED

hide comments
2017-06-29 05:39:59
dễ vl
2017-06-29 05:39:39
10 dong AC ahihi
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.