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

UTOPIA

Bài toán

Đất nước Utopia tươi đẹp bị chiến tranh tàn phá. Khi chiến tranh đi qua, kẻ thù đã chia cắt đất nước này thành 4 miền bởi một đường kinh tuyến (theo hướng Bắc-Nam) và một đường vĩ tuyến (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 trở thành Utopia 1 (phía Đông Bắc), Utopia 2 (phía Tây Bắc), Utopia 3 (phía Tây Nam) và 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). Các tọa độ này có thể âm; do đó một điểm ở miền Utopia 2 có tọa độ (âm, dương), một điểm ở miền Utopia 3 có tọa độ (âm, âm), một điểm ở miền Utopia 4 có tọa độ (dương, âm), một điểm ở miền Utopia 1 có tọa độ (dương, dương).

Một vấn đề là công dân các miền không được đ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 mày cần các mã số, mỗi mã số chỉ được dùng một lần. Bây giờ, bạn và nhóm thí sinh trên hãy 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 phải quan tâm đến việc phải hạ cánh ở đ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.

Input là một chuỗi gồm 2N mã số và bạn 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 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 -.

Giả sử bạn có các mã số 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 gồm các cặp mã số (+7,-1), (-5,+2), (-4,+3), (+8,+6) đáp ứng yêu cầu này vì nó đưa bạn từ điểm (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.

Yêu cầu

Cho trước 2N mã số khác nhau và một dãy N số hiệu 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ã số từ các mã 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

Dòng đầu tiên chứa số nguyên dương N (1< N> 10000). Dòng thứ hai chứa 2N mã số nguyên khác nhau (nằm trong khoảng từ 1 đến 100000) được ngăn cách bằng ký tự trống. Dòng cuối cùng chứa một dãy gồm N số hiệu miền (1, 2, 3 hoặc 4).

OUTPUT

Output gồm N dòng, mỗi dòng chứa một cặp mã số, trước mỗi mã số có một dấu + hoặc -. Đó là các cặp mã sẽ hướng dẫn máy vận chuyển từ xa đến các miền đã cho. Chú ý không được cho dấu cách trống sau dấu + hoặc - nhưng phải có một dấu cách trống sau mã số thứ nhất.

Nếu có nhiều lời giải, chương trình của bạn hãy đư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.

Ví dụ INPUT và OUTPUT

Cho điểm

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