algorithmic_toolbox/different_summands.py at master · pythonpapadotin/algorithmic_toolbox · GitHub

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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
# Uses python3
import sys
import math
# import random
def n_sum(n):
    return (n*(n+1))//2

def rev_sum(n):
    return (math.sqrt(1+8*n)-1)//2

# def optimal_summands(n):
#     summands = []
#     candies_left = n
#     i = 1
#     while(candies_left>0):
#         # print(i)
#         if i not in summands and candies_left-i not in summands and i!=candies_left-i:
#             summands.append(i)
#             candies_left-=i
#         i+=1
#     return summands

# def optimal_summands_adv(n):
#     i = 1
#     summands = []
#     candies_left = n
#     while(n_sum(i)<=n and n-n_sum(i) not in summands):
#         # print("i is ",i,"and sum is ",n_sum(i))
#         if i!=n-n_sum(i):
#             # print("here")
#             summands.append(i)
#             candies_left-=i
#         i+=1
#     if candies_left:
#         summands.append(candies_left)
#     return summands

def optimal_summands_very_adv(n):
    summands = []
    i = int(rev_sum(n))
    over = 1
    while(over):
        if n-n_sum(i)>i:
            over = 0
            break
        i-=1
    for j in range(1,i+1):
        summands.append(j)
    summands.append(n-n_sum(i))

    return summands


if __name__ == '__main__':
    input = sys.stdin.read()
    summands = optimal_summands_very_adv(int(input))
    print(len(summands))
    for x in summands:
        print(x, end=' ')
    # count = 0
    # while True:
    #     count+=1
    #     n = random.randint(10*8,10**9)
        # summands_1 = optimal_summands_adv(n)
        # summands_2 = optimal_summands_very_adv(n)
        # if summands_1!=summands_2:
        #     print("Wrong Answer for n =",n)
        # if count%10 == 0:
        #     print(count,"testcases passed")
        # print(count,"testcases passed")
        # print(len(summands))
        # for x in summands:
        #     print(x, end=' ')
        # print("\n","###########################################")