1460. Double reverse

Given a sequence of positive integers 1, 2, 3, ..., n. Arrange first in reverse order the part of this sequence starting from the element with number a to the element with number b, and then reverse the subsequence starting from element with number c to the element with number d.

Input. Given the integers n (1 ≤ n ≤ 1000), a, b, c, d (a < b, c < d, 1 ≤ a, b, c, d ≤ 1000).

Output. Print the resulting sequence.

Sample input	Sample output
9 2 5 6 9	1 5 4 3 2 9 8 7 6

SOLUTION

arrays

Algorithm analysis

In this problem we need to reverse twice the part of array. This can be done for example with the help of two pointers. One pointer is set at the beginning of segment to be reversed, and the second is set at the end. The pointers run towards each other, swapping the items where they point.

Algorithm realization

Read the input data.

scanf("%d %d %d %d %d",&n,&a,&b,&c,&d);

Fill array m with numbers from 1 till n.

for(i = 1; i <= n; i++) m[i] = i;

Reverse the subarray m[a … b].

for(; a < b; a++, b--)

temp = m[a], m[a] = m[b], m[b] = temp;

Reverse the subarray m[c … d].

for(; c < d; c++, d--)

temp = m[c], m[c] = m[d], m[d] = temp;

Print the resulting array.

printf("%d",m[1]);

for(i = 2; i <= n; i++) printf(" %d",m[i]);

printf("\n");

Realization with while loop

#include <stdio.h>

int i, n, a, b, c, d, temp;

Declare the array.

int m[1010];

int main(void)

{

Read the input data.

scanf("%d %d %d %d %d",&n,&a,&b,&c,&d);

Fill array m with numbers from 1 till n.

for(i = 1; i <= n; i++)

m[i] = i;

Reverse the subarray m[a … b].

while(a < b)

{

temp = m[a]; m[a] = m[b]; m[b] = temp;

a++; b--;

}

Reverse the subarray m[c … d].

while(c < d)

{

temp = m[c]; m[c] = m[d]; m[d] = temp;

c++; d--;

}

Print the resulting array.

for(i = 1; i <= n; i++)

printf("%d ",m[i]);

printf("\n");

return 0;

}

Realization with memory allocation

#include <stdio.h>

int i, n, a, b, c, d, temp;

int *m;

void swap(int &i, int &j)

{

int temp = i;

i = j;

j = temp;

}

int main(void)

{

scanf("%d %d %d %d %d",&n,&a,&b,&c,&d);

m = new int[n+1];

for(i = 1; i <= n; i++) m[i] = i;

for(; a < b; a++, b--)

swap(m[a],m[b]);

for(; c < d; c++, d--)

swap(m[c],m[d]);

printf("%d",m[1]);

for(i = 2; i <= n; i++) printf(" %d",m[i]);

printf("\n");

delete[] m;

return 0;

}

Java realization

import java.util.*;

public class Main

{

public static void swap(int m[], int i, int j)

{

int temp = m[i];

m[i] = m[j]; m[j] = temp;

}

public static void main(String[] args)

{

Scanner con = new Scanner(System.in);

int n = con.nextInt();

int a = con.nextInt(), b = con.nextInt();

int c = con.nextInt(), d = con.nextInt();

int m[] = new int[n + 1];

for(int i = 1; i <= n; i++)

{

m[i] = i;

}

for(; a < b; a++, b--)

{

swap(m,a,b);

}

for(; c < d; c++, d--)

{

swap(m,c,d);

}

for(int i = 1; i <= n; i++)

{

System.out.printf("%d ",m[i]);

}

}

}