Как отсортировать целые числа от 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 секунда" автоматом наводит на совсем другие рассуждения :) Никогда не ленитесь выкладывать полное условие!