Разбиение массива

@RafaProfa · Регистрация: 22.11.2015

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

Рассмотрим множество целых чисел от 1 до 3n. Необходимо распределить эти числа в три массива a, b и c длиной n так, чтобы для любого i от 1 до n выполнялось следующее: a_i + b_i = c_i

Формат входных данных

Единственная строка содержит целое число n (1 ≤ n ≤ 23).

Формат выходных данных

Если решения не существует, то в первой строке выведите единственное число -1. В ином случае, выведите 3 строки, в каждой по n целых чисел, разделенных пробелами. В первой строке должны находиться элементы массива a, во второй – элементы массива b, в третьей – массива c. Каждое число от 1 до 3n должно быть выведено ровно один раз.

Пример входных данных
1

Пример выходных данных
1
2
3
Что предлагаете господа?

echs · 20.01.2017, 17:01

RafaProfa
Мне понравилась ваша задача и я решил немного ее
исследовать. Вот пока первый шаг.
1. Сумма всех элементов массива с() равна сумме всех
элементов остальных массивов. То есть сумма вообще
всех элементов есть число чётное
2. Посмотрим, что это нам даёт.
n = 2 , сумма чисел от 1 до 6 равна 21 (число нечетное - отпадает)
n = 3 , сумма чисел от 1 до 9 равна 45 (число нечетное - отпадает)
Аналогичным образом вы можете отбросит числа n = 6, 7, 10, 11, ...
Значит надо посмотреть, что делать с числами n = 4, 5, 8, 9, ...
...
это первый шаг, пошел писать программу, может на подскажет
второй шаг... в общем надо подумать...

Добавлено через 1 час 26 минут
RafaProfa

Вот написал программу и нашел пару результатов
при n = 4 программа выдала числа (массивы)
4 + 8 = 12
6 + 3 = 9
5 + 2 = 7
10 + 1 = 11
...
при n = 5 (такой вывод)
5 + 9 = 14
6 + 2 = 8
3 + 7 =10
12 + 1 = 13
11 + 4 = 15
...
конечно можно считать и дальше, но очевидно, что
1 принадлежит массивам-слагаемым, а наибольшее
число массиву-сумме.
Аналитического выражения я пока не нашел. Это надо
взять ручку и попробовать на бумаге...
... надо ещё подумать...

QBasic/QuickBASIC
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
REM 1, 2, ..., 3n
 
CLS
CONST n = 5
n2 = 2 * n
n3 = 3 * n
 
DIM x(1 TO n)
DIM y(1 TO n)
DIM z(1 TO n)
DIM u(1 TO 3 * n)
 
FOR i = 1 TO n3
   u(i) = i
NEXT
 
DO
   FOR i = 1 TO n3
      j = INT(n3 * RND) + 1
      SWAP u(i), u(j)
   NEXT
 
   FOR i = 1 TO n3
      IF i <= n THEN
         x(i) = u(i)
      ELSEIF i <= n2 THEN
         y(i - n) = u(i)
      ELSE
         z(i - n2) = u(i)
      END IF
   NEXT
 
   FOR i = 1 TO n
      IF x(i) + y(i) <> z(i) THEN 100
   NEXT
 
   FOR i = 1 TO n
      PRINT x(i); y(i); z(i)
   NEXT
   END
100
LOOP
END

@RafaProfa · 20.01.2017, 21:33 **[ТС]**

echs, Я пытался найти какую-то закономерность и решить методом динамического программирования, но ничего не нашел. А так задача очень хорошая. Если хотите проверить ваше решение, то можете здесь http://informatika.edu.az/task... ail&id=429(переключитесь наверху сайта на русский язык и пройдите регистрацию, она быстрая, потом опять откройте эту ссылку)

Добавлено через 20 минут
echs, Да и еще если считаете что ваша программа выдает правильный ответ, а на сайте не проходит проверку, то наверное дело в тестах к задаче, потому, что не написано в условии в каком порядке надо выводить сами числа(по возрастанию или как?). Да и еще я проверил что когда выводишь "1\n2\n3\n" проверку на первый тест не проходит, а когда выводишь "1 \n2 \n3 " проходит.

echs · 21.01.2017, 11:42

RafaProfa
Аналитическое решение пока не найдено. Но вот начало
Распишем найденные массивы при n = 4 и n = 5 в ином
порядке
1 + 10 = 11 (n = 4)
2 + 5 = 7
3 + 6 = 9
4 + 8 = 12
....
1 + 12 = 13 (n = 5)
2 + 6 = 8
3 + 7 = 10
4 + 11 = 15
5 + 9 = 14
...
Из этого видно, что первый массив можно задать натуральными
числами от 1 до n (ещё не доказательство, но всё-же)
Следующим числом, которое может пройти будет n = 8
Итак первый массив пусть состоит из чисел 1, 2, ..., 8
сумма его элементов равна 36. А общая сумма всех чисел (1, ...24)
равна 300. Значит сумма элементов третьего массива равна 150
А на второй массив остаётся сумма равная 150 - 36 = 114
...
То есть задача такая
Даны числа 9, 10, ..., 24 и требуется из них выбрать 8 таких,
чтобы их сумма равнялась 114.
...
надо написать еще программу для точного доказательства
верно это? или нет?

Байт · 21.01.2017, 14:50

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

не написано в условии в каком порядке надо выводить сами числа(по возрастанию или как?)

А зачем их вводить? Вводится только 1 число - n

@RafaProfa · 21.01.2017, 15:45 **[ТС]**

Байт,

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

Формат выходных данных
Если решения не существует, то в первой строке выведите единственное число -1. В ином случае, выведите 3 строки, в каждой по n целых чисел, разделенных пробелами. В первой строке должны находиться элементы массива a, во второй – элементы массива b, в третьей – массива c. Каждое число от 1 до 3n должно быть выведено ровно один раз.

Новые блоги и статьи Все статьи Все блоги /
Философия технологии iceja 01.02.2026 На мой взгляд у человека в технических проектах остается роль генерального директора. Все остальное нейронки делают уже лучше человека. Они не могут нести предпринимательские риски, не могут. . .	SDL3 для Web (WebAssembly): Вывод текста со шрифтом TTF с помощью SDL3_ttf 8Observer8 01.02.2026 Содержание блога В этой пошаговой инструкции создадим с нуля веб-приложение, которое выводит текст в окне браузера. Запустим на Android на локальном сервере. Загрузим Release на бесплатный. . .	SDL3 для Web (WebAssembly): Сборка C/C++ проекта из консоли 8Observer8 30.01.2026 Содержание блога Если вы откроете примеры для начинающих на официальном репозитории SDL3 в папке: examples, то вы увидите, что все примеры используют следующие четыре обязательные функции, а. . .	SDL3 для Web (WebAssembly): Установка Emscripten SDK (emsdk) и CMake для сборки C и C++ приложений в Wasm 8Observer8 30.01.2026 Содержание блога Для того чтобы скачать Emscripten SDK (emsdk) необходимо сначало скачать и уставить Git: Install for Windows. Следуйте стандартной процедуре установки Git через установщик. . . .
SDL3 для Android: Подключение Box2D v3, физика и отрисовка коллайдеров 8Observer8 29.01.2026 Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами. Версия v3 была полностью переписана на Си, в. . .	Инструменты COM: Сохранение данный из VARIANT в файл и загрузка из файла в VARIANT bedvit 28.01.2026 Сохранение базовых типов COM и массивов (одномерных или двухмерных) любой вложенности (деревья) в файл, с возможностью выбора алгоритмов сжатия и шифрования. Часть библиотеки BedvitCOM Использованы. . .	SDL3 для Android: Загрузка PNG с альфа-каналом с помощью SDL_LoadPNG (без SDL3_image) 8Observer8 28.01.2026 Содержание блога SDL3 имеет собственные средства для загрузки и отображения PNG-файлов с альфа-каналом и базовой работы с ними. В этой инструкции используется функция SDL_LoadPNG(), которая. . .	SDL3 для Android: Загрузка PNG с альфа-каналом с помощью SDL3_image 8Observer8 27.01.2026 Содержание блога SDL3_image - это библиотека для загрузки и работы с изображениями. Эта пошаговая инструкция покажет, как загрузить и вывести на экран смартфона картинку с альфа-каналом, то есть с. . .

@RafaProfa 3 / 3 / 1 Регистрация: 22.11.2015 Сообщений: 59

	Разбиение массива 18.01.2017, 17:49. Показов 793. Ответов 5 Метки нет (Все метки) Рассмотрим множество целых чисел от 1 до 3n. Необходимо распределить эти числа в три массива a, b и c длиной n так, чтобы для любого i от 1 до n выполнялось следующее: a_i + b_i = c_i Формат входных данных Единственная строка содержит целое число n (1 ≤ n ≤ 23). Формат выходных данных Если решения не существует, то в первой строке выведите единственное число -1. В ином случае, выведите 3 строки, в каждой по n целых чисел, разделенных пробелами. В первой строке должны находиться элементы массива a, во второй – элементы массива b, в третьей – массива c. Каждое число от 1 до 3n должно быть выведено ровно один раз. Пример входных данных 1 Пример выходных данных 1 2 3 Что предлагаете господа? 0

@RafaProfa 3 / 3 / 1 Регистрация: 22.11.2015 Сообщений: 59
	20.01.2017, 21:33 [ТС]
	echs, Я пытался найти какую-то закономерность и решить методом динамического программирования, но ничего не нашел. А так задача очень хорошая. Если хотите проверить ваше решение, то можете здесь http://informatika.edu.az/task... ail&id=429(переключитесь наверху сайта на русский язык и пройдите регистрацию, она быстрая, потом опять откройте эту ссылку) Добавлено через 20 минут echs, Да и еще если считаете что ваша программа выдает правильный ответ, а на сайте не проходит проверку, то наверное дело в тестах к задаче, потому, что не написано в условии в каком порядке надо выводить сами числа(по возрастанию или как?). Да и еще я проверил что когда выводишь "1\n2\n3\n" проверку на первый тест не проходит, а когда выводишь "1 \n2 \n3 " проходит. 1

echs Регистрация: 23.10.2013 Сообщений: 5,076 Записей в блоге: 8
	21.01.2017, 11:42
	RafaProfa Аналитическое решение пока не найдено. Но вот начало Распишем найденные массивы при n = 4 и n = 5 в ином порядке 1 + 10 = 11 (n = 4) 2 + 5 = 7 3 + 6 = 9 4 + 8 = 12 .... 1 + 12 = 13 (n = 5) 2 + 6 = 8 3 + 7 = 10 4 + 11 = 15 5 + 9 = 14 ... Из этого видно, что первый массив можно задать натуральными числами от 1 до n (ещё не доказательство, но всё-же) Следующим числом, которое может пройти будет n = 8 Итак первый массив пусть состоит из чисел 1, 2, ..., 8 сумма его элементов равна 36. А общая сумма всех чисел (1, ...24) равна 300. Значит сумма элементов третьего массива равна 150 А на второй массив остаётся сумма равная 150 - 36 = 114 ... То есть задача такая Даны числа 9, 10, ..., 24 и требуется из них выбрать 8 таких, чтобы их сумма равнялась 114. ... надо написать еще программу для точного доказательства верно это? или нет? 1