Chuyến đi vượt thời gian: Chapter IV (Chemical Protocol)

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: 2200 Thời gian: 0.02s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Sau khi thoát khỏi cuộc khủng hoảng tên lửa Cuba trong Chapter III, Youtuber_TWK và doangiaphuc13 cuối cùng cũng có cơ hội khởi động lại chiếc máy thời gian.

Chiếc máy nhỏ, chỉ lớn khoảng bằng một cái đầu người, được đặt xuống mặt đất bên cạnh một chiếc xe quân sự cũ mà hai người tìm thấy gần đó.

Youtuber_TWK cúi xuống kiểm tra màn hình.

"Lần này chắc chắn phải về được."

doangiaphuc13:

"Hy vọng vậy."

Cậu nhấn nút khởi động.

Bíp.

Một vòng sáng xanh xuất hiện quanh thiết bị.

TEMPORAL GATE: INITIALIZING

ENERGY: 18%

ENERGY: 13%

ENERGY: 9%

Rồi đột ngột—

BÍP.

Vòng sáng biến mất.

Màn hình chuyển sang màu đỏ.

TEMPORAL GATE: OFFLINE

ENERGY: 6%

Cả hai nhìn nhau.

Youtuber_TWK:

"..."

"Đừng nói với tôi là lại hết năng lượng nhé?"

doangiaphuc13 kiểm tra thiết bị.

"Không chỉ thiếu năng lượng."

"Lõi năng lượng đang mất ổn định."

Một cảnh báo mới xuất hiện:

ENERGY CORE INSTABILITY

SECONDARY POWER SOURCE REQUIRED

Youtuber_TWK nhìn quanh.

"Ở đây còn nguồn dự phòng nào không?"

Hai người bắt đầu tìm kiếm quanh những thùng thiết bị quân sự.

Vài phút sau, doangiaphuc13 phát hiện một chiếc hộp kim loại nhỏ nằm dưới một thùng dụng cụ.

Trên nắp hộp là dòng chữ đã gần phai:

CHEMICAL ENERGY UNIT

Cậu mở nắp.

Bên trong là một thiết bị được nối với màn hình điện tử.

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

CHEMICAL REACTION SYSTEM

STATUS: LOCKED

Bên cạnh thiết bị là một tập tài liệu cũ.

Youtuber_TWK mở ra.

Những trang bên trong chứa đầy công thức hóa học.

Ở trang cuối cùng chỉ có một dòng cảnh báo:

"Phản ứng chỉ được kích hoạt khi phương trình hóa học đạt trạng thái cân bằng."

Chiếc máy thời gian lập tức phát ra tiếng bíp.

CHEMICAL BALANCE REQUIRED

REACTIONS REMAINING: 100

Youtuber_TWK:

"Một trăm phương trình?!"

doangiaphuc13:

"Có vẻ mỗi phản ứng cân bằng thành công sẽ cung cấp thêm năng lượng cho lõi."

Ngay lúc đó, chiếc radio quân sự cũ đặt bên cạnh phát ra tiếng nhiễu.

Trên mặt radio vẫn còn dòng chữ:

Р-108

Xẹt... xẹt...

Một giọng nói méo mó vang lên:

"...đơn vị... nghe rõ..."

Youtuber_TWK:

"Radio vẫn hoạt động?"

Chưa kịp kiểm tra, phía sau họ bỗng vang lên tiếng bước chân.

Cộp... cộp...

Cả hai lập tức quay lại.

Một người đang bước ra từ bóng tối.

Đó là thang16092012.

thang16092012:

"Hai ông đang làm gì ở đây vậy?"

Youtuber_TWK:

"Ủa? Ông cũng ở đây à?"

thang16092012 chỉ vào chiếc radio.

"Tôi lần theo tín hiệu của nó tới đây."

Cậu nhìn chiếc máy thời gian.

"Không ngờ lại gặp hai ông."

doangiaphuc13 đưa tập tài liệu cho cậu.

"Đúng lúc lắm."

"Bọn tôi cần khởi động lại máy thời gian."

thang16092012 lật vài trang.

"Hóa học?"

Youtuber_TWK:

"Ừ."

"Và nó bắt chúng ta cân bằng một trăm phương trình."

thang16092012 nhìn màn hình.

"..."

"Đưa đây."

Hệ thống hóa học

Hệ thống gồm nhiều phản ứng hóa học cần được cân bằng.

Mỗi phản ứng có dạng:

\[ A_1+A_2+\cdots+A_N\rightarrow B_1+B_2+\cdots+B_M \]

trong đó mỗi \(A_i\) và \(B_i\) là một công thức hóa học.

Một công thức có thể chứa:

Ký hiệu nguyên tố.
Chỉ số nguyên dương.
Dấu ngoặc tròn ( và ).
Các dấu ngoặc có thể lồng nhau.

Ví dụ:

\[ H_2O \]

chứa \(2\) nguyên tử H và \(1\) nguyên tử O.

Công thức

\[ Ca(OH)_2 \]

chứa \(1\) nguyên tử Ca, \(2\) nguyên tử O và \(2\) nguyên tử H.

Công thức

\[ Al_2(SO_4)_3 \]

chứa \(2\) nguyên tử Al, \(3\) nguyên tử S và \(12\) nguyên tử O.

Các dấu ngoặc có thể lồng nhau, chẳng hạn:

\[ K_4(ON(SO_3)_2)_2. \]

Cân bằng phản ứng

Giả sử phản ứng có \(N\) chất ở vế trái và \(M\) chất ở vế phải.

Bạn cần tìm các hệ số nguyên dương

\[ x_1,x_2,\ldots,x_N \]

và

\[ y_1,y_2,\ldots,y_M \]

sao cho với mọi nguyên tố, tổng số nguyên tử của nguyên tố đó ở hai vế bằng nhau.

Ví dụ:

\[ H_2+O_2\rightarrow H_2O \]

có thể được cân bằng thành

\[ 2H_2+O_2\rightarrow2H_2O. \]

Ngoài ra, bộ hệ số phải thỏa mãn:

\[ \gcd(x_1,x_2,\ldots,x_N,y_1,y_2,\ldots,y_M)=1. \]

Nếu tồn tại nhiều bộ hệ số hợp lệ, chọn bộ có tổng các hệ số nhỏ nhất.

Nếu vẫn còn nhiều bộ có cùng tổng, chọn bộ có thứ tự từ điển nhỏ nhất theo dãy

\[ (x_1,x_2,\ldots,x_N,y_1,y_2,\ldots,y_M). \]

Đề bài đảm bảo luôn tồn tại ít nhất một bộ hệ số thỏa mãn.

Input

Dòng đầu tiên chứa hai số nguyên \(N,M\) — số chất ở vế trái và vế phải.

Dòng thứ hai chứa \(N\) công thức hóa học ở vế trái.

Dòng thứ ba chứa \(M\) công thức hóa học ở vế phải.

Các công thức trên cùng một dòng được phân cách bởi dấu cách.

Output

In ra \(N+M\) số nguyên dương trên một dòng:

\[ x_1,x_2,\ldots,x_N,y_1,y_2,\ldots,y_M. \]

Đây phải là bộ hệ số thỏa mãn các điều kiện đã mô tả ở trên.

Example

Test 1

Input

2 1
H2 O2
H2O

Output

2 1 2

Note

Phản ứng:

\[ H_2+O_2\rightarrow H_2O \]

được cân bằng thành:

\[ 2H_2+O_2\rightarrow2H_2O. \]

Hai vế đều có \(4\) nguyên tử H và \(2\) nguyên tử O.

Test 2

Input

2 2
Fe2O3 CO
Fe CO2

Output

1 3 2 3

Note

Phản ứng:

\[ Fe_2O_3+CO\rightarrow Fe+CO_2 \]

được cân bằng thành:

\[ Fe_2O_3+3CO\rightarrow2Fe+3CO_2. \]

Test 3

Input

2 2
Al2(SO4)3 Ca(OH)2
Al(OH)3 CaSO4

Output

1 3 2 3

Note

Phản ứng:

\[ Al_2(SO_4)_3+Ca(OH)_2 \rightarrow Al(OH)_3+CaSO_4 \]

được cân bằng thành:

\[ Al_2(SO_4)_3+3Ca(OH)_2 \rightarrow 2Al(OH)_3+3CaSO_4. \]

Giới hạn

\(1\le N,M\le10\).
\(N+M\le20\).
Có không quá \(20\) nguyên tố khác nhau trong toàn bộ phản ứng.
Độ dài mỗi công thức không vượt quá \(200\).
Độ sâu lồng ngoặc không vượt quá \(10\).
Mỗi chỉ số trong công thức không vượt quá \(10^4\).
Mỗi hệ số trong đáp án không vượt quá \(10^9\).
Đề đảm bảo phản ứng luôn có ít nhất một bộ hệ số nguyên dương hợp lệ.

Scoring

Subtask (100%): Không có giới hạn bổ sung ngoài phần Giới hạn.

Phương trình đầu tiên xuất hiện trên màn hình:

\[ H_2+O_2\rightarrow H_2O. \]

thang16092012:

"Cái này thì dễ."

Cậu nhập:

\[ 2H_2+O_2\rightarrow2H_2O. \]

Bíp.

REACTION BALANCED

ENERGY +1%

REACTIONS REMAINING: 99

Youtuber_TWK:

"Có tác dụng thật."

doangiaphuc13:

"Vậy chia việc."

Youtuber_TWK:

"Tôi nhập đáp án."

doangiaphuc13:

"Tôi theo dõi lõi năng lượng."

thang16092012:

"Còn tôi cân bằng."

Ba người bắt đầu làm việc.

Phương trình thứ hai.

Rồi thứ ba.

Rồi thứ tư.

Bíp.

REACTIONS REMAINING: 87

Bíp.

REACTIONS REMAINING: 64

Thời gian trôi qua.

Chiếc radio Liên Xô bên cạnh thỉnh thoảng lại vang lên những đoạn tín hiệu nhiễu.

Xẹt... xẹt...

Không ai chú ý.

Cho đến khi màn hình chuyển sang màu đỏ.

WARNING

COMPLEX FORMULA DETECTED

Một phản ứng mới xuất hiện với nhiều lớp ngoặc lồng nhau.

thang16092012:

"..."

"Được rồi. Bắt đầu khó thật rồi đấy."

Youtuber_TWK nhìn đồng hồ đếm ngược.

TIME UNTIL SYSTEM SHUTDOWN: 28:41

"Chúng ta còn chưa đến nửa tiếng."

doangiaphuc13:

"Vậy thì làm nhanh."

Các phương trình tiếp tục được giải.

REACTIONS REMAINING: 36

...

REACTIONS REMAINING: 10

...

REACTIONS REMAINING: 3

Chiếc máy bắt đầu rung mạnh.

ENERGY: 82%

ENERGY: 91%

ENERGY: 97%

Youtuber_TWK:

"Còn ba!"

thang16092012:

"Đưa đây."

Ba phản ứng cuối cùng lần lượt được cân bằng.

BÍP

REACTIONS REMAINING: 0

Màn hình chuyển sang màu xanh.

CHEMICAL PROTOCOL: COMPLETE

ENERGY CORE: STABLE

TEMPORAL GATE: READY

Youtuber_TWK thở phào.

"Cuối cùng cũng xong."

Nhưng ngay lúc đó

XẸT... XẸT...

Chiếc radio bên cạnh đột nhiên phát tín hiệu mạnh.

Cả ba quay lại.

Một giọng nói méo mó vang lên:

"...đơn vị kiểm soát..."

"...Pripyat..."

Xẹt...

"...Chernobyl Nuclear Power Plant..."

"...sự cố tại lò phản ứng..."

"...tình hình chưa được kiểm soát..."

Rồi tín hiệu biến mất.

Cả ba im lặng.

doangiaphuc13:

"Chernobyl?"

Chiếc máy thời gian đột nhiên phát ra tiếng cảnh báo.

UNKNOWN SIGNAL DETECTED

SOURCE: USSR MILITARY NETWORK

TEMPORAL SIGNAL LOCKED

Youtuber_TWK:

"Khoan đã."

"Chúng ta chưa chọn điểm đến."

Màn hình tiếp tục chạy.

TEMPORAL COORDINATES CALCULATING...

LOCATION: UKRAINIAN SSR

YEAR: 1986

thang16092012:

"1986?"

Một dòng cuối cùng xuất hiện.

DESTINATION: CHERNOBYL

doangiaphuc13:

"Không ổn rồi."

Chiếc máy rung dữ dội.

TEMPORAL JUMP INITIALIZED

Youtuber_TWK:

"Tắt nó đi!"

doangiaphuc13 đập tay vào nút tắt.

Không có tác dụng.

3

2

1

Một luồng sáng trắng nuốt chửng cả ba.

Khi Youtuber_TWK mở mắt, thứ đầu tiên anh nghe thấy là tiếng còi báo động.

Căn cứ quân sự đã biến mất.

Những chiếc xe cũng không còn ở đó.

Trước mặt họ là một con đường xa lạ giữa những khối nhà cao tầng chìm trong màn đêm.

Ở phía chân trời, một cột khói khổng lồ đang vươn lên bầu trời.

thang16092012 nhìn cảnh tượng trước mặt.

"...Chernobyl."

doangiaphuc13 cúi xuống.

Chiếc máy thời gian nằm trên mặt đường.

Màn hình chỉ còn sáng một dòng:

APRIL 26, 1986

Một tiếng còi khác vang lên từ phía xa.

Lần này không phải từ chiếc máy.

doangiaphuc13:

"Chúng ta vừa đến đúng thời điểm xảy ra sự cố."

thang16092012:

"Vậy..."

"...bây giờ phải làm gì?"

Youtuber_TWK nhìn về phía ánh sáng đang phản chiếu lên bầu trời.

"Trước tiên phải tìm hiểu chuyện gì vừa xảy ra."

Chiếc máy thời gian lại phát sáng.

DESTINATION REACHED: CHERNOBYL

TEMPORAL MISSION: ACTIVE

CHEMICAL PROTOCOL: COMPLETE

TEMPORAL GATE: CLOSED

Youtuber_TWK nhìn màn hình.

"Ít nhất lần này máy không nổ..."

thang16092012:

"Và cũng không bắt cân bằng thêm phương trình."

Bíp.

Một dòng chữ mới xuất hiện.

NEW MISSION DATA DETECTED

Cả ba nhìn nhau.

Không ai nói gì.

Ở phía xa, tiếng còi báo động vẫn tiếp tục vang lên.

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

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

Bình luận (3)

Tải bình luận...