trang chủ / đề bài / icpcwf08_g

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 y=a1x+a0 và y=b1x+b0. Hai đoạn gặp nhau tại một điểm có hoành độ c nằm giữa −1 và +1. Rose muốn phép xấp xỉ là tốt nhất theo nghĩa khoảng cách giữa p và hàm xấp xỉ g là nhỏ nhất. Khoảng cách giữa p và g được định nghĩa là tích phân của bình phương hiệu của chúng:

d(p,g)=∫−11(p(x)−g(x))2dx

Chẳng hạn, nếu đa thức là x2−0.2 thì xấp xỉ gấp khúc tốt nhất, với hai đoạn gặp nhau tại c=0, được thể hiện trong Hình 2 (đường nét đứt là đồ thị của xấp xỉ gấp khúc):

g(x)={−x−0.367,−1≤x≤0x−0.367,0≤x≤1

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ị a1,a0,b1,b0 và c 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 c. Với giá trị này, hãy giúp Rose tìm các giá trị tối ưu của a1,a0,b1 và b0 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 n (1≤n≤10) là bậc của đa thức p(x).
  • Dòng thứ hai chứa n+1 số nằm trong đoạn [−1,1], là các hệ số của p(x) 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 (−1<c<1), 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ố 0.

Dữ liệu ra

Với mỗi bộ test, in số thứ tự bộ test (bắt đầu từ 1) 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ố a1 và a0 của đoạn thẳng y=a1x+a0 xác định g trên đoạn −1≤x≤c. Giá trị thứ ba và thứ tư là các tham số b1 và b0 của đoạn thẳng y=b1x+b0 xác định g trên đoạn c≤x≤1. Khoảng cách d(p,g) giữa p và g (như định nghĩa ở trên) phải nhỏ nhất trong mọi cách chọn a1,a0,b1 và b0.

Ràng buộc

  • 1≤n≤10, hệ số bậc cao nhất của p khác 0.
  • Mọi hệ số thuộc [−1,1], −1<c<1, mỗi số có không quá ba chữ số sau dấu thập phân.
  • Mỗi file có không quá 1000 bộ test.
  • Trong mọi test, không đáp án nào có giá trị tuyệt đối nhỏ hơn 0.0006 hoặc nằm gần một ngưỡng làm tròn (cách mọi giá trị k+0.0005 với k là bội của 0.001 ít nhất 10−5).

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, p(x)=x2−0.2. Bộ 2: p(x)=x3−x, c=0.707.
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: p là một đường thẳng nên g=p và d(p,g)=0. Bộ 2: p(x)=x2, c=0.5, đáp án chính xác là a1=−5/12, a0=1/6, b1=9/4, b0=−7/6.

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