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

@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;
}

Новые блоги и статьи Все статьи Все блоги /
Doom для терминала без стрельбы и монстров. 3D Raycasting на ascii. dcc0 05.07.2026 Попросил нейронную сеть deepai. org написать рейкастинг 3D с библиотекой ncurses для Linux. Чтобы можно было ходить на стрелочки. Чтобы стены были отрисованы символами. Справилась. Первый вариант. . .	Установка статуса документа по условию Maks 05.07.2026 Алгоритм из решения ниже реализован на нетиповом документе "НарядПутевка" разработанного в КА2. Задача: в табличной части "Материалы" документа при записи автоматически устанавливать статус. . .	Сезонность и суточность закисления почв anaschu 04.07.2026 200 часов это все равно моловато. Есть ситуации, но нестандартные, когда смена происходит за 5 лет. Но обычно это 50 лет и более. Наверное, закисление почвы происходит сезонно в средней. . .	В чем ценность человеческого опыта в глобальном смысле? kumehtar 03.07.2026 Возможно, ценность человека не в том, что он однажды достигает мудрости, а в том, что он становится носителем карты пути. Он знает не только истину, но и последовательность внутренних изменений,. . .
интеграция AnyLogic с самописным REST API и переход на Odoo anaschu 03.07.2026 Успешная интеграция AnyLogic с самописным REST API и переход на промышленную Odoo WMS Сегодня проделал огромный путь от простой симуляции физических процессов до построения полноценной. . .	Поиск всех путей на ориентированном графе. Linux dcc0 02.07.2026 Переработка старого кода из моей статьи. Через несколько переработок от PHP кода к C89 (надеюсь, 89). Но довольно запутанно получилось. Код для Linux. Но если убрать time и то, что с ним. . .	Сам себя обучал rest api anaschu 02.07.2026 Педагогический лайфхак: Почему чистый REST API для ученика намного круче, чем готовые библиотеки Когда мы отказались от капризного JAR-файла AnyLogic и переписали код на стандартный HttpClient,. . .	rest api anylogic - выполнение модели на своём русском сайте anaschu 02.07.2026 Как подружиться с AnyLogic Cloud API, победить провайдеров и развернуться Java-бэкенд в Docker на бесплатном хостинге: Двухдневный лог борьбы Всем привет! Хочу поделиться свежим (и довольно. . .

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

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