Contest ôn thi HSG 9-10 (số 4)

Bạn có một ổ khóa số gồm ba chữ số (có giá trị từ \(0-9\)). Mỗi vị trí có thể xoay thuận chiều (tăng giá trị lên một) hoặc ngược chiều (giảm giá trị đi một).

Đặc biệt, do các giá trị được xếp theo vòng tròn nên số \(0\) và số \(9\) ở liên tiếp nhau. Tại vị trí có giá trị là \(9\), xoay thuận chiều sẽ được \(0\) và ngược lại, từ giá trị \(0\), xoay ngược chiều sẽ được \(9\).

Yêu cầu: Bạn đang ở trạng thái ban đầu (000), và cần chuyển đến trạng thái cuối là số \(\overline{abc}\) cho trước. Hỏi cần phải xoay ít nhất bao nhiêu lần?

Input

• Dữ liệu đọc từ tệp văn bản KHOASO.INP:
  • Dòng duy nhất chứa ba chữ số \(\overline{abc}\) được viết liền nhau (\(0 \le a, b, c \le 9\)).

Output

• Ghi ra tệp văn bản KHOASO.OUT:
  • Dòng duy nhất chứa kết quả bài toán.

Example

129

4

Hôm nay Tí học về số lẻ. Vì rất tò mò nên Tí thử tạo các biểu thức để khám phá tính chất của chúng. Tí viết bình phương các số lẻ đầu tiên và đảo dấu các số này một cách xen kẽ: \(1^2, -3^2, 5^2, -7^2, 9^2, \dots\) sau đó tính tổng của \(n\) số đầu tiên. Việc tính toán bằng tay với \(n\) nhỏ không thành vấn đề, nhưng với \(n\) lớn, Tí cần sự trợ giúp của lập trình.

Yêu cầu: Cho biết \(n\), hãy tính tổng \(n\) số hạng đầu tiên của dãy số tạo bởi quy luật trên.

Input

• Đọc vào từ tệp văn bản TONGLE.INP:
  • Dòng duy nhất chứa số nguyên \(n\) (\(1 \le n \le 10^9\)).

Output

• Ghi ra tệp văn bản TONGLE.OUT:
  • Dòng duy nhất chứa kết quả tổng cần tính.

Example

2

-8

Ràng buộc

• Subtask 1 (\(70\%\) số điểm): \(n \le 10^6\).
• Subtask 2 (\(30\%\) số điểm): Không có ràng buộc thêm.

Q vừa tìm hiểu về Radix Sort, cảm thấy vô cùng thích thú nên bạn ấy đã áp dụng vào bài toán này. Xét dãy số \(a\) gồm \(n\) phần tử được tạo từ các số nguyên \(b, c, d, M\) theo công thức như sau:

• \(a_1 = b\)
• \(a_2 = c\)
• \(a_i = (a_{i-2} \times a_{i-1} + d) \% M\) với mọi \(i\) mà \(3 \le i \le n\). Trong đó \(\%\) kí hiệu cho phép chia lấy dư.

Q dự đoán rằng, dãy \(a\) sau khi tạo sẽ có rất nhiều giá trị trùng lặp. Q muốn tìm ra giá trị xuất hiện nhiều lần nhất.

Yêu cầu: Cho biết \(n, b, c, d, M\). Hãy tìm giá trị xuất hiện nhiều lần nhất trong \(a\). Nếu có nhiều giá trị như vậy, in ra giá trị lớn nhất.

Input

• Dòng duy nhất chứa các số nguyên \(n, b, c, d, M\) theo thứ tự.
• Dữ liệu vào đảm bảo \(0 \le b, c, d < M \le 10^7\); \(n \le 10^7\).

Output

• Ghi ra tệp văn bản LAP.OUT: Dòng duy nhất chứa giá trị cần tìm.

Example

5 2 3 1 6

5

Ràng buộc

• Subtask 1 (\(30\%\) số điểm): \(n, M \le 1000\).
• Subtask 2 (\(30\%\) số điểm): \(n, M \le 10^5\).
• Subtask 3 (\(40\%\) số điểm): không có ràng buộc gì thêm.