VOI 09 Bài 3 - Đường lên Bái Đính

View as PDF

Submit solution

Points: 1.01 (partial)
Time limit: 0.38s
Memory limit: 512M
Input: stdin
Output: stdout

Problem source:
Thi HSG Quốc gia 2009
Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Đầu năm mới Kỷ Sửu tượng phật ở chùa Bái Đính - ngôi chùa to nhất Đông Nam Á đã được làm lễ nhập thần. Chùa Bái Đính nằm ở trên một ngọn đồi cao, có đường bậc thang dẫn từ chân đồi lên gồm ~n~ bậc. Để làm tăng ý nghĩa tâm linh của khu chùa người ta thiết kế đặt các tượng ở các bậc thang, mỗi bậc thang đặt ba bức tượng: một bức đặt ở giữa và hai bức đặt ở hai bên. Hai bên là hai dãy tượng của các vị cao tăng, có người chắp tay đón chào phật tử về hành hương vãn cảnh chùa, có người cầm một số nén nhang. Giữa đường đi là dãy tượng của các tín đồ, một số người chắp tay, một số người khác có cầm trong tay vài thẻ hương đón chào khách hành hương. Số thẻ hương hoặc nén nhang ở mỗi bức tượng là không quá 9.

image

Ý tưởng của nhà Phật là nếu nhìn từ dưới chân đồi lên số nén nhang mà mỗi vị cao tăng cầm được hiểu như một chữ số hệ đếm thập phân, những tượng chắp tay biểu diễn số 0. Hai dãy các chữ số tương ứng với số nén nhang mà các vị cao tăng cầm trên tay ở hai dãy tượng cao tăng sẽ tạo thành hai số, mỗi số có ~n~ chữ số tượng trưng cho lượng từ bi mà Đức Phật ban phát. Khi đi từ dưới lên, hai vị cao tăng đầu tiên ở cả hai bên đều cầm nhang. Số thẻ hương tín đồ cầm cũng tượng trưng cho chữ số bằng số thẻ hướng trên tay, những tượng không cầm hương thể hiện chữ số 0. Những tượng tín đồ đứng đầu có thể có hoặc không cầm hương. Dãy số nguyên tương ứng với số thẻ hương trong tay các tín đồ của dãy tượng các tín đồ cũng tương ứng với một số nguyên tượng trưng cho nỗi khổ của chúng sinh.

Bản thiết kế được thực hiện rất công phu, mỗi bức tượng một dáng vẻ riêng, sống động và thành kính. Tuy vậy, sau khi xem nhà sư trụ trì có ý kiến: - A di đà phật, Bần tăng muốn khi đọc từ dưới lên số thể hiện nỗi khổ của chúng sinh phải nhỏ nhất nhưng vẫn lớn hơn số thể hiện lượng từ bi của Đức Phật ở mỗi dãy, nhưng khi đứng từ trên xuống các phật tử phải thấy được rằng lượng từ bi của Đức Phật ở mỗi dãy đều lớn hơn nỗi khổ chúng sinh. Bần tăng cũng không muốn làm lại tượng, cũng không muốn làm phiền các vị cao tăng mà chỉ muốn thay đổi chỗ đặt tượng các tín đồ. Các thí chủ có thể làm điều đó giúp nhà chùa được hay không? A di đà phật.

Ví dụ, gọi các số thể hiện lượng từ bi là ~A~ và ~B~, số thể hiện nỗi khổ chúng sinh là ~C~ và trên bảng thiết kế hiện tại ~A = 342876115, B = 468862513, C = 992125619~. Để thỏa mãn điều kiện của nhà sư trụ trì, các tượng tín đồ cần được đổi chỗ để thể hiện số ~511269992~ bởi vì khi đó ta có:

  • ~511269992 > 342876115~; ~511269992 > 468862513~;
  • ~299962115 < 511678243~; ~299962115 < 315268864~.

Yêu cầu: Cho các số nguyên ~A, B, C~, mỗi số có ~n~ chữ số. A và B bắt đầu bởi chữ số khác 0, còn ~C~ có thể được bắt đầu bằng một hay nhiều chữ số 0. Hãy xác định xem có cách đổi chỗ các chữ số trong ~C~ để nhận được số mới thỏa mãn điều kiện của nhà sư trụ trì đã nêu hay không. Hãy đưa ra số mới, nếu có cách đổi chỗ hoặc đưa ra -1 trong trường hợp ngược lại.

image

Input

  • Dòng đầu tiên chứa số nguyên ~n~ ~(2 \leq n \leq 200000)~;
  • Dòng thứ hai chứa số nguyên ~A~;
  • Dòng thứ ba chứa số nguyên ~B~;
  • Dòng thứ tư chứa số nguyên ~C~.

Output

  • Một dòng chứa số mới nhận được từ ~C~ hoặc -1 trong trường hợp vô nghiệm.

Giới hạn

60% số tests ứng với 60% số điểm của bài có ~2 \leq n \leq 10~.

Sample Input

9
342876115
468862513
992125619

Sample Output

511269992

Note

image


Comments

Please read the guidelines before commenting.


There are no comments at the moment.