trang chủ / đề bài / icpc25_mt_h

Tam giác kỳ diệu

Đề bài

Mô tả

Cho một tam giác đều và n số nguyên phân biệt từ 1 đến n, trong đó n chia hết cho 3.

  • Mỗi cạnh của tam giác có k vị trí để đặt số, gồm hai đỉnh và k−2 vị trí nằm giữa hai đỉnh.
  • Ba đỉnh, mỗi đỉnh thuộc hai cạnh, nên tổng số vị trí phân biệt trên cả ba cạnh là n=3k−3.

Yêu cầu: Đặt các số 1,2,…,n vào các vị trí của tam giác (mỗi số đúng một lần) sao cho tổng các số trên mỗi cạnh đều bằng đúng T.

  • Hai cách đặt được coi là khác nhau nếu dãy số trên các vị trí khác nhau.
  • Không xét tính đối xứng qua phép quay hay phép lật: mọi dãy phân biệt đều được đếm.

Dữ liệu vào

Một dòng gồm hai số nguyên n và T.

Dữ liệu ra

Nếu tồn tại ít nhất một cách đặt hợp lệ:

  • In ra tất cả các cách đặt hợp lệ theo thứ tự từ điển, mỗi cách trên một dòng, gồm đúng n số cách nhau bởi dấu cách, là các số được đặt ở các vị trí của tam giác.
  • Các vị trí được liệt kê theo một quy ước cố định: bắt đầu từ một đỉnh cố định và đi vòng quanh tam giác theo chiều kim đồng hồ. Như vậy số thứ 1, thứ k và thứ 2k−1 là ba đỉnh; cạnh thứ nhất gồm các số thứ 1 đến k, cạnh thứ hai gồm các số thứ k đến 2k−1, cạnh thứ ba gồm các số thứ 2k−1 đến n cùng với số thứ 1.
  • Quay hay lật tam giác không làm hai cách đặt trở thành giống nhau; mỗi dãy phân biệt được tính là một cách đặt riêng.
  • Sau khi in tất cả các cách đặt, in một dòng chứa tổng số cách đặt tìm được.

Nếu không có cách đặt hợp lệ nào, in ra −1.

Ràng buộc

  • 3≤n≤12, n chia hết cho 3
  • 1≤T≤40

Ví dụ

Input Output Giải thích
6 8 -1 Với n=6 thì k=3. Không có cách đặt nào để cả ba cạnh có tổng 8.
6 12 4 2 6 1 5 3
4 3 5 1 6 2
5 1 6 2 4 3
5 3 4 2 6 1
6 1 5 3 4 2
6 2 4 3 5 1
6
Ví dụ cách đặt đầu tiên: các cạnh là 4+2+6, 6+1+5, 5+3+4, đều bằng 12. Có tất cả 6 cách.

Bình luận

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0