Tổng nhiều số nguyên cực lớn có dấu

Bối cảnh

Một hệ thống tài chính thử nghiệm nhận n số nguyên có thể dài hàng nghìn chữ số, vượt xa long long. Mỗi số có thể bắt đầu bằng + hoặc -, có thể có nhiều số 0 ở đầu. Nhiệm vụ là tính tổng chính xác của tất cả số và in ở dạng canonical: không dấu +, không leading zero; số 0 luôn in 0 chứ không -0.

Không được dùng thư viện big integer. Hãy biểu diễn magnitude bằng std::string. Cần các hàm: chuẩn hóa input; so sánh hai magnitude; cộng hai magnitude; trừ magnitude nhỏ khỏi magnitude lớn. Khi cộng hai số có cùng dấu, cộng magnitude; khi khác dấu, trừ magnitude và lấy dấu của magnitude lớn hơn. Sau mỗi bước, accumulator vẫn là một số signed canonical.

Bài Advanced yêu cầu pipeline nhiều hàm nhỏ và xử lý carry/borrow từ phải sang trái. Đây là dạng arbitrary precision kinh điển trong Olympic/ICPC Foundation.

Để tránh code signed arithmetic trở thành một hàm khổng lồ, hãy kiểm thử riêng từng primitive: addMag("999","1"), subMag("1000","1"), compare magnitude khác độ dài và canonical -0000. Khi các primitive đúng, phép cộng nhiều số chỉ còn là việc cập nhật accumulator theo dấu. Đây cũng là cách tổ chức lời giải contest để giảm rủi ro bug borrow/carry.

Yêu cầu

1. Đọc n và n token số nguyên có dấu.
2. Chuẩn hóa từng token.
3. Tính tổng bằng signed big integer string.
4. Không dùng kiểu số để chứa toàn bộ giá trị.
5. In canonical result.

Yêu cầu tổ chức code

Không dùng thư viện big integer hoặc kiểu số để chứa toàn operand.

Online Judge chấm output. Giảng viên có thể review source code để kiểm tra việc sử dụng đúng pointer/lifetime/string pipeline theo phạm vi buổi học.

Input

Dòng 1 n; n dòng hoặc token số.

Output

Một số nguyên canonical.

Ràng buộc

1≤n≤200, mỗi số dài ≤2000 chữ số; input hợp lệ theo grammar [+-]?[0-9]+.

Ví dụ 1

Input

3
999999999999999999999
1
-2

Output

999999999999999999998

Giải thích

Accumulator bắt đầu 0. Cộng số đầu 999...999, sau đó cộng 1 tạo carry xuyên toàn chuỗi thành 1000000000000000000000. Cuối cùng cộng -2 nghĩa là trừ magnitude 2, kết quả 999999999999999999998. Không có kiểu số nguyên chuẩn nào được dùng để chứa toàn giá trị.

Ví dụ 2

Input

2
-1000
250

Output

-750

Giải thích

Accumulator sau token đầu là -1000. Token tiếp theo +250 có dấu khác, nên phải so magnitude 1000 và 250. Vì 1000 lớn hơn, thực hiện subMag("1000","250") = "750" và giữ dấu của operand magnitude lớn là âm. Không có leading zero và magnitude khác 0, nên canonical result cuối là -750.

Thông tin học tập

• Module: M06
• Buổi: B21
• Loại bài: ADVANCED
• Độ khó: Hard
• Concepts: big integer string, signed addition, magnitude compare, normalization, arbitrary precision
• Giới hạn kiến thức: B01-B21
• Time limit: 2 second(s)
• Memory limit: 256 MB
• Point: 100