[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;
}

Cám ơn bạn đã đọc bài viết này. Hãy chia sẻ bài viết và bình luận ý kiến của bạn ở bên dưới.

Share this

Chào mừng bạn đến với SimpleCodeCJava Blog - Mục đích của chúng tôi khi thành lập blog này là muốn chia sẻ những kiến thức và kinh nghiệm lập trình mà chúng tôi đã học được với mong muốn giúp đỡ mọi người, giúp bạn rút ngắn được thời gian tìm hiểu cũng như việc giải quyết những vấn đề trong lập trình C và Java.