[Bài tập mẫu] Đa giác số

Bài toán: Trên vòng tròn đánh dấu n điểm phân biệt. Các điểm này được chọn làm n đỉnh của đa giác lồi P. Vẽ tất cả các đường chéo của đa giác P. Cho N là một họ gồm n số nguyên dương. Mỗi số của họ N sẽ được viết bên cạnh một đỉnh của đa giác P. Ta gọi việc làm này là phân bố các số của họ N cho các đỉnh của đa giác P. Tiếp theo, mỗi đường chéo của đa giác P sẽ được gán cho một số nguyên bằng tích của hai số gán cho đỉnh đầu mút của nó.
Ví dụ: n = 7, N = <15, 12, 2, 12, 10, 11, 10>. Một cách phân bố các số của họ N cho các đỉnh của đa giác được chỉ ra trong hình vẽ dưới đây:

Yêu cầu: Tìm cách phân bố các số của họ N cho các đỉnh của đa giác sao cho tổng các số gán cho các đường chéo là lớn nhất.
Dữ liệu: Vào từ file văn bản NUMPOLY.INP:

• Dòng đầu tiên chứa số nguyên n (3 < n ≤ 105).
• Dòng thứ hai chứa n số nguyên dương của họ N, mỗi số không vượt quá 106, hai số liên tiếp phân tách nhau bởi dấu cách.

Kết quả: Ghi ra file văn bản NUMPOLY.OUT 5 chữ số cuối cùng của tổng các số gán trên đường chéo theo cách phân bố tìm được. Chú ý là file kết quả phải chứa đúng 5 chữ số (như vậy, số gồm 5 chữ số trên file kết quả có thể có các số 0 đứng đầu).

NUMPOLY.INP	NUMPOLY.OUT
7 15 12 2 12 10 11 10	01487

Giải thích: Cách phân bố cho trong hình vẽ minh họa ở trên có tổng các số gán cho đường chéo là số có tận cùng bởi 5 chữ số ‘01487’.

Phát biểu lại bài toán:

• Cho N số nguyên: a0, a1,…, an-1 (3 < n ≤10^5);
• Tìm cách phân bố n số cho các đỉnh của đa giác n đỉnh sao cho tổng các số gán cho các đường chéo ( bằng tích của hai số ở hai đỉnh đầu mút) là lớn nhất.

Giải thuật

• Ta có khai triển: (SUM(ai))^2 = SUM((ai)^2) + 2* SUM(ai*a(i+1)mod n) + 2* SUM(ai*aj); trong đó  i = 0 to n-1
• Ta tính được bình phương tổng của các số (ký hiệu là ∑) và tổng các bình phương của các số S1, nên nếu ký hiệu S2 là tổng của tích các cặp số liên tiếp thì tổng các số trên đường chéo S được tính bởi công thức sau: S = (∑ - S1 – 2S2)/2.
• Từ đó suy ra bài toán dẫn về tìm cực tiểu tổng S1.
• Nhận xét này cho phép giảm độ phức tạp, bởi vì số lượng đường chéo là n(n-3)/2, trong đó n là số đỉnh của đa giác.
• Hơn nữa, ta có thuật toán đơn giản đê tìm cấu hình cho cực tiểu tổng S1: Sắp xếp các số a1, sau đó bắt đầu từ hai đầu dãy, tiến hành hoán đổi các số và dịch chuyển sang bên cạnh: phái trái dịch từ trái sang phải, phái phải dịch từ phải sang trái cho đến khi chờm qua nhau. Khi phân bố chú ý tiến hành tính chỉ số theo model.

Chương trình cài đặt:

#include <cstdio>
#include <iostream>
#include<stdlib.h>
#include<conio.h>
using namespace std;
#define nmax 1000000
int array[nmax];
unsigned long long sum;
unsigned long long SIGMA, sigma, sumS1;
int compare(const void * a, const void * b)
{
 return (*(int*)a - *(int*)b);
}
int main(int argc, char** argv)
{
 freopen("NUMPOLY.INP", "r", stdin);
 freopen("NUMPOLY.OUT", "w", stdout);


 int n;
 cin >> n;
 for (int i = 0; i < n; i++){
  cin>> array[i];
  SIGMA += array[i];
  sigma += array[i] * array[i];
 }
 SIGMA *= SIGMA;
 qsort(array, n, sizeof(int), compare);
 
 for (int i = 1; i < n/2; i = i+ 2){
  int temp = array[i];
  array[i] = array[n - 1 - i];
  array[n - 1 - i] = temp;
 }
 for (int i = 0; i < n; i ++){
  sumS1 += (unsigned long long) array[i] * array[(i + 1) % n];
 }

 sum = (unsigned long long)(SIGMA - sigma - 2 * sumS1) / 2;
 if (sum < 10){
  cout << "0000" << sum;
 }
 else if (sum < 100){
  cout << "000" << sum;
 }
 else if (sum < 1000){
  cout << "00" << sum;
 }
 else if (sum < 10000){
  cout << "0" << sum;
 }
 else{
  cout<< sum%100000;
 }
 
 return 0;
}