Permeowtation 3

View as PDF

Submit solution

Points: 0.20 (partial)
Time limit: 1.0s
Memory limit: 256M
Input: stdin
Output: stdout

Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

To read the problem statement in English, choose the language using the flag on the navigation bar.

Sau khi các thần dân đã được tiêm ngừa vaccine đầy đủ, đại dịch COVID-19 trên hành tinh mèo đã được đẩy lùi và cuộc sống dần ổn định trở lại. Để ăn mừng chiến thắng đại dịch, quốc vương hành tinh mèo đã tổ chức đại hội thể thao với nhiều môn thể thao khác nhau, trong đó có bộ môn Permeowtation (do Neko sáng tạo ra) với luật chơi như sau:

Ban đầu, vận động viên (VĐV) sẽ được cho hai hoán vị ~a~ và ~b~ có cùng độ dài ~n~. VĐV cần tiến hành trộn hai hoán vị với nhau để tạo ra dãy ~c~ gồm ~2 \cdot n~ phần tử như sau:

  • Ban đầu, dãy ~c~ không chứa phần tử nào.

  • VĐV thực hiện ~2\cdot n~ bước. Ở mỗi bước cần chọn dãy ~a~ hoặc dãy ~b~, rồi xóa phần tử đầu tiên khỏi dãy được chọn và thêm phần tử này vào cuối dãy ~c~. Lưu ý rằng, dãy được chọn cần có ít nhất một phần tử.

VĐV sẽ giành được tấm huy chương cao quý từ liên đoàn thể thao hành tinh mèo, nếu như dãy ~c~ mà VĐV tạo ra không có hai phần tử liên tiếp nào trùng nhau. Nói cách khác, VĐV cần tạo ra dãy ~c~ thỏa mãn với mọi ~1 \le i < 2 \cdot n~, ~c_i \ne c_{i + 1}~.

Mike, một trong những VĐV trẻ tuổi của bộ môn này, đã luyện tập rất chăm chỉ để có sự chuẩn bị tốt nhất. Tuy nhiên, trước áp lực sân khấu, cô đang cảm thấy rất hồi hộp và không còn nhớ cách để giành chiến thắng. Hãy giúp cô hoàn thành trò chơi này và giành được tấm huy chương nhé.

Định nghĩa. Hoán vị là một mảng số nguyên gồm ~n~ phần tử khác nhau từ ~1~ đến ~n~ theo thứ tự bất kì. Ví dụ, ~[2,3,1,5,4]~ là một hoán vị, nhưng ~[1,2,2]~ không phải là một hoán vị (giá trị ~2~ được lặp lại hai lần trong mảng) và ~[1,3,4]~ cũng không phải là hoán vị (độ dài mảng là ~n=3~ nhưng trong mảng có phần tử ~4~).

Input

Dòng đầu tiên gồm số nguyên ~n~ (~2 \le n \le 10^5~) là độ dài của hai hoán vị ~a~ và ~b~.

Dòng thứ hai gồm ~n~ số nguyên phân biệt ~a_1, a_2, \ldots, a_n~ (~1 \le a_i \le n~).

Dòng thứ ba gồm ~n~ số nguyên phân biệt ~b_1, b_2, \ldots, b_n~ (~1 \le b_i \le n~).

Output

In ra chuỗi gồm ~2n~ kí tự a hoặc b. Kí tự thứ ~i~ cho biết dãy cần được lựa chọn ở bước thứ ~i~.

Có thể chỉ ra rằng đáp án luôn tồn tại với giới hạn đề bài cho.

Scoring

  • Subtask 1, tương ứng với ~15~ điểm, có ~n = 2~

  • Subtask 2, tương ứng với ~15~ điểm ~n \le 10~

  • Subtask 3, tương ứng với ~20~ điểm, Không có giới hạn gì thêm

Tổng cộng bài toán có ~50~ điểm.

Sample Input 1

3
1 2 3
3 2 1

Sample Output 1

abaabb

Sample Input 2

2
2 1
1 2

Sample Output 2

baab

Notes

Ở ví dụ đầu tiên đã cho, dãy ~a~ có giá trị ~[1, 2, 3]~ và dãy ~b~ có giá trị ~[3, 2, 1]~.

Với cách tạo dãy ~c~ ở output, ta thu được dãy ~[1, 3, 2, 3, 2, 1]~.


Comments

Please read the guidelines before commenting.