Đa giác số - thuật toán và cài đặt bằng C/C++

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).

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;

}