//
you're reading...
Bài tập huấn luyện

Bài tập huấn luyện: Lát nền

 

Cho tới nay trụ sở của IOICAMP vẫn là một phòng nhỏ bừa bãi trên tầng 3 của khối chuyên Toán-Tin học Đại học Quốc gia Hà Nội. Sau khi tham quan đại bản doanh của IOICAMP, anh Nguyễn Thành Nam (FSOFT) ngỏ ý muốn tặng IOICAMP một mảnh đất xây trụ sở. Để thử thách trí tuệ của IOICAMP, anh Nam đề ra các yêu cầu sau:

  • Có một mảnh đất hình chữ nhật kích thước M´N ô vuông đơn vị, các dòng ô vuông đánh số từ 1 đến M từ trên xuống, các cột ô vuông đánh số từ 1 đến N từ trái sang phải.
  • Có K viên gạch vuông cạnh đơn vị, mỗi cạnh có một mầu nói chung khác nhau, các màu có số hiệu nguyên dương.
  • Cần đặt các viên gạch trên mảnh đất sao cho các điều kiện sau thoả mãn:
    • Mỗi viên gạch phủ một ô vuông đất.
    • Cạnh chung của hai viên gạch kề cạnh có cùng màu.
    • Khi đặt viên gạch, không được lật ngược mặt nhưng có thể quay để phù hợp màu ở cạnh chung.
    • Tập các viên gạch được đặt liên thông kề cạnh.

Trụ sở IOICAMP sẽ xây dựng trên vùng đất được phủ bởi các viên gạch này. Các bạn hãy tìm cách đặt các viên gạch sao cho chúng ta có một trụ sở rộng nhất.

Input:     TILE.INP

  • Dòng thứ nhất ghi bốn số M, N, K.
  • Dòng thứ i trong K dòng tiếp theo ghi bốn số nguyên dương U, R, D, L tương ứng là các màu của các cạnh trên, phải, dưới, trái của viên gạch thứ i.

Output:   TILE.OUT

Ghi ra K dòng, dòng thứ i ghi 3 số U V W thể hiện cách đặt viên gạch thứ i với U, V là tọa độ dòng, cột của viên gạch và W = 0/1/2/3 có nghĩa viên gach đặt tại ô đó quay một góc 0o/90o/180o/270o ngược chiều kim đồng hồ so với vị trí chuẩn đã cho trong file input. Nếu viên gạch thứ i không được sử dụng thì dòng thứ i ghi ra 3 số –1.

Giới hạn:

  • 1 ≤ M, N ≤ 100
  • 1 ≤ K ≤ 10000
  • Màu sắc trên các cạnh của các viên gạch là các số nguyên dương không quá 10000.
  • Thời gian: 3 s/test
  • Bộ nhớ: 16 MB

Ví dụ:

TILE.INP TILE.OUT
2 2 4

1 2 3 2

2 4 5 4

1 1 1 1

6 6 6 6

2 1 0

2 2 1

1 1 0

-1 -1 -1

Advertisements

About pascalteacher

Trang thông tin Toán học và Tin học

Thảo luận

Không có bình luận

Trả lời

Mời bạn điền thông tin vào ô dưới đây hoặc kích vào một biểu tượng để đăng nhập:

WordPress.com Logo

Bạn đang bình luận bằng tài khoản WordPress.com Đăng xuất / Thay đổi )

Twitter picture

Bạn đang bình luận bằng tài khoản Twitter Đăng xuất / Thay đổi )

Facebook photo

Bạn đang bình luận bằng tài khoản Facebook Đăng xuất / Thay đổi )

Google+ photo

Bạn đang bình luận bằng tài khoản Google+ Đăng xuất / Thay đổi )

Connecting to %s

Các tác giả

Categories

Tháng Mười 2016
H B T N S B C
« Th9   Th11 »
 12
3456789
10111213141516
17181920212223
24252627282930
31  

NCT Computer

Flickr Photos

Thống kê

  • 148,992 lượt xem

pascalteacher.nct@gmail.com


Trang huấn luyện học sinh giỏi Tin học

%d bloggers like this: