University of Toronto ACM-ICPC Tryouts 2012

B: Interleaving Leaves

Leafy Lee likes leaves. He also likes interleaving things. So he definitely likes interleaving leaves.

Lee starts with two piles of N (1 ≤ N ≤ 1000) leaves each, and wants to combine them into one new pile. He'll start by taking the top leaf of the first pile, then putting the top leaf of the second pile on top of it, then the next leaf from the first on top of those, then the next leaf from the second, and so on. In this way, Lee will end up with a single pile containing 2N leaves.

Every leaf has a (possibly non-unique) type, which can be represented as an uppercase letter. A pile of leaves can then be described as a string, giving the types of its leaves from top to bottom.

There are T (1 ≤ T ≤ 20) scenarios as described above. For each, given the two initial piles of leaves in the above format, Lee would like to predict the contents of the interleaved pile, in the same format.

Input

Line 1: 1 integer, T
For each scenario:
Line 1: 1 integer, N
Line 2: N uppercase letters, describing the leaves in the first pile
Line 3: N uppercase letters, describing the leaves in the second pile

Output

For each scenario:
Line 1: 2N uppercase letters, describing the leaves in the final pile

Sample Input

2
1
A
B
3
ZEO
NXF

Sample Output

BA
FOXENZ

Explanation of Sample

In the first scenario, Lee will put down the A leaf first, and then the B leaf on top of it. The resulting pile, then, will contain leaves BA from top to bottom.

In the second scenario, Lee will put down the Z from the first pile, followed by the N from the second pile, followed by the E from the first pile, and so on. The final pile will contain leaves FOXENZ from top to bottom.

All Submissions
Best Solutions


Point Value: 5
Time Limit: 5.00s
Memory Limit: 64M
Added: Oct 02, 2012
Author: SourSpinach

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)

Are the two strings N length? The problem description says so, but when I try to use a for loop to output the two strings it gives me RE.
When I use a stack it returns me AC.
It seems like the strings are not the same length.

Whateva.

It's a word of adulation for The Great Fox.

I forgot what I was just about to say.

When I run the sample case it seems correct but the judge gives me 0/1 and weird things come up (============8 or something)

Your algorithm is correct, but you need to be careful reading input.
See: http://wcipeg.com/comments/view#comment3719

I saw, what you were trying to make the text look like!