20 / 16 / 5
Регистрация: 20.09.2018
Сообщений: 51
Записей в блоге: 1
1

Для каждого числа найти количество вариантов разбиения его на сумму двух других чисел из данного набора

05.10.2018, 22:34. Показов 3403. Ответов 1

Условие
Дано N натуральных чисел. Требуется для каждого числа найти количество вариантов разбиения его на сумму двух других чисел из данного набора.

Входные данные
В первой строке дано число N ( 1 ≤ N ≤ 10000). Далее заданы N натуральных чисел, не превосходящих 10**9. Для каждого числа количество разбиений меньше 2**31.

Выходные данные
Вывести N чисел – количество разбиений, в порядке, соответствующем исходному.

Примеры
входные данные
5
3
3
2
2
1
выходные данные
2
2
0
0
0

код

Python
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
def find(c,v) :
    y = -1
    x = len(v)
    while x > y + 1:
        m = (y + x) // 2
        if v[m] >= c:
            x = m
        else:
            y = m
    if x == len(v) :
        bx = 0
    else :
        if v[x] == c :
            bx = x+1
        else :
            bx = 0
    y = -1
    x = len(v)
    while x > y + 1:
        m = (y + x) // 2
        if v[m] > c:
            x = m
        else:
            y = m
    if y == -1 :
        by = 0
    else :
        if v[y] == c :
            by = x+1
        else :
            by = 0
    return abs(bx-by)
 
 
def gen(n,v) :
    if n < 3 :
        return 0
    q = 0
    for i in range(1,(n+1)//2) :
        q = q + find(i,v) * find(n-i,v)
    return q
 
def pod(v,s) :
    for i in v :
        print(gen(i,s))
 
v = []
for _ in range(int(input())) :
    v.append(int(input()))
c = v[:]
c.sort()
pod(v,c)
Python
1
Пояснения
find(c,v) -- функция методом бинарного поиска находит кол-во чисел 'с' в массиве 'v'
gen(n,v) -- перебирает все возможные числа количество вариантов разбиения n на сумму двух других чисел
например для n = 6 : 1+5, 2+4, 3+3

программа не проявляется с задачей за 5 секунд, как можно ускорить код
__________________
Помощь в написании контрольных, курсовых и дипломных работ, диссертаций здесь
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
05.10.2018, 22:34
Ответы с готовыми решениями:

Найти максимальную сумму двух соседних чисел из данного набора
Приветствую,Вас,посетители и администрация форума.Прошу у Вас помощи в решении списка задач,список...

Найти максимальную сумму двух соседних чисел из данного набора
Дано целое число N (&gt; 1). Задать N элементов одномерного массива. Найти максимальную сумму двух...

Найти максимальную сумму двух соседних чисел из данного набора
Дано целое число N(&gt;1) и набор из N чисел. Найти максимальную сумму двух соседних чисел из данного...

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

1
20 / 16 / 5
Регистрация: 20.09.2018
Сообщений: 51
Записей в блоге: 1
06.10.2018, 12:04  [ТС] 2
*справляется
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
06.10.2018, 12:04
Помогаю со студенческими работами здесь

Даны целые числа K,N а также К наборов целых чисел по N элементов в каждом наборе .Для каждого набора вывести сумму его элементов
Ребята,пожалуйста,укажите ошибку... Даны целые числа K,N а также К наборов целых чисел по N...

Для каждого набора чисел вывести сумму его отрицательных элементов
Даны целые числа K, N, а также K наборов целых чисел по N элементов в каждом наборе. Для каждого...

Для каждого набора целых чисел вывести количество его элементов
/*Series35. Дано целое число K, а также K наборов ненулевых целых чисел. Признаком завершения...

Для каждого числа найти количество его делителей и определить общее количество простых чисел в последовательности
С клавиатуры вводится последовательность целых чисел, 0 - конец этой последовательности. Для...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
2
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2022, CyberForum.ru