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
A4. Rô bốt đi dạo In E-mail
(1 vote)
Người viết: Ngô Minh Đức   
17/04/2008

Bài 4. Rô bốt đi dạo                                                           Tên file chương trình: TOUR.PAS

Công ty VinaBot là một trong các công ty nổi tiếng về chế tạo Rô bốt. Vừa qua, họ đã chế tạo một con Rô bốt mới và đang trong quá trình thử nghiệm. Rô bốt này có khả năng tự vận hành. Điểm đặc biệt là nó có khả năng tự tìm về vị trí xuất phát. Giai đoạn hiện nay Rô bốt đang được huấn luyện để tìm đường đi theo qui luật định sẵn. Sân thử nghiệm Rô bốt có hình vuông, kích thước NxN ô, giới hạn bởi điểm có toạ độ (0, 0) ở góc dưới trái và điểm toạ độ (N,N) ở góc trên phải.

 

Từ điểm thích hợp P có toạ  độ (i,j) thuộc sân thử nghiệm ( 0 i, j N), rô bốt phải di chuyển theo một đường gấp khúc khép kín do nó tự xác định, thoả mãn các điều kiện:

  • Đường gấp khúc có đúng M đỉnh và không có 3 đỉnh liên tiếp thẳng hàng,
  • Các đỉnh của đường gấp khúc phải nằm trên sân thử nghiệm và có toạ độ nguyên,
  • Kể từ điểm P, tính theo hướng chuyển động của Rô bốt, các cạnh của đường gấp khúc  phải lần lượt nhận những giá trị cho trước làm độ dài,
  • Rô bốt không đi qua một đỉnh nào của đường gấp khúc quá một lần, trừ đỉnh P nơi nó sẽ quay về.

Ban đầu, rô bốt đứng tại điểm có toạ độ (0,0). Nếu không tồn tại đường gấp khúc khép kín đáp ứng yêu cầu đã nêu, Rô bốt nhấp nháy đèn đỏ và ở nguyên tại chỗ. Trong trường hợp ngược lại, rô bốt tiến thẳng tới điểm xuất phát thử nghiệm (i,j), bật đèn xanh báo hiệu bắt đầu thực hiện chương trình của mình và chuyển động theo đường gấp khúc tìm được.

 

Yêu cầu: Hãy giúp rô bốt xác định điểm P cũng như các đỉnh khác của đường gấp khúc mà rô bốt phải đi theo yêu cầu đặt ra hoặc thông báo rằng không thể tìm được một đường như vậy.

Để đơn giản cho việc tính toán của rô bốt, thay vì cho chiều dài của các đoạn gấp khúc, người ta sẽ cung cấp cho nó bình phương của các chiều dài này (vì đây sẽ là các giá trị nguyên).

Dữ liệu: Dữ liệu vào cho trong file văn bản có tên TOUR.INP gồm 2 dòng:

·         Dòng đầu chứa 2 số nguyên N và  M (2 N 15; 3 M 20),

·         Dòng thứ hai gồm M số nguyên dương cho biết bình phương chiều dài của các đoạn trên đường gấp khúc đúng theo trình tự mà Rô bốt cần đi qua.

Kết quả: Kết quả ghi ra file văn bản có tên TOUR.OUT gồm M dòng, mỗi dòng chứa 2 số nguyên cho biết toạ độ của các đỉnh của đường gấp khúc  tìm được. Các toạ độ được nêu theo trình tự chuyển động của rô bốt, tính từ điểm xuất phát. Trong trường hợp có nhiều phương án, chỉ cần đưa đúng một trong số đó. Nếu không có lời giải, file sẽ chứa duy nhất số -1.

Trong file dữ liệu vào và file kết quả, các số trên một dòng cách nhau ít nhất một dấu cách.

Ví dụ:

TOUR.INP

TOUR.OUT

8 4

13 29 65 5

 

0 1

3 3

1 8

2 0

 

8 4

1 1 1 2

 

-1

 

 
< Trước