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

Bài tập huấn luyện: Hoán vị đặc biệt #2

 

Với một số nguyên dương N, một hoán vị P = (P1, P2,…, PN) được tạo ra từ các số {0, 1, 2…, N-1}  (các phần tử trong P khác nhau đôi một) được gọi là một hoán vị “đặc biệt” nếu khi ta chọn ra bộ 3 số (Pi, Pj, Pk) (1 ≤ i < j < k  ≤N) bất kỳ thì 3 số này không tạo thành một dãy có tính chất:

  • Pj = Pi + d
  • Pk = Pj + d

trong đó d là một số nguyên bất kì. Ví dụ với N = 4, dãy 3 0 1 2 không phải là một hoán vị đặc biệt vì bộ 3 số P2 = 0, P3 = 1, P4 = 2 vi phạm khi P3 = P2 + 1 và P4 = P3 + 1.

InputSPER.INP

  • Dòng đầu tiên là số nguyên dương T là test trong file input.
  • Trong T dòng tiếp theo, mỗi dòng ghi một số nguyên dương N.

Output:            SPER.OUT

  • Ứng với mỗi test trong file input, in ra một hoán vị “đặc biệt”. Nếu có nhiều đáp án, chỉ cần in ra một đáp án bất kì.

Giới hạn:

  • T ≤ 15
  • N ≤ 16000
  • Thời gian: 0.5 s/test
  • Bộ nhớ: 1MB

Ví dụ:

SPER.INP SPER.OUT
1

4

0 2 1 3
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ả

Chuyên mục

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ê

  • 252,751 lượt xem

pascalteacher.nct@gmail.com


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

%d bloggers like this: