Chuyến đi vượt thời gian: Chapter V (Chernobyl Nuclear Accident 1986)

Xem PDF
Tất cả bài nộp
Các bài nộp tốt nhất
Tác giả:
Youtuber_TWK, doangiaphuc13, thang16092012
Dạng bài
Ngôn ngữ cho phép
Assembly, Awk, C, C#, C++, Clang, Cobol, D, Groovy, Haskell, JS, Java, Kotlin, Lua, Node JS, OCaml, ObjectiveC, Output, PHP, Pascal, Perl, Prolog, Pypy, Pypy 3, Python, Ruby, Rust, Scala, Scratch, Swift
Điểm: 1600 Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Sau khi hoàn thành Chemical Protocol trong Chapter IV, Youtuber_TWK, doangiaphuc13 và thang16092012 đã bị chiếc máy thời gian đưa thẳng tới năm 1986.

DESTINATION REACHED: CHERNOBYL
TEMPORAL MISSION: ACTIVE
CHEMICAL PROTOCOL: COMPLETE
TEMPORAL GATE: CLOSED

Tiếng còi báo động vẫn vang lên giữa màn đêm.

Youtuber_TWK nhìn về phía chân trời.

Một cột khói khổng lồ đang vươn lên bầu trời.

doangiaphuc13 nhìn chiếc máy thời gian.

"Không còn nghi ngờ gì nữa."

"Chúng ta đang ở Chernobyl."

thang16092012 nhìn xung quanh.

"Nhưng tại sao máy lại đưa chúng ta tới đây?"

Không ai trả lời.

Đột nhiên—

BÍP.

Màn hình sáng lên.

UNKNOWN TEMPORAL SIGNAL
SIGNAL STATUS: ACTIVE
ORIGIN: USSR — 1983
DESTINATION: 1963

Youtuber_TWK:

"Signal năm 1983..."

doangiaphuc13 gật đầu.

"Nó vẫn còn hoạt động."

Một bản đồ xuất hiện.

Một điểm sáng màu đỏ nhấp nháy bên trong khu vực Chernobyl.

SIGNAL SOURCE DETECTED
DISTANCE: 4.7 KM

thang16092012:

"Nguồn phát đang ở gần đây."

Youtuber_TWK:

"Vậy thì đi tìm nó."

Phòng thí nghiệm

Sau một thời gian tìm kiếm, cả ba tìm thấy một tòa nhà kỹ thuật bị bỏ hoang.

Bên trong là một phòng điều khiển cũ.

Một chiếc máy tính vẫn còn hoạt động.

thang16092012 bật màn hình.

USSR NUCLEAR RESEARCH SYSTEM
REACTOR PHYSICS SIMULATOR
STATUS: EMERGENCY MODE

Một cửa sổ khác xuất hiện.

NEUTRON FLUX SIMULATION

doangiaphuc13:

"Mô phỏng neutron..."

Youtuber_TWK:

"Liên quan đến lò phản ứng?"

"Có vẻ vậy."

Màn hình đột nhiên chuyển sang màu đỏ.

REACTOR STATE CANNOT BE DETERMINED
PHYSICS MODEL REQUIRED

Ngay sau đó, một tập dữ liệu xuất hiện.

Mô hình phản ứng neutron

Ta xét một mô hình đơn giản hóa của phản ứng dây chuyền trong lò phản ứng.

Một neutron tại mỗi thời điểm có thể thuộc một trong \(s\) trạng thái năng lượng:

\[ 1,2,\ldots,s \]

Trong đó:

  • Trạng thái \(1\) là neutron năng lượng cao.
  • Trạng thái \(s\) là neutron năng lượng thấp.

Lò phản ứng gồm \(r\) vùng phản ứng. Mỗi vùng có \(s\) mức năng lượng.

Đặt:

\[ n=r\times s \]

là tổng số trạng thái của hệ thống.

Các trạng thái được đánh số theo thứ tự:

\[ (1,1),(1,2),\ldots,(1,s),(2,1),\ldots,(r,s) \]

Trong đó \((x,y)\) biểu diễn trạng thái thuộc vùng \(x\) và mức năng lượng \(y\). Trạng thái \((x,y)\) được đánh chỉ số 1-based là:

\[ \mathrm{id}(x,y)=(x-1)\times s+y \]

Ma trận chuyển trạng thái

Với mỗi cặp trạng thái \(i,j\), hệ thống cho biết số neutron kỳ vọng ở trạng thái \(j\) được tạo ra bởi một neutron ở trạng thái \(i\) sau một bước thời gian:

\[ A_{i,j}=\frac{a_{i,j}}{q} \]

Giá trị \(A_{i,j}\) không nhất thiết nằm trong đoạn \([0,1]\).

Nó có thể bao gồm toàn bộ ảnh hưởng của:

  • chuyển trạng thái;
  • sinh neutron;
  • neutron tiếp tục tồn tại;
  • neutron thất thoát khỏi hệ thống.

Vì vậy, \(A\) không nhất thiết là ma trận xác suất.

Ta sử dụng vector hàng:

\[ v_t=(v_{t,1},v_{t,2},\ldots,v_{t,n}) \]

trong đó \(v_{t,i}\) là số neutron kỳ vọng ở trạng thái \(i\) sau \(t\) bước.

Hệ thống tiến hóa theo:

\[ v_{t+1}=v_tA \]

Quy ước ma trận

Do sử dụng vector hàng:

  • hàng \(i\) của \(A\) là trạng thái nguồn;
  • cột \(j\) của \(A\) là trạng thái đích.

Nói cách khác, \(A_{i,j}\) là số neutron kỳ vọng ở trạng thái \(j\) được tạo ra bởi một neutron ở trạng thái \(i\) sau một bước.

Năng lượng

Mỗi trạng thái \(i\) có một giá trị năng lượng kỳ vọng:

\[ C_i=\frac{c_i}{q} \]

Một neutron ở trạng thái \(i\) giải phóng trung bình \(C_i\) đơn vị năng lượng trong một bước thời gian.

Gọi \(E_t\) là tổng năng lượng đã giải phóng sau \(t\) bước.

Ban đầu:

\[ E_0=0 \]

Trong bước chuyển từ \(t\) sang \(t+1\), năng lượng được tính dựa trên số neutron trước khi thực hiện bước chuyển, tức là \(v_t\):

\[ E_{t+1}=E_t+\sum_{i=1}^{n}v_{t,i}C_i \]

Do đó, sau đúng \(T\) bước:

\[ E=\sum_{t=0}^{T-1}\sum_{i=1}^{n}v_{t,i}C_i \]

Lưu ý rằng năng lượng của bước đầu tiên được tính từ \(v_0\), còn năng lượng của bước cuối cùng được tính từ \(v_{T-1}\).

Nhiều vùng phản ứng

Lò phản ứng có \(r\) vùng phản ứng.

Một neutron ở vùng \(x\) có thể:

  • tiếp tục phản ứng trong vùng \(x\);
  • chuyển sang vùng khác;
  • thay đổi mức năng lượng;
  • tạo thêm neutron;
  • hoặc thoát khỏi hệ thống.

Toàn bộ các quá trình trên đã được gộp vào ma trận \(A\).

Vì vậy, mỗi trạng thái thực tế được xác định bởi cặp (vùng, mức năng lượng).

Nếu có \(r\) vùng và \(s\) mức năng lượng thì tổng số trạng thái là:

\[ n=r\times s \]

Ta xây dựng ma trận chuyển trạng thái \(A\) có kích thước \(n\times n\).

Nhiệm vụ

Cho trạng thái ban đầu của hệ thống, ma trận chuyển trạng thái và số bước \(T\).

Hãy tính:

  1. Số neutron kỳ vọng ở mỗi trạng thái sau đúng \(T\) bước.
  2. Tổng năng lượng kỳ vọng được giải phóng trong toàn bộ \(T\) bước.

Ta có:

\[ v_T=v_0A^T \]

và:

\[ E=\sum_{t=0}^{T-1}v_tC \]

trong đó \(C\) được xem là vector cột:

\[ C=\begin{pmatrix}C_1\\C_2\\\vdots\\C_n\end{pmatrix} \]

Vì \(T\) có thể rất lớn, không thể mô phỏng từng bước.

Cần sử dụng lũy thừa ma trận kết hợp kỹ thuật cộng dồn tổng cấp số nhân của ma trận, ví dụ bằng cách mở rộng \(A\) thành ma trận khối kích thước \((n+1)\times(n+1)\).

Tính toán modulo

Tất cả kết quả được tính modulo:

\[ MOD=1000000007 \]

Các giá trị trong input có dạng phân số với cùng mẫu số \(q\):

\[ A_{i,j}=\frac{a_{i,j}}{q},\qquad C_i=\frac{c_i}{q} \]

Khi tính toán các phân số modulo \(MOD\), ta sử dụng nghịch đảo modulo của \(q\):

\[ \frac{x}{q}\equiv x\cdot q^{-1}\pmod{MOD} \]

Đề bài đảm bảo:

\[ \gcd(q,MOD)=1 \]

nên \(q^{-1}\) luôn tồn tại.

Với số neutron ban đầu \(v_i\), có thể lấy \(v_i\bmod MOD\) ngay khi đọc dữ liệu.

Input

  • Dòng đầu tiên chứa bốn số nguyên:
\[ r\ s\ T\ q \]

trong đó \(r\) là số vùng phản ứng, \(s\) là số mức năng lượng mỗi vùng, \(T\) là số bước thời gian, \(q\) là mẫu số chung của các phân số trong input.

  • Dòng thứ hai chứa \(n=r\times s\) số nguyên:
\[ v_1\ v_2\ \ldots\ v_n \]

là số neutron ban đầu ở mỗi trạng thái theo thứ tự đánh số \((1,1),(1,2),\ldots,(r,s)\).

  • \(n\) dòng tiếp theo, dòng thứ \(i\) (\(1\le i\le n\)) chứa \(n\) số nguyên:
\[ a_{i,1}\ a_{i,2}\ \ldots\ a_{i,n} \]

biểu diễn hàng thứ \(i\) của ma trận \(A\) đã nhân với \(q\), tức là \(A_{i,j}=\dfrac{a_{i,j}}{q}\).

  • Dòng cuối cùng chứa \(n\) số nguyên:
\[ c_1\ c_2\ \ldots\ c_n \]

biểu diễn vector năng lượng đã nhân với \(q\), tức là \(C_i=\dfrac{c_i}{q}\).

Output

  • Một dòng gồm \(n\) số nguyên, là:
\[ v_{T,1},v_{T,2},\ldots,v_{T,n}\pmod{MOD} \]
  • Một dòng tiếp theo gồm một số nguyên duy nhất, là:
\[ E\bmod MOD \]

Ràng buộc

  • \(1\le r\le3\)
  • \(1\le s\le2\)
  • \(1\le n=r\times s\le6\)
  • \(1\le T\le10^{18}\)
  • \(1\le q\le10^9\)
  • \(0\le a_{i,j}\le10^9\)
  • \(0\le c_i\le10^9\)
  • \(0\le v_i\le10^{18}\)
  • \(\gcd(q,10^9+7)=1\)

Đề bài đảm bảo tất cả dữ liệu đều hợp lệ.

Scoring

  • Subtask 1 (100%): Không có giới hạn bổ sung.

Example

Test 1

Input

1 2 2 1
1 0
2 1
0 3
5 1

Output

4 5
16

Note

Với \(r=1,s=2\) nên \(n=2\), \(q=1\) (không cần nghịch đảo).

  • \(v_0=(1,0)\), \(A=[[2,1],[0,3]]\), \(C=(5,1)\).
  • \(v_1=v_0A=(2,1)\).
  • \(v_2=v_1A=(4,5)\).
  • \(E=v_0\cdot C+v_1\cdot C\).
  • \(=(1\cdot5+0\cdot1)+(2\cdot5+1\cdot1)\).
  • \(=5+11=16\).

Màn hình im lặng vài giây.

Youtuber_TWK nhìn ma trận.

"..."

doangiaphuc13:

"Sao?"

Youtuber_TWK:

"Cái này không còn là bài vật lý bình thường nữa rồi."

thang16092012 nhìn \(T=10^{18}\).

"Mô phỏng từng bước chắc chắn chết."

doangiaphuc13 nhìn ma trận.

"Vậy thì nâng ma trận lên lũy thừa."

Youtuber_TWK:

"Ma trận sáu nhân sáu..."

Anh nhìn màn hình thêm vài giây.

"...nhưng \(T\) tới \(10^{18}\)."

thang16092012:

"Lũy thừa nhị phân."

Youtuber_TWK:

"Được."

Cậu bắt đầu nhập chương trình.

MATRIX EXPONENTIATION
T = 1000000000000000000
PROCESSING...

POWER 1
POWER 2
POWER 4
POWER 8
POWER 16
...
POWER 524288
...
POWER 1099511627776
...

Cuối cùng—

BÍP.

PHYSICS SIMULATION COMPLETE

Nhưng ngay khi kết quả xuất hiện, chiếc máy thời gian bên cạnh đột nhiên sáng lên.

TEMPORAL SIGNAL DETECTED
ORIGIN: 1983
DESTINATION: 1963
SIGNAL STRENGTH: 100%

doangiaphuc13 quay phắt lại.

"Signal!"

Màn hình tiếp tục thay đổi.

ARCHIVED MESSAGE FOUND
DATE: 1983-██-██
LOCATION: USSR

Một đoạn dữ liệu được giải mã.

THE REACTOR MODEL WAS NEVER THE REAL EXPERIMENT.

Cả ba im lặng.

Một dòng cuối cùng hiện lên:

THE REAL EXPERIMENT WAS TEMPORAL TRANSMISSION.

Youtuber_TWK:

"...Thí nghiệm thật sự không phải về lò phản ứng."

thang16092012:

"Mà là truyền tín hiệu xuyên thời gian."

Chiếc máy thời gian phát ra một tiếng BÍP.

NEXT TEMPORAL EVENT: 1963

Cả ba nhìn nhau.

Lần này, họ đã có một manh mối rõ ràng.

Signal năm 1983 đang cố gửi thứ gì đó về năm 1963.

Và bằng cách nào đó, chiếc máy thời gian của họ đã bắt được nó.

Câu chuyện vẫn chưa kết thúc!!!!

Chuyến đi vượt thời gian: Chapter VI (Temporal Reconstruction)

Bình luận (5)

Mới nhất
Tải bình luận...