1460. Двойной переворот

Дана последовательность натуральных чисел 1, 2, 3, ..., n. Необходимо сначала расположить в обратном порядке часть этой последовательности от элемента с номером a до элемента с номером b, а потом – от элемента с номером c до элемента с номером d.

Вход. Целые числа n (1 ≤ n ≤ 1000), a, b, c, d (a < b, c < d, 1 ≤ a, b, c, d ≤ 1000).

Выход. Вывести полученную последовательность.

Пример входа	Пример выхода
9 2 5 6 9	1 5 4 3 2 9 8 7 6

РЕШЕНИЕ

массивы

Анализ алгоритма

В задаче следует дважды промоделировать обращение части массива. Это можно например сделать при помощи двух указателей. Один указатель ставим на начало инвертируемого отрезка, а второй – на конец. Указатели начинают сходиться друг к другу, меняя местами элементы m[a] и m[b], на которые они указывают.

Реализация алгоритма

Объявим рабочий массив.

int m[1010];

Читаем входные данные.

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

Заполняем массив m числами от 1 до n.

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

Обращаем отрезок m[a … b] массива.

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

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

Обращаем отрезок m[c … d] массива.

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

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

Выводим полученный массив.

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

printf("\n");

Реализация с использованием while цикла

#include <stdio.h>

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

Объявим рабочий массив.

int m[1010];

int main(void)

{

Читаем входные данные.

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

Заполняем массив m числами от 1 до n.

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

m[i] = i;

Обращаем отрезок m[a … b] массива.

while(a < b)

{

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

a++; b--;

}

Обращаем отрезок m[c … d] массива.

while(c < d)

{

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

c++; d--;

}

Выводим полученный массив.

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

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

printf("\n");

return 0;

}

Реализация с выделением памяти

#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;

}

Реализация STL reverse

#include <cstdio>

#include <algorithm>

using namespace std;

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

int *m;

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;

reverse(m+a,m+b+1); // m[a..b]

reverse(m+c,m+d+1); // m[c..d]

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

printf("\n");

delete[] m;

return 0;

}

Реализация STL vector reverse

#include <cstdio>

#include <vector>

#include <algorithm>

using namespace std;

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

vector<int> m;

int main(void)

{

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

m.resize(n+1);

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

reverse(m.begin()+a,m.begin()+b+1); // m[a..b]

reverse(m.begin()+c,m.begin()+d+1); // m[c..d]

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

printf("\n");

return 0;

}

Java реализация

import java.util.*;

public class Main

{

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--)

{

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

}

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

{

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

}

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

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

con.close();

}

}

Java реализация – swap

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]);

}

}

}

Java реализация – class Array

import java.util.*;

class Array

{

ArrayList<Integer> m;

Array(int n)

{

m = new ArrayList<Integer>(Collections.nCopies(n, 0));

}

public void set(int index, int value)

{

m.set(index,value);

}

public void Reverse(int i, int j)

{

while(i < j)

{

Collections.swap(m,i,j);

i++; j--;

}

}

public void Print()

{

for(int i = 1; i < m.size(); i++)

System.out.print(m.get(i) + " ");

System.out.println();

}

};

public class Main

{

public static void main(String[] args)

{

Scanner con = new Scanner(System.in);

int n = con.nextInt();

int a = con.nextInt();

int b = con.nextInt();

int c = con.nextInt();

int d = con.nextInt();

Array m = new Array(n+1);

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

m.set(i,i);

// Reverse an array

m.Reverse(a,b);

m.Reverse(c,d);

// Print the reversed array

m.Print();

con.close();

}

}