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
XOR Compression In E-mail
(2 votes)
Người viết: Ngô Minh Đức   
21/04/2008

XOR COMPRESSION

Bài toán

Bạn đang cài đặt một ứng dụng cho máy điện thoại di động có màn hình đen trắng. Tọa độ x của màn hình bắt đầu từ trái sang phải và tọa độ y bắt đầu từ trên xuống dưới như trong hình vẽ. Với ứng dụng này, bạn cần những hình ảnh khác nhau nhưng không luôn cùng kích thước. Thay vì lưu giữ các hình ảnh, bạn muốn tạo ra ảnh bằng cách sử dụng thư viện đồ họa của điện thoại. Bạn có thể giả thiết rằng khi bắt đầu vẽ một hình ảnh, tất cả các điểm ảnh của màn hình có màu trắng. Trong thư viện của điẹn thoại chỉ có duy nhất lệnh XOR (L, R, T, B), lệnh này sẽ đảo giá trị của điểm ảnh trong hình chữ nhật với tọa độ trên trái là (L, T) và tọa độ dưới phải là (R, B), ở đây L là tọa độ trái (left), T là tọa độ trên (top), R là tọa độ phải (right) và B là tọa độ dưới (bottom). Chú ý rằng thứ tự các biến này không giống như trong một số thư viện đ họa khác.

Chẳng hạn để có hình 3, đầu tiên ta áp dụng lệnh XOR (2, 4, 2, 6) cho màn hình trắng , ta nhận được hình 1, tiếp theo, ta áp dụng lệnh XOR(3, 6, 4, 7) cho hình 1, ta nhận được hình 2, cuối cùng áp dụng lệnh XOR(1, 3, 3, 5) cho hình 2 ta nhận được hình 3.

Cho một tập các ảnh đen-trắng, công việc của bạn là với mỗi hình ảnh, sử dụng một số càng ít càng tốt lệnh XOR để tạo ra hình ảnh đó từ một màn hình ban đầu hoàn toàn trắng. Mỗi hình ảnh được cho bởi một tệp input. Bạn được cho các tệp input mô tả các hình ảnh và bạn phải nộp các tệp output mà mỗi tệp gồm các tham số gọi lệnh XOR cần thiết để tạo ra hình ảnh cho bởi tệp input tương ứng, không cần nộp chương trình tạo ra các tệp này.

INPUT

Bạn được cho 10 tình huống trong các tệp văn bản đặt tên từ xor1.in đến xor10.in. Mỗi tệp input được tổ chức như sau. Dòng đầu tiên chứa 1 số nguyên N, 5< N < 2000, nghi~a la` co' N dòng và N cột trong bức ảnh.

Những dòng còn lại biểu diễn các dòng của bức ảnh từ trên xuống dưới. Mỗi dòng gồm N số nguyên: đó là các giá trị của điểm ảnh trên dòng tính từ trái sang phải. Mỗi số trong những số nguyên này hoặc là 0 hoặc là 1, số 0 thể hiện điểm ảnh trắng và số 1 thể hiện điểm ảnh đen.

OUTPUT

Bạn phải nộp 10 tệp output tương ứng với các tệp input đã cho. Recall that the size of an output file must be less than 1 megabyte.

Dòng đầu tiên chứa văn bản sau:

#FILE xor I

trong đó số nguyên I là số hiệu của tệp input tương ứng. Dòng thứ hai gồm duy nhất một số nguyên K: đó là số lần gọi XOR được mô tả trong tệp. K dòng tiếp theo thể hiện những lần gọi này từ lần gọi đầu tiên đến lần gọi cuối cùng. Mỗi dòng trong số K dòng này gồm 4 số nguyên, đó là các tham số gọi XOR viết theo thứ tự L, R, T, B.

Ví dụ INPUT và OUTPUT

Cho điểm

Nếu

- các lần gọi XOR mô tả trong tệp output không tạo ra ảnh như yêu cầu, hoặc

- số lần gọi XOR được chỉ ra trong tệp output không là K, hoặc

- trong tệp output file, K >40000, hoặc

- trong tệp output có số lần gọi XOR mà L>R hoặc T>B, hoặc

- tệp output có số lần gọi XOR mà các tọa độ không dương, hoặc

- tệp output chứa một lần gọi XOR với một giá trị tọa độ vượt quá N, thì điểm của bạn là 0. Ngược lại, kết quả được tính theo công thức sau:

1+9 số lần gọi của thí sinh có lời giải tốt nhất /số lần gọi của bạn.

Số điểm được làm tròn đến 1 chữ số thập phân. Tổng số điểm được làm tròn đến số điểm gần nhất.

Giả sử bạn đã ra lời giải với 121 lần gọi XOR. Nếu đó là lời giải tốt nhất so với tất cả các thí sinh, điểm của bạn sẽ là 10. Nếu lời giải tốt nhất của các thí sinh dùng 98 lần gọi XOR, điểm của bạn sẽ là 1 + 9 ´ 98 / 121(= 8,289), và được làm tròn thành 8.3.
 
< Trước   Tiếp >