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

Bài tập huấn luyện: Trò chơi

 

Một tam giác đều được chia thành N2 tam giác nhỏ đều bằng nhau bởi một lưới đường song song cách đều với các cạnh của tam giác. Tại mỗi đỉnh của các tam giác nhỏ có đặt không quá một viên bi. Có tất cả (N+1)(N+2)/2 đỉnh khác nhau được đánh số từ 1 đến (N+1)(N+2)/2 theo thứ tự các dòng từ trên xuống và trên mỗi dòng, từ trái sang phải.

Một trò chơi diễn ra như sau: Nếu có hai viên bi ký hiệu A, B nằm trên hai đỉnh của một tam giác con, người chơi có thể di chuyển viên bi A đến điểm đối xứng với nó qua viên bi B và khi đó viên bi B bị đưa ra khỏi bảng với điều kiện điểm mà A sẽ được chuyển tới là một đỉnh của một tam giác con và không có bi. Người chơi được thực hiện một dãy các di chuyển như vậy cho tới khi không thể di chuyển được nữa.

luyentap46

Người chơi giỏi là người mà sau khi chơi xong, số bi còn lại ít nhất có thể được. Bạn hãy thể hiện mình là người chơi giỏi.

Input: GAME.INP

  • Dòng thứ nhất ghi hai số nguyên dương N và M. Trong đó N là số dòng các đỉnh các tam giác con, M là số bi.
  • Dòng thứ hai ghi M số nguyên dương là số hiệu các đỉnh đặt bi.

Output: GAME.OUT

  • Dòng thứ nhất ghi số P là số phép di chuyển mà bạn sử dụng.
  • Tiếp theo là P dòng, mỗi dòng ghi 2 số U, V thể hiện một bước di chuyển với ý nghĩa viên bi ở đỉnh có số hiệu U được di chuyển đến vị trí đối xứng với viên bi ở đỉnh có số hiệu V.

Giới hạn:

  • 4 ≤ N ≤ 50
  • Thời gian: 1 s/test
  • Bộ nhớ: 16 MB

Ví dụ:

GAME.INP GAME.OUT
4 5

4 5 6 7 8

4

8 5

7 4

6 3

1 2

(Với cách chơi này, số bi còn lại bằng 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ê

  • 180,806 lượt xem

pascalteacher.nct@gmail.com


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

%d bloggers like this: