Циклически сдвинуть целочисленную последовательность

@Haker Cat · Регистрация: 09.06.2024

Студворк — интернет-сервис помощи студентам

Дана последовательность из N (1 ≤ N ≤ 100000) целых чисел и число K (|K| ≤ 100000). Сдвинуть всю последовательность (сдвиг - циклический) на |K| элементов вправо, если K – положительное и влево, если отрицательное.

В данной задаче нельзя использовать дополнительные массивы (списки).
Входные данные

В первой строке дано натуральное число N, во второй строке N целых чисел, а в последней целое число K. Все числа во входных данных не превышают 109.
Выходные данные

Требуется вывести полученную последовательность.
Примеры
Входные данные

5
5 3 7 4 6
3

Выходные данные

7 4 6 5 3

У меня код есть, но плохой

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include <iostream>
using namespace std;
 
const int BUF_SIZE = 35;
int a[BUF_SIZE];
int n, k, s;
int main()
{
    cin >> n;
    for (int i = 0; i < n; ++i)
    {
        cin >> a[i];
    }
    cin >> k;
    if (k < 0)
    {
        for (int i = 0; i > k; i--)
        {
            s = 0;
            for (int i = 1; i < n; i++)
            {
                s = a[0];
                a[i] = a[i-1];
            }
            a[n] = s;
        }
        for (int i = 0; i < n; ++i)
        {
            cout << a[i] << " ";
        }
    }
    else if (k > 0)
    {
        for (int i = 0; i < k; i++)
        {
            s = 0;
            for (int i = 1; i < n; i++)
            {
                s = a[0];
                a[i] = a[i-1];
            }
            a[n] = s;
        }
        for (int i = 0; i < n; ++i)
        {
            cout << a[i] << " ";
        }
    }
    else
    {
        for (int i = 0; i < n; ++i)
        {
            cout << a[i] << " ";
        }
    }
    return 0;
}

P.S. Помогите, пожалуйста

Алексей1153 · 10.03.2025, 07:27

Сообщение от gunslinger

P.S.: не совсем понял фразу из задания
Обратите внимание, что нужно именно преобразовать имеющийся список и распечатать его целиком

видимо, это пытались подстраховаться от

Сообщение от VTsaregorodtsev

но проверяться будет не содержимое массива, а только лишь выведенные данные.

Но возможности проверить это у них, видимо, нету

Добавлено через 50 секунд

Сообщение от Haker Cat

а как

в смысле, как ? Не использовать их

@SmallEvil · 10.03.2025, 07:42

Сообщение от Алексей1153

Но возможности проверить это у них, видимо, нету

Потому что система проверяет результат из стандартного потока вывода.
А не тестирует часть кода, как на leetcode или codewars.
Например, шаблон клиентского кода :

C++
1
2
3
4
struct Exam{
   vector<int> super_shift(vector<int> arr, int k){
   }
]

Конечно, большинство будет использовать готовый алгоритм из STL, так как задача, можно сказать, тривиальная.

Алексей1153 · 10.03.2025, 07:52

Сообщение от SmallEvil

Потому что система проверяет результат из стандартного потока вывода.

это понятно

Сообщение от SmallEvil

Конечно, большинство будет использовать готовый алгоритм из STL

а вот это можно и запретить принудительным удалением заголовков из кода

@SmallEvil · 10.03.2025, 07:58

Сообщение от Алексей1153

а вот это можно и запретить принудительным удалением заголовков из кода

Теоретически, наверное можно, если поставить себе такую цель.
Но что помешает просто скопировать готовый алгоритм?
Обучаться в первую очередь нужно ученику.

Добавлено через 3 минуты
Ну схитрит ученик один раз, десять, сто.
"Прогуляет" половину занятий.
Когда придет пора к сложному комплексному заданию, тут и писец подкрадется.

Алексей1153 · 10.03.2025, 08:26

SmallEvil, кто желает сам обучаться, ему системы тестирования и не нужны

@SmallEvil · 10.03.2025, 09:25

Сообщение от Алексей1153

кто желает сам обучаться, ему системы тестирования и не нужны

Вообще-то, они не лишние.
Не нужно искать задачи.
Самому тесты писать не нужно, уже всё готовенькое.
Бери и практикуйся.

@gunslinger · 10.03.2025, 18:01

Сообщение от gunslinger

Нужно сделать замену элементов массива?
Если да, то, полагаю, это не должно быть (наверно) слишком сложно. Нужно будет просто где-то (временно) хранить заменяемые элементы, пока они нужны (для дальнейшей замены). Только не в массиве (что запрещено), а в переменных.

Я тут посидел (поседел), подумал. Не так это просто сделать через переменные. В худшем случае понадобится как минимум N / 2 переменных (если не ошибаюсь; иначе поправьте). Так что задача с подвохом.
Запрет на доп. массив понятен, но ограничение в 16 МБ памяти выглядит "случайным" - в моем решении используется максимум около 6 МБ, судя по тестам.

Добавлено через 1 час 2 минуты
Вот вариант для только неотрицательных или только неположительных элементов:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <iostream>
using namespace std;
 
int main()
{
  unsigned n;
  cin >> n;
 
  long long *a = new long long[n];
  for (unsigned i = 0; i < n; i++)
    cin >> a[i];
 
  int k;
  cin >> k;
 
  unsigned rem = abs(k) % n;
  if (k > 0)
    rem = n - rem;
 
  const int tmp = 1e9;
  for (unsigned i = 0; i < n; i++)
    a[i] = (a[(rem + i) % n] % tmp) * tmp + a[i] % tmp;
 
  for (unsigned i = 0; i < n; i++)
  {
    a[i] /= tmp;
    cout << a[i] << " ";
  }
 
  delete[] a;
  cout << endl;
  system("pause");
  return 0;
}

Тестирующая система решение засчитывает (видимо, там для проверки не используются числа с разными знаками).
А вот как сделать для общего случая (числа с разными знаками) - пока вопрос.

Добавлено через 1 час 34 минуты
Предыдущий код не учитывал, что числа могут принимать значение 10⁹.
Следующий код это "учитывает" (частично), но возможны переполнения (при большИх получаемых значениях на границе long long).
Также можно вводить числа с разными знаками.
Короче, решение абсолютно костыльное и мне не нравится (но как есть).

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include <iostream>
using namespace std;
 
int main()
{
  unsigned n;
  cin >> n;
 
  long long *a = new long long[n];
  for (unsigned i = 0; i < n; i++)
    cin >> a[i];
 
  int k;
  cin >> k;
 
  unsigned rem = abs(k) % n;
  if (k > 0)
    rem = n - rem;
 
  const long long tmp = 1e10, tmp2 = 2 * tmp / 10;
  long long x, y;
  bool sign;
  for (unsigned i = 0; i < n; i++)
  {
    x = a[(rem + i) % n] % tmp;
    if (x <= -tmp2)
      x += tmp2, x = -x;
    else if (x >= tmp2)
      x -= tmp2, x = -x;
 
    y = a[i] % tmp;
    if (y <= -tmp2)
      y += tmp2, y = -y;
    else if (y >= tmp2)
      y -= tmp2, y = -y;
 
    sign = (x < 0 && y > 0 || x > 0 && y < 0);
    a[i] = x * tmp + (sign ? -y : y);
    if (sign)
      a[i] += (y > 0 ? -tmp2 : tmp2);
  }
 
  for (unsigned i = 0; i < n; i++)
  {
    a[i] /= tmp;
    cout << a[i] << " ";
  }
 
  delete[] a;
  cout << endl;
  system("pause");
  return 0;
}

@Kuzia domovenok · 12.03.2025, 11:53

я что-то не понял, а почему самого доступного для понимания новичком алгоритма нет?

C++
1
2
3
4
5
6
7
for (shift = 0; shift < k; ++shift) { //к раз
  //сдвиг на 1 всего массива
  last = arr[n-1];
  for (elem = n-1; elem >0; ++elem)
     arr[elem] = arr[elem-1];
  arr[0] = last;
}

самое то для обучения

@SmallEvil · 12.03.2025, 12:56

Сообщение от Kuzia domovenok

а почему самого доступного для понимания новичком алгоритма нет?

Есть упоминание по ссылкам #14 вместе с указанием неэффективности такого подхода.
Это как умножать циклом суммируя умножаемое.

С возвращением.

@gunslinger · 13.03.2025, 06:33

Еще есть бредовая идея - изначально создать массив в 2 раза большего размера.
В первой половине разместить исходные N чисел, а во второй - те же данные, но со сдвигом.
В конце выводить вторую половину массива.
Мы же не используем доп. массив? Или это наглое читерство?

@gunslinger · 15.03.2025, 01:20

Вот вариант (тесты проходит) на основе приведенного выше поста Как сдвинуть массив влево?
Пытался сам до подобного догадаться (точнее, реализовать, догадка была, но с движением в другую сторону), но не получилось (ICQ не позволяет).

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <iostream>
using namespace std;
 
int main()
{
  unsigned n;
  cin >> n;
 
  long *a = new long[n];
  for (unsigned i = 0; i < n; i++)
    cin >> a[i];
 
  int k;
  cin >> k;
 
  unsigned rem = abs(k) % n;
  if (k > 0)
    rem = n - rem;
 
  unsigned old_index, new_index, value, count = 0, i = 0;
  if (k != 0)
    while (count < n)
    {
      old_index = i;
      value = a[i];
      while (i != (new_index = (old_index + rem) % n))
      {
        a[old_index] = a[new_index];
        old_index = new_index;
        count++;
      }
      a[old_index] = value;
      count++;
      i++;
    }
 
  for (unsigned i = 0; i < n; i++)
    cout << a[i] << " ";
 
  cout << endl;
  delete[] a;
  system("pause");
  return 0;
}

Новые блоги и статьи Все статьи Все блоги /
Программное добавление префикса в нумерацию документов Maks 27.10.2026 Реализация из решения ниже выполнена в самописной конфигурации на БСП (помощь начинающему коллеге). Задача: Программно добавить префикс в нумерацию документов. Решение: В модуле объекта. . .	После закрытия оутлука продолжает висеть процесс в диспетчере задач Maks 27.10.2026 С недавнего времени в продакшене возникла проблема: при закрытии оутлука в диспетчере задач продолжал висеть процесс outlook. exe. Проблема возникла после установки MS Office 2021 LTSC на машинах, под. . .	Baragoz - DPS/HPS бот для WoW 3.3.5a, многоязычный AmbA 26.10.2026 Хотите ещё ботов? У меня есть один! А я пока отдохну от него. https:/ / www. cyberforum. ru/ blog_attachment. php?attachmentid=12062&stc=1&d=1793007952 Инструкция внутри. https:/ / youtu. be/ VpfFZSUDGnQ. . .	Особенности gif сгенерированных в Си russiannick 21.10.2026 Рассмотрим генерацию gif файлов, которые в Си имеют свои особенности. Gif представляет собой графический формат популярный в интернете. Посмотрим на палитру. Gif файл сгенерированный в си отличается. . .
FPS контроллер с анимированными Y-Bot и 3D-звуком miniaudio (Box3D, Recast, BehaviorTree.CPP, ozz-animation, ImGui, OpenGL и SDL3) 8Observer8 18.10.2026 Содержание блога \| English Version Полное мультиплатформенное руководство по стартовому проекту с FPS-контроллером игрока, анимированными роботами Y-Bot с 4-слойным блендингом, 3D-физикой Box3D,. . .	Локальный http сервер Argus19 17.10.2026 Локальный http сервер На работе, на двух локальных компьютерах круглосуточно работают программы опроса приборов с записью в книги Excel,которые раз в сутки записываются на сервер компании. Т. к. . . .	Копировать Windows на новый диск на UEFI damix 17.10.2026 https:/ / uriesk. wordpress. com/ 2016/ 11/ 01/ move-window-10-to-ssd-on-a-uefi-dualboot-system-with-basic-linux-tools/ TL DR Вставляем диск, а старый подключаем через переходник, грузимся с лайва. . .	ИИ не может найти нужный язык в списке Supersumestria 05.10.2026 Я ему даю вот такое изображение и прошу найти и подчеркнуть немецкий язык. Возвращает он вот это: https:/ / i. **********/ vqBWLe2. png Нужную строчку в 3й колонке просто выдумал. . Это. . .

Алексей1153 фрилансер 6510 / 5769 / 1135 Регистрация: 11.10.2019 Сообщений: 15,410
	10.03.2025, 08:26
	SmallEvil, кто желает сам обучаться, ему системы тестирования и не нужны 0

@gunslinger place status here 3192 / 2227 / 640 Регистрация: 20.07.2013 Сообщений: 6,028
	13.03.2025, 06:33
	Еще есть бредовая идея - изначально создать массив в 2 раза большего размера. В первой половине разместить исходные N чисел, а во второй - те же данные, но со сдвигом. В конце выводить вторую половину массива. Мы же не используем доп. массив? Или это наглое читерство? 0