Mất mát của mạng
Đề bài
Mô tả
Rose N. Blatt đang thiết kế một mạng nơ-ron nhúng để đặt bên trong điện thoại di động. Sau khi được chủ điện thoại huấn luyện, mạng nơ-ron sẽ cho phép người dùng đọc tin nhắn văn bản mà không cần dùng tay. Ý tưởng chính trong thiết kế của Rose là dùng các hàm phản hồi đa thức phức tạp tại mỗi nút của mạng (thay cho các hàm ngưỡng truyền thống được dùng trong nhiều mạng nơ-ron khác). Hình 1 cho thấy một phần của mạng nơ-ron như vậy (các đa thức không được vẽ chính xác).

Hình 1
Khi Rose sẵn sàng chọn các đa thức, cô phát hiện ra một vấn đề. Do bộ nhớ có hạn, cô không có đủ chỗ để lưu tất cả các hệ số của các đa thức trong mạng. Cô quyết định xấp xỉ mỗi đa thức bằng một đường gấp khúc liên tục gồm hai đoạn thẳng và . Hai đoạn gặp nhau tại một điểm có hoành độ nằm giữa và . Rose muốn phép xấp xỉ là tốt nhất theo nghĩa khoảng cách giữa và hàm xấp xỉ là nhỏ nhất. Khoảng cách giữa và được định nghĩa là tích phân của bình phương hiệu của chúng:
Chẳng hạn, nếu đa thức là thì xấp xỉ gấp khúc tốt nhất, với hai đoạn gặp nhau tại , được thể hiện trong Hình 2 (đường nét đứt là đồ thị của xấp xỉ gấp khúc):

Hình 2
Trong vài byte còn trống cho mỗi nút, Rose có thể lưu các giá trị và dưới dạng số có dấu. May mắn là Rose có một chương trình cho cô một giá trị khá tốt của . Với giá trị này, hãy giúp Rose tìm các giá trị tối ưu của và cho các xấp xỉ của các đa thức.
Dữ liệu vào
Dữ liệu gồm nhiều bộ test. Mỗi bộ test gồm ba dòng:
- Dòng đầu chứa số nguyên dương () là bậc của đa thức .
- Dòng thứ hai chứa số nằm trong đoạn , là các hệ số của theo thứ tự từ hạng tử bậc cao nhất xuống hạng tử tự do, mỗi số có không quá ba chữ số sau dấu thập phân.
- Dòng cuối chứa giá trị (), có không quá ba chữ số sau dấu thập phân.
Sau bộ test cuối cùng là một dòng chứa số .
Dữ liệu ra
Với mỗi bộ test, in số thứ tự bộ test (bắt đầu từ ) và bốn giá trị tối ưu, mỗi giá trị in đúng ba chữ số sau dấu thập phân, theo định dạng của ví dụ. Giá trị thứ nhất và thứ hai là các tham số và của đoạn thẳng xác định trên đoạn . Giá trị thứ ba và thứ tư là các tham số và của đoạn thẳng xác định trên đoạn . Khoảng cách giữa và (như định nghĩa ở trên) phải nhỏ nhất trong mọi cách chọn và .
Ràng buộc
- , hệ số bậc cao nhất của khác .
- Mọi hệ số thuộc , , mỗi số có không quá ba chữ số sau dấu thập phân.
- Mỗi file có không quá bộ test.
- Trong mọi test, không đáp án nào có giá trị tuyệt đối nhỏ hơn hoặc nằm gần một ngưỡng làm tròn (cách mọi giá trị với là bội của ít nhất ).
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 2 1.0 0.0 -0.2 0.0 3 1 0 -1 0 0.707 0 |
Case 1: -1.000 -0.367 1.000 -0.367 Case 2: -0.499 -0.036 1.198 -1.236 |
Bộ 1 là ví dụ của Hình 2, . Bộ 2: , . |
| 1 0.5 0.25 0.3 2 1 0 0 0.5 3 1 0 0 0.5 -0.9 0 |
Case 1: 0.500 0.250 0.500 0.250 Case 2: -0.417 0.167 2.250 -1.167 Case 3: 6.243 5.630 0.559 0.514 |
Bộ 1: là một đường thẳng nên và . Bộ 2: , , đáp án chính xác là , , , . |
Bình luận