11388. Cards game 2
Huseyn arranged n cards in
a row with numbers a1, a2, a3,
..., an. Then he collected them and rearranged them in a
different order: a1, a3, a5,
..., a6, a4, a2. This is the sequence he gave to Yaroslav.
Your task is to help Yaroslav restore Hussein's original sequence.
For example, if Yaroslav received the
sequence (2, 4, 9, 4, 7, 6), then he should return the sequence (2, 6, 4, 7, 9, 4) to Huseyn.
Input. The first line contains one integer n (1 ≤ n ≤ 10000), representing the number of cards. The
second line contains n positive integers written on the cards. All
numbers are no greater than 109.
Output. Print Huseyn’s original sequence.
|
Sample
input 1 |
Sample output 1 |
|
6 2 4 9 4 7 6 |
2 6 4 7 9 4 |
|
|
|
|
Sample
input 2 |
Sample output 2 |
|
7 5 7 34 1 89 4 2 |
5 2 7 4 34 89 1 |
SOLUTION
two pointers
Algorithm analysis
Let the
array a contain the numbers written on the cards. Initialize two
pointers: i = 0 at the
beginning of the array and j = n – 1 at its end.
To restore the original
sequence, alternately take cards from the left and the right until all elements
have been processed. With each selection, the corresponding pointer changes its
position: i moves to
the right, j moves
to the left.
Example
Let’s consider a few steps
of the algorithm using the first test case as an example.
Algorithm realization
Declare
an array.
int a[100001];
Read
the input data.
scanf("%d", &n);
for (i = 0; i < n; i++)
scanf("%d", &a[i]);
Set the pointers i = 0 and j = n – 1.
i = 0; j = n - 1;
While the inequality i ≤ j holds,
alternately print a[i] and a[j], simultaneously
moving the pointers.
while (i <= j)
{
printf("%d ", a[i++]);
if (i > j) break;
printf("%d ", a[j--]);
}