Problem:


Score : 300 points

Problem Statement

The problem set at CODE FESTIVAL 20XX Finals consists of N problems.

The score allocated to the i-th (1≦i≦N) problem is i points.

Takahashi, a contestant, is trying to score exactly N points. For that, he is deciding which problems to solve.

As problems with higher scores are harder, he wants to minimize the highest score of a problem among the ones solved by him.

Determine the set of problems that should be solved.

Constraints

1≦N≦10^7

Partial Score

200 points will be awarded for passing the test set satisfying 1≦N≦1000.

Additional 100 points will be awarded for passing the test set without additional constraints.

Input

The input is given from Standard Input in the following format:

N

Output

Among the sets of problems with the total score of N, find a set in which the highest score of a problem is minimum, then print the indices of the problems in the set in any order, one per line.

If there exists more than one such set, any of them will be accepted.

Sample Input 1

4

Sample Output 1

1
3

Solving only the 4-th problem will also result in the total score of 4 points, but solving the 1-st and 3-rd problems will lower the highest score of a solved problem.

Sample Input 2

7

Sample Output 2

1
2
4

The set \{3,4\} will also be accepted.

Sample Input 3

1

Sample Output 3

1



Sample input:
4


Sample output:
1
3

Submission status: Accepted

Solution code:
from math import ceil, sqrt
import sys

n = int(next(sys.stdin).strip())
l = list()
while n > 0:
    i = ceil((sqrt(8 * n + 1) - 1) / 2)
    l.append(i)
    n -= i

for i in reversed(l):
    print(i)

Submission status: Accepted

Solution code:
import sys
import math

N = int(sys.stdin.readlines()[0].strip())

r = N
while r >= 2:
    ans = int(math.ceil((-1 + math.sqrt(1 + 8*r))/2))
    print ans
    r -= ans

if r != 0:
    print 1

Submission status: Accepted

Solution code:
N = input()
i = 1
while i*(i+1)/2 < N:
    i += 1

print i

N -= i
j = i-1
while N > 0:
    if N - j >= 0:
        print j
        N -= j
    j -= 1

Submission status: Accepted

Solution code:
def solve():
    n = int(input())
    if n == 1:
        print(1)
        return
    elif n == 2:
        print(2)
        return
    ans = []
    anssum = 0
    for i in range(1, n):
        ans.append(str(i))
        anssum += i
        if anssum >= n:
            if anssum == n:
                print("\n".join(ans))
            else:
                ans.remove(str(anssum - n))
                print("\n".join(ans))
            return
    print("\n".join(ans))

if __name__=="__main__":
    solve()

Submission status: Accepted

Solution code:
import math
N = int(raw_input())
M = int(math.ceil(-0.5 + math.sqrt(1+8*N) / 2))

while N > 0:
    if N >= M:
        print M
        N -= M
        M -= 1
    else:
        print N
        break

Submission status: Accepted

Solution code:
n=int(raw_input())
r=n+1
l=1
while r-l>1:
    m=(r+l)/2
    if m*(m+1)/2>n:
        r=m
    else:
        l=m
if l*(l+1)/2==n:
    for i in xrange(1,l+1):
        print(i)
else:
    for i in xrange(1,l+2):
        if (l+1)*(l+2)/2-i==n:
            idx=i
            break
    for i in xrange(1,l+2):
        if i==idx:continue
        print(i)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys,copy,math,heapq,itertools as it,fractions,re,bisect,collections as coll

N = int(raw_input())

s = 0
ans = []
for i in xrange(1, N + 1):
	ans.append(i)
	s += i
	if s >= N:
		k = s - N
		break

for i in ans:
	if i == k: continue
	print i

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

N = int(input())
s = 0
ans = set()
for i in range(1,N+1):
    s += i
    ans.add(i)
    if s == N:
        break
    if s > N:
        ans.remove(s - N)
        break
for a in ans:
    print(a)

Submission status: Runtime Error

Solution code:
N = int(input())
vec = []

k = 0
sum = 0
while(k**2 + k < 2*N):
  k += 1
  sum += k
  vec.append(k)

vec.remove(sum - N)

for i in range(len(vec)):
  print(vec[i])

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**6)
from math import floor,ceil,sqrt,factorial,log
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from operator import itemgetter
from fractions import gcd
mod = 10 ** 9 + 7
inf = float('inf')
ninf = -float('inf')
 
#整数input
def ii(): return int(sys.stdin.readline().rstrip()) #int(input())
def mii(): return map(int,sys.stdin.readline().rstrip().split())
def limii(): return list(mii()) #list(map(int,input().split()))
def lin(n:int): return [ii() for _ in range(n)]
def llint(n: int): return [limii() for _ in range(n)]
#文字列input
def ss(): return sys.stdin.readline().rstrip() #input()
def mss(): return sys.stdin.readline().rstrip().split()
def limss(): return list(mss()) #list(input().split())
def lst(n:int): return [ss() for _ in range(n)]
def llstr(n: int): return [limss() for _ in range(n)]

#本当に貪欲法か？ DP法では？？
#本当に貪欲法か？ DP法では？？
#本当に貪欲法か？ DP法では？？

#https://atcoder.jp/contests/cf16-final-open/tasks/codefestival_2016_final_b

n=ii()

if n==1:
    print(1)
    exit()

ans=0
i=0
while ans<n:
    i+=1
    ans+=i
if ans>n:
    p=ans-n

for k in range(1,i+1):
    if k!=p:
        print(k)

Submission status: Runtime Error

Solution code:
cv# -*- coding: utf-8 -*-
import sys
import math
import os
import itertools
import string
import heapq
import _collections
from collections import Counter
from collections import defaultdict
from functools import lru_cache
import bisect
import re
import queue


class Scanner():
    @staticmethod
    def int():
        return int(sys.stdin.readline().rstrip())

    @staticmethod
    def string():
        return sys.stdin.readline().rstrip()

    @staticmethod
    def map_int():
        return [int(x) for x in Scanner.string().split()]

    @staticmethod
    def string_list(n):
        return [input() for i in range(n)]

    @staticmethod
    def int_list_list(n):
        return [Scanner.map_int() for i in range(n)]

    @staticmethod
    def int_cols_list(n):
        return [int(input()) for i in range(n)]


class Math():
    @staticmethod
    def gcd(a, b):
        if b == 0:
            return a
        return Math.gcd(b, a % b)

    @staticmethod
    def lcm(a, b):
        return (a * b) // Math.gcd(a, b)

    @staticmethod
    def divisor(n):
        res = []
        i = 1
        for i in range(1, int(n ** 0.5) + 1):
            if n % i == 0:
                res.append(i)
                if i != n // i:
                    res.append(n // i)
        return res

    @staticmethod
    def round_up(a, b):
        return -(-a // b)

    @staticmethod
    def is_prime(n):
        if n < 2:
            return False
        if n == 2:
            return True
        if n % 2 == 0:
            return False
        d = int(n ** 0.5) + 1
        for i in range(3, d + 1, 2):
            if n % i == 0:
                return False
        return True


class PriorityQueue:
    def __init__(self, l=[]):
        self.q = l
        heapq.heapify(self.q)
        return

    def push(self, n):
        heapq.heappush(self.q, n)
        return

    def pop(self):
        return heapq.heappop(self.q)


MOD = int(1e09) + 7
INF = int(1e15)


def factorization(n):
    S = {}
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp % i == 0:
            cnt = 0
            while temp % i == 0:
                cnt += 1
                temp //= i
            S[i] = cnt

    if temp != 1:
        S[temp] = 1

    if S == []:
        S[n] = 1

    return S


def main():
    # sys.stdin = open("sample.txt")
    N = Scanner.int()
    ok = N + 1
    ng = 0
    while abs(ok - ng) > 1:
        m = (ok + ng) // 2
        if m * (m + 1) // 2 >= N:
            ok = m
        else:
            ng = m
    for i in reversed(range(1, ok + 1)):
        if N >= i:
            print(i)
            N -= i


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
n=int(input());print(int(round(int(input()))*2)+1if n!=1else"1")

Submission status: Runtime Error

Solution code:
n = int(input())
k = int((n*2)**.5)
while k*(k+1)//2 < n:
  k += 1
l = [range(1,k+1)]
if k*(k+1)//2-n:
  l.remove(k*(k+1)//2-n)
for i in l:
  print(l)

Submission status: Runtime Error

Solution code:
def sigma(N):
    return N*(N-1)//2


def find_max(N):
    for i in range(N+1):
        if sigma(i) > N:
            return i


def solve(N):
    Y = find_max(N)
    rem = sigma(Y)-N
    for i in range(1, Y):
        if i != rem:
            print(i)


N = int(input())
solve(N)

Submission status: Runtime Error

Solution code:
def sigma(N):
    return N*(N-1)//2


def find_max(N):
    for i in range(N):
        if sigma(i) > N:
            return i


def solve(N):
    Y = find_max(N)
    rem = sigma(Y)-N
    for i in range(1, Y+1):
        if i != rem:
            print(i)


N = int(input())
solve(N)

Submission status: Runtime Error

Solution code:
N = int(input())

L = [0]
l = 0
for i in range(1,100) :
    l += i
    L.append(l)
ans = []
while N > 0 :
    for i in range(len(L))  :
        #print(L[i],N,L[i+1])
        if (L[i]+1 <= N <= L[i+1]) :
            ans.append(i+1)
            N -= i+1
            break
    
print(*ans,sep="\n")

Submission status: Runtime Error

Solution code:
from bisect import bisect_right

sum_list = []
nm = 1
sm = 1
while sm <= 10**7:
    sum_list.append(sm)
    nm += 1
    sm += nm
    
n = int(input())

k = bisect_right(sum_list, n)

ans_set = set([i for i in range(1,k+2)])
ans_set.remove(sum_list[k] - n)
ans = list(ans_set)

for a in ans:
    print(a)

Submission status: Runtime Error

Solution code:
n = int(input())
a = int((2*n)**0.5)+1
b = int((a*(a+1))/2)-n
c = [i for i in range(1,a+1)]
c.remove(b)
for i in c:
    print(i)

Submission status: Runtime Error

Solution code:
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<iostream>
#include<string>
#include<stack>
#include<queue>
#include<vector>
#include<map>
#include<set>
#include<algorithm>
#include<numeric>

#define rep(n) for(int i=0;i<n;i++)
#define repp(j, n) for(int j=0;j<n;j++)
#define reppp(i, m, n) for(int i=m;i<=n;i++)
#define all(c) c.begin(), c.end()
#define rall(c) c.rbegin(), c.rend()
#define MOD 1000000007
#define MAX 100000
#define INF 1410065408
#define EPS 1e-9
#define DEBUG 0
#define ll long long
#define Pll pair<ll, ll>
#define Pii pair<int, int>
 
using namespace std;
struct edge{int from, to; ll cost;};

//int G[MAX][MAX];

signed main(){
    ios::sync_with_stdio(0); cin.tie(0);
    int n, a;

    cin >> n;
    if(n == 1){
        cout << 1;
        return 0;
    }
    a = (n+2)/2;
    cout << a << endl << n-a << endl;
    return 0;
}

Submission status: Runtime Error

Solution code:
def calc(n):
    i=1
    sm = 0
    st = set()
    if n<=2:
        st.add(n)
        return st
    while sm<=n:
        st.add(i)
        sm += i
        i+=1
    st = st - calc(sm-n)
    return st

n = int(input())

c = calc(n)

for cc in c:
    print(cc)

Submission status: Runtime Error

Solution code:
import math

N = int(input())

sum  =0


for i in range(1,N):
    sum += i
    if sum>=N:
        break

for j in range(1,i+1):
    if j == sum-N:
        continue
    print(j)

Submission status: Runtime Error

Solution code:
a = int(input().strip())

tmp = []
res = []
ind = 1

def bar(foo,hoge):
    if(foo == 0):
        return
    if foo == 1:
        res.append(1)
        return
    elif foo == 2:
        res.append(2)
        return
    for i in reversed(range(hoge)):
        if (tmp[i] <= foo):
            res.append(i + 1)
            bar(foo - (i + 1) , i)
            return
        
        
    
for i in range(10000000):
    ind = ind + i
    tmp.append(ind)
    if ind >= a :
        bar(a, i + 1 )
        break
for i in res:
    print(i)

Submission status: Runtime Error

Solution code:
import sys

f = open('input.txt')
# f = input()

N = int(f.readline())


out = []
sum = 0
for i in range(0, N+1):
    sum = sum + i
    out.append(i)
    if sum > N:
        r = sum - N
        out.remove(r)
        break
    
out.remove(0)

for n in out:
    print(n)

# print(' '.join(map(str, out)))