Как отсортировать целые числа от 1 до n так, чтобы каждое число, начиная со второго, делило сумму чисел, стоящих левее него, нацело
1,00
р.
Массив всегда начинается с 1 и заканчивается каким-нибудь n и числа идут по порядку
Наример, есть массив [1,2,3,4,5] на выходе должно получится [3,1,4,2,5]
P.S. Имеется ограничение по времени - 1 секунда, а максимальная длина массива может быть до 10000 чисел (все числа идут по порядку и не повторяются)
Вот что пока выходит:
def check(a): #проверка подходит массив под условие или нет E = a[0] out = False for i in a[1:]: if(E%i==0): out = True if(E%i!=0): return False E=E+i return out
def sort(arr): #сортировка, тут у нас простой перебор комбинаций n = len(arr) for a in range(n): for b in range(n): if(b==a): continue E = arr[b] #сумма чисел стоящих левее for c in range(n): if(c==b): continue if(E%arr[c]!=0): #если сумма чисел стоящих левее делится на текущее нацело то меняем текущее и предыдущее числа местами temp = arr[c-1] arr[c-1] = arr[c] arr[c] = temp if(check(arr)): return arr #если массив проходим проверку возвращаем его
E=E+arr[c]
Ответ
Окончательный ответ. На С++, правда :)
#include #include
using namespace std
int main() { int N cin >> N int m = N/2 for(int i = 1 i <= m ++i) cout << (m+i) << " " << i << " " <br> if (N % 2) cout << (2*m+1) <br> cout << endl } <br>Итак, если это N = 2m, то мы пишем числа
m+1, 1, m+2, 2, ..., 2m, m
Если N = 2m+1, то
m+1, 1, m+2, 2, ..., 2m, m, 2m+1
Всё.
Промежуточный ответ не вытираю, все ж таки пример перебора с возвратом - иногда годится. Да и о том, как прочищает мозги информация о том, что решение существует - тоже :)
Прошу обратить внимание - сами видите, что условие "до 10000, 1 секунда" автоматом наводит на совсем другие рассуждения :) Никогда не ленитесь выкладывать полное условие!
Наример, есть массив [1,2,3,4,5] на выходе должно получится [3,1,4,2,5]
P.S. Имеется ограничение по времени - 1 секунда, а максимальная длина массива может быть до 10000 чисел (все числа идут по порядку и не повторяются)
Вот что пока выходит:
def check(a): #проверка подходит массив под условие или нет E = a[0] out = False for i in a[1:]: if(E%i==0): out = True if(E%i!=0): return False E=E+i return out
def sort(arr): #сортировка, тут у нас простой перебор комбинаций n = len(arr) for a in range(n): for b in range(n): if(b==a): continue E = arr[b] #сумма чисел стоящих левее for c in range(n): if(c==b): continue if(E%arr[c]!=0): #если сумма чисел стоящих левее делится на текущее нацело то меняем текущее и предыдущее числа местами temp = arr[c-1] arr[c-1] = arr[c] arr[c] = temp if(check(arr)): return arr #если массив проходим проверку возвращаем его
E=E+arr[c]
Ответ
Окончательный ответ. На С++, правда :)
#include #include
using namespace std
int main() { int N cin >> N int m = N/2 for(int i = 1 i <= m ++i) cout << (m+i) << " " << i << " " <br> if (N % 2) cout << (2*m+1) <br> cout << endl } <br>Итак, если это N = 2m, то мы пишем числа
m+1, 1, m+2, 2, ..., 2m, m
Если N = 2m+1, то
m+1, 1, m+2, 2, ..., 2m, m, 2m+1
Всё.
Промежуточный ответ не вытираю, все ж таки пример перебора с возвратом - иногда годится. Да и о том, как прочищает мозги информация о том, что решение существует - тоже :)
Прошу обратить внимание - сами видите, что условие "до 10000, 1 секунда" автоматом наводит на совсем другие рассуждения :) Никогда не ленитесь выкладывать полное условие!
