Problem:


Score : 200 points

Problem Statement

There is a kangaroo at coordinate 0 on an infinite number line that runs from left to right, at time 0.
During the period between time i-1 and time i, the kangaroo can either stay at his position, or perform a jump of length exactly i to the left or to the right.
That is, if his coordinate at time i-1 is x, he can be at coordinate x-i, x or x+i at time i.
The kangaroo's nest is at coordinate X, and he wants to travel to coordinate X as fast as possible.
Find the earliest possible time to reach coordinate X.

Constraints

X is an integer.

1≤X≤10^9

Input

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

X

Output

Print the earliest possible time for the kangaroo to reach coordinate X.

Sample Input 1

6

Sample Output 1

3

The kangaroo can reach his nest at time 3 by jumping to the right three times, which is the earliest possible time.

Sample Input 2

2

Sample Output 2

2

He can reach his nest at time 2 by staying at his position during the first second, and jumping to the right at the next second.

Sample Input 3

11

Sample Output 3

5



Sample input:
6


Sample output:
3

Submission status: Accepted

Solution code:
import math
x = int(input())
k = 0
t = 0

if (math.sqrt(8 * x + 1) == math.floor(math.sqrt(8 * x + 1))):
  a = (-1 + math.sqrt(1 + 8 * x))/2
  print(int(a))
else:
  x = (-1 + math.sqrt(1 + 8 * x))//2
  print(int(x) + 1)

Submission status: Accepted

Solution code:
X = int(input())

l = 0
for i in range(X):
    l += (i + 1)
    if l >= X:
        ans = i + 1
        break

print(ans)

Submission status: Accepted

Solution code:
n=int(input())
ans=1
m=1
while m<n:
  ans+=1
  m+=ans
print(ans)

Submission status: Accepted

Solution code:
X = int(input())
sum_time = 0
for i in range(X):
    sum_time+=(i+1)
    if sum_time>=X:
        print(i+1)
        break

Submission status: Accepted

Solution code:
X = input()
res = 0
for i in range(10 ** 5):
  if res + i > X:
    break
  res += i
if X == res:
  print i - 1
else:
  print i

Submission status: Accepted

Solution code:
import math

X = int(input())
print(math.ceil((-1+(8*X+1)**0.5)/2))

Submission status: Accepted

Solution code:
X=int(input())
print([t for t in range(10**5) if t*(t+1)/2<X][-1]+1)

Submission status: Accepted

Solution code:
X = int(input())
a =0
for i in range(1,10**9):
    a += i    
    if a>=X:
        print(i)
        break

Submission status: Accepted

Solution code:
from math import*
x = int(input())
ans = ceil((-1+sqrt(1+8*x))/2)
print(ans)

Submission status: Accepted

Solution code:
def fun():
     print('ac')
     print('ac')
     print('ac')
     print('ac')
from math import*
n=eval(input())
s=ceil((-1+sqrt(1+8*n))/2)
print(s)

Submission status: Accepted

Solution code:
X = int(input())

ans = 0
pos = 0
while pos < X:
    ans += 1
    pos += ans
print(ans)

Submission status: Accepted

Solution code:
x = int(input())
ans = 0
for i in range(1,10**9):
  ans += i
  if ans >= x:
    print(i)
    exit()

Submission status: Accepted

Solution code:
a=int(input())
for i in range(a):
    if i*(i+1)//2<=a and a<=(i+1)*(i+2)//2:
        print(i+1)
        break

Submission status: Accepted

Solution code:
n = int(input())
for t in range(10**9):
    n-= t
    if n<=0: print(t); break

Submission status: Accepted

Solution code:
a = int(input())
ar = []
count = 0
i = 1
while True:
    count += i
    ar.append(i)
    if count >= a:
        break
    i += 1
print(ar[len(ar)-1])

Submission status: Accepted

Solution code:
x=int(input())
i=1
t=1
while x>t:
    i+=1
    t+=i
print(i)

Submission status: Accepted

Solution code:
N=int(input())
a=0
i=0
while a<N:
  i+=1
  a+=i
print(i)

Submission status: Accepted

Solution code:
x = int(input())
import math
huga = int((-1 + math.sqrt(1+8*x))/2)

if huga*(huga+1) == 2*x:
    print(huga)
else:
    print(huga+1)

Submission status: Accepted

Solution code:
N = int(input())

for t in range(10**5):
    if t*(t+1)/2 >= N:
        print(t)
        break

Submission status: Accepted

Solution code:
n=int(input())
ans=0
for i in range(n+1):
    if i*(i+1)/2>=n:
        ans=i
        break
print(ans)

Submission status: Accepted

Solution code:
from sys import exit, setrecursionlimit, stderr
from functools import reduce
from itertools import *
from collections import *
from bisect import *

def read():
  return int(input())
 
def reads():
  return [int(x) for x in input().split()]

X = read()
ans = next(n for n in count(0) if n * (n+1) // 2 >= X)
print(ans)

Submission status: Accepted

Solution code:
X = int(input())

t = 0
x = 0

while 1:
    t += 1
    x += t
    if x >= X:
        break
    
print(t)

Submission status: Accepted

Solution code:
import sys
X=int(input())
for i in range(1,10**5):
    if (i*(i+1))//2 >=X:
        print(i)
        sys.exit()

Submission status: Accepted

Solution code:
x = int(input())
t = (-1+(1+8*x)**0.5)/2
print(int(-(-t//1)))

Submission status: Accepted

Solution code:
X = int(input())

x = 0
i = 0

while True:
	i += 1
	x += i
	if x >= X:
		break

print(i)

Submission status: Accepted

Solution code:
n = input() * 2
a = int(n ** 0.5)
if a * (a + 1) < n:
	a += 1
print a

Submission status: Accepted

Solution code:
import math
X = int(input())
low_N = (-1 + (1 + 8 * X)**0.5) / 2
high_N = (1 + (1 + 8 * X)**0.5) / 2
if low_N % 1 == 0:
    print(int(low_N))
else:
    print(math.floor(high_N))

Submission status: Accepted

Solution code:
X = int(input())

t=0
x=0
while(True):
    t += 1
    x += t
    if x>=X:break
    
print(t)

Submission status: Accepted

Solution code:
X = int(input())
t = 1
while True:
    if X<=t*(t+1)/2:
        print(t)
        break
    t += 1

Submission status: Accepted

Solution code:
x=int(input())
for i in range(100000):
  if i * (i+1) >= 2 * x:
    print(i)
    quit()

Submission status: Accepted

Solution code:
x = int(input())
i = 1
while i * (i + 1) / 2 < x:
	i += 1
print(i)

Submission status: Accepted

Solution code:
x = int(input())
count = 0
s = 0
while True:
    count += 1
    s += count
    if s >= x:
        break
print(count)

Submission status: Accepted

Solution code:
x=int(input())
import math
print(math.ceil((-1+math.sqrt(1+8*x))/2))

Submission status: Accepted

Solution code:
n=int(input())
for i in range(1,100000000):
    n-=i
    if n<=0:
        print(i)
        break

Submission status: Accepted

Solution code:
import math
x = int(input())
i = math.ceil((-1 + math.sqrt(1 + 8 * x)) / 2)
print(i)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
def inpl(): return list(map(int, input().split()))
from math import ceil

X = int(input())
print(ceil((2*X+1/4)**(1/2) - 1/2))

Submission status: Accepted

Solution code:
nest = int(input())

max = 0
i = 0

while max < nest:
	i += 1
	max += i

print(i)

Submission status: Accepted

Solution code:
X = int(input())
for i in range(1, 100000):
    if i*(i+1)/2 >= X:
        print(i)
        exit(0)

Submission status: Accepted

Solution code:
def solution():
	a = raw_input()

	a = int(a)

	i = 0		

	b = 0

	while b < a:
		i += 1
		b += i
	print i

solution()

Submission status: Accepted

Solution code:
n = int(raw_input())
c = int((-1 + (1 + 8*n)**0.5)/2)
while c * (c+1) < n * 2:
    c += 1
print c

Submission status: Accepted

Solution code:
def solve_slow(X):
    for n in range(1000000):
        # print((n * (n - 1) // 2))
        if (n * (n - 1) // 2) >= X:
            break
    return n - 1


def solve_fast(X):
    # n^2 - n - 2X <= 0
    # n = (1 + sqrt(1 + 8X)) // 2
    n = max(int((1 + (1 + 8 * X) ** 0.5) / 2) - 1, 0)
    while True:
        if (n * (n - 1) // 2) >= X:
            break
        n += 1
    return n - 1


X = int(input())
print(solve_fast(X))

Submission status: Accepted

Solution code:

X = int(input())

# for n in range(1000000):
#     # print((n * (n - 1) // 2))
#     if (n * (n - 1) // 2) >= X:
#         break


# n^2 - n - 2X <= 0
# n = (1 + sqrt(1 + 8X)) // 2
n = max(int((1 + (1 + 8 * X) ** 0.5) / 2) - 1, 0)
while True:
    if (n * (n - 1) // 2) >= X:
        break
    n += 1
print(n - 1)

Submission status: Accepted

Solution code:
X = int(input())

for n in range(1000000):
    # print((n * (n - 1) // 2))
    if (n * (n - 1) // 2) >= X:
        break
print(n - 1)

Submission status: Accepted

Solution code:
n=int(input())
ans=1
while ans*(ans+1)/2<n:ans+=1
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
i, sum = 0, 0
while True:
    i += 1
    sum += i
    if sum >= n:
        print(i)
        break

Submission status: Accepted

Solution code:
a = int(input())
s = 0
cnt = 0
for i in range(1, a + 1):
    s += i
    cnt += 1
    if s >= a:
        break
print(cnt)

Submission status: Accepted

Solution code:
from math import ceil, sqrt

x = int(input())
print(ceil((-1 + sqrt(8 * x + 1)) / 2))

Submission status: Accepted

Solution code:
x = int(input())

total = 0
for i in range(0, x+1):
	total += i
	if total >= x:
		print(i)
		break

Submission status: Accepted

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

def readln():
    _res = list(map(int,str(input()).split(' ')))
    return _res

x = int(input())
sum = 0
ans = 0
for i in range(0,x+1):
    sum = sum + i
    if sum >= x:
        ans = i
        break
print(ans)

Submission status: Accepted

Solution code:
X = int(input())
previous = 0 
for i in range(100000):
    previous += i 
    if X <= previous:
        print(i)
        break

Submission status: Accepted

Solution code:
import copy
x = int(input())

m = 0

for i in range(1, x + 1):
    m += i
    if x <= m:
        print(i)
        break

Submission status: Accepted

Solution code:
# coding: utf-8

x = int(input())

i = 1
while 1:
    if i * (i + 1) / 2 >= x:
        print(i)
        break
    else:
        i += 1

Submission status: Accepted

Solution code:
import math

str = input()
x = int(str)

res = math.ceil((-1 + math.sqrt(1 + 8 * x)) / 2.0)

print(res)

Submission status: Accepted

Solution code:
x = int(input())

from math import sqrt
result = int(sqrt(x))

while x > (((result + 1 ) * result ) / 2):
  result += 1

print(result)

Submission status: Accepted

Solution code:
str = input()
x = int(str)

res = 1
s = 0
for i in range(1, 10 ** 5):
  s = s + i
  if s >= x:
    res = i
    break

print(res)

Submission status: Accepted

Solution code:
n = int(raw_input())
x = 0

for i in xrange(1, 100000):
	x += i
	if x >= n:
		print(i)
		break

Submission status: Accepted

Solution code:
import math

length=input()
print int(math.ceil((math.sqrt(1+8*length)-1)/2))

Submission status: Accepted

Solution code:
import sys
from math import sqrt, ceil

cin = sys.stdin
# cin = open("in.txt", "r")

X = int(cin.readline())
'''
i(i+1)/2<=X
i**2 + i - 2X <=0
  -1 +- sqrt( 1 - 4 * (-2X))
  ------
  2
'''
i = ceil((-1+sqrt(1+8*X))/2)


print(i)

Submission status: Accepted

Solution code:
X = int(input())
cnt = 0
for i in range(1, X+1):
	cnt += i
	if cnt >= X:
		print(i)
		break

Submission status: Accepted

Solution code:
import math
x = int(input())
print(math.ceil((-1+math.sqrt(8*x+1))/2))

Submission status: Accepted

Solution code:
import math
print(int(math.sqrt(8*int(input()))+1)//2)

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def II(): return int(input())
def LS(): return input().split()
def S(): return input()


def main():
    x = II()
    for i in range(10**5):
        if (i+1)*i/2 >= x:
            return i
    return -1


print(main())

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

import math

print(math.ceil((-1 + (8 * int(input()) + 1) ** 0.5) / 2))

Submission status: Accepted

Solution code:
def cal(n): return n*(n+1)//2
 
x=int(input())
ans=[1,cal(x)]
a=0
while 1:
    a+=1
    tmp=cal(sum(ans)//2)
    if tmp>x:
        ans[1]=sum(ans)//2
    elif tmp<x:
        ans[0]=sum(ans)//2
    elif tmp==x:
        print(sum(ans)//2)
        break
    if ans[1]-ans[0]==1:
        print(ans[1])
        break

Submission status: Accepted

Solution code:
# coding: utf-8
num = int(input())


# def make_sum(ind):
#     return sum(range(1, ind + 1))

ans = 0
sum_num = 0

if num == 1:
    print(1)
else:
    while True:
        ans += 1
        sum_num += ans
        if sum_num < num <= (sum_num + ans + 1):
            break

    print(ans + 1)

Submission status: Accepted

Solution code:
x=int(raw_input())
ans=0
su=0
while su<x:
    ans+=1
    su+=ans
print ans

Submission status: Accepted

Solution code:
import sys 
import math
home = int(sys.stdin.readline())

edge = int(math.sqrt(home*2)) +1
try_one = (edge * (edge+1)) /2
try_two = (edge * (edge-1)) /2
if try_two >= home:
    print edge -1
else:
    print edge

Submission status: Accepted

Solution code:
x = int(input())
t = 0
i = 1
while i < x:
    x -= i
    i += 1
print(i)

Submission status: Accepted

Solution code:
from sys import stdin
import math
n = int(stdin.readline())
cur = 0
st = 1
while cur <=n:
    cur += st
    if cur >=n:
        break
    st += 1
    
print st

Submission status: Accepted

Solution code:
from math import sqrt

x = int(input())
n = int(sqrt(2 * x)) - 10
while not (n - 1) * n // 2 < x <= n * (n + 1) // 2:
    n += 1
print(n)

Submission status: Accepted

Solution code:
import math
x = input()
a = int((1 + math.sqrt(1 + 8*x)) / 2)
if a*(a-1) == 2*x:
    print a-1
else:
    print a

Submission status: Accepted

Solution code:
def cal(n): return n*(n+1)//2

x=int(input())
ans=[1,cal(x)]
a=0
while 1:
    a+=1
    tmp=cal(sum(ans)//2)
    if tmp>x:
        ans[1]=sum(ans)//2
    elif tmp<x:
        ans[0]=sum(ans)//2
    elif tmp==x:
        print(sum(ans)//2)
        break
    if ans[1]-ans[0]==1:
        print(ans[1])
        break

Submission status: Accepted

Solution code:
x = int(raw_input())
n = 0
c = 0
while n < x:
    c += 1
    n += c

print c

Submission status: Accepted

Solution code:
import math
X = int(input())
t = (-1+(1+8*X)**(1/2))/2
print(math.ceil(t))

Submission status: Accepted

Solution code:
import itertools
def f(t):
    return t * (t + 1) // 2
X = int(input())

def solve():
    for t in itertools.count(0):
        if X <= f(t):
            return t
print(solve())

Submission status: Accepted

Solution code:
import math

if __name__=="__main__":
    m = int(input())
    n = math.ceil((math.sqrt(1.0+8*m) -1)/2.0)
    print(n)

Submission status: Accepted

Solution code:
x = input()
i = 0
n = 0
while n<x:
    n = 0.5*i*(i+1)
    i += 1
print i-1

Submission status: Accepted

Solution code:
from sys import stdin
rr = lambda: stdin.readline().strip()
rrI = lambda: int(rr())
rrM = lambda: map(int, rr().split())

X = rrI()
def solve(X):
    i = 0
    a = X
    while a > 0:
        i += 1
        a -= i
    return i
print solve(X)

Submission status: Accepted

Solution code:
from math import sqrt,ceil
print(ceil((sqrt(1+8*int(input()))-1)/2))

Submission status: Accepted

Solution code:
from math import *
x = int(input())
print(ceil((-1+sqrt(1+8*x))/2))

Submission status: Accepted

Solution code:
# coding: utf-8
def getLnInputs():
    return input().split()


def getLnIntInputs():
    return list(map(int, getLnInputs()))


def main():
    X = getLnIntInputs()[0]
    counter = 0
    displacement = 0
    while displacement < X:
        counter += 1
        displacement += counter

    print(counter)
    return


main()

Submission status: Accepted

Solution code:
def triangle(x):
  n = int(((8*x-1)**0.5-1)/2)
  while n*(n+1) < 2*x: n += 1
  return  n
  
x = int(input())
n = triangle(x)
print(n)

Submission status: Accepted

Solution code:
X=int(input())
place=0
time=0
while place<X:
	time+=1
	place+=time
print(time)

Submission status: Accepted

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

y = 0
i = 0
while y<x:
  i += 1
  y += i

print(i)

Submission status: Accepted

Solution code:
x = int(input())
s = 0
i = 1
while True:
    s += i
    if x <= s:
        print(i)
        break
    else:
        i += 1

Submission status: Accepted

Solution code:
X = int(input())

mina = 0
maxa = 1000000000
mid = int((mina+maxa)/2)
for i in range(100):
    if mid*(mid+1)/2 < X:
        mina = mid
    else:
        maxa = mid
    mid = int((mina+maxa)/2)

print(mid+1)

Submission status: Accepted

Solution code:
import itertools 
X = int(input())
su = 0
for i in itertools.count(1):
    su += i
    if X <= su:
        print(i)
        break

Submission status: Accepted

Solution code:
x = int(input())
d = 0
for i in range(1, 10 ** 6):
    d += i
    if x <= d:
        print(i)
        break

Submission status: Accepted

Solution code:
X = int(input())

sum = 0
for i in range(1, X+1):
    sum += i;
    if sum >= X:
        break

print(i)

Submission status: Accepted

Solution code:
# coding: utf-8

x = int(input())

i = 0
while True:
    i += 1
    if (i * (i + 1) / 2) >= x:
        print(i)
        break

Submission status: Accepted

Solution code:
x = int(raw_input())

import math
n = int(math.ceil((-1 + math.sqrt(1 + 8 * x)) / 2.0))
print(n)

Submission status: Accepted

Solution code:
#import string,itertools,fractions,heapq,re,array,bisect
#from math import *
#from collections import Counter
def rl(s): return xrange(len(s))


INF = 2147483647


import sys
stdin = sys.stdin

X =        int( stdin.readline().strip() )

start = int((2*X)**0.5)

def triangular(n):
    return n*(n+1)//2

while triangular(start) > X:
    start -= 1

while triangular(start) < X:
    start += 1

print start

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys

def s():
    return raw_input().strip()
def n():
    return int(raw_input())
def d():
    return float(raw_input())

def ls():
    return raw_input().strip().split()
def ln():
    return map(int, raw_input().strip().split())
def ld():
    return map(float, raw_input().strip().split())

def fs():
    return [raw_input().strip() for i in xrange(input())]
def fn():
    return [int(raw_input().strip()) for i in xrange(input())]
def fd():
    return [float(raw_input().strip()) for i in xrange(input())]

MOD = 10**9 + 7

X = n()

s = int(math.sqrt(2 * X))

for i in xrange(max(0, s - 200), s + 3000):
    if i**2 + i >= 2 * X:
        print i
        break

Submission status: Accepted

Solution code:
x = int(input())
i = 0
while i*(i+1)//2 < x:
	i += 1
print(i)

Submission status: Accepted

Solution code:
X = int(input())

n = 1
s = 0
while True:
    s += n
    if s >= X:
        print(n)
        break
    else:
        n += 1

Submission status: Accepted

Solution code:
X = int(input())

for i in range(100000):
    s = i * (i + 1) / 2
    if s >= X:
        print(i)
        break

Submission status: Accepted

Solution code:
X = input()
t = 0
i = 1
while True:
    t += i
    if t>=X:
        print i
        break
    i += 1

Submission status: Runtime Error

Solution code:
import math
n = int(input());
dp = []
def dfs(x, i) :
  dp[i] = dp[i-1] + i
  if dp[i] >= n : 
    return i
  return dfs(dp[i], i+1)

sz = int(math.sqrt(n)) + 10
dp = [0] * sz
ans = dfs(0, 1)
print(ans)

Submission status: Runtime Error

Solution code:
n=int(input())
i=int(sqrt(n))//2
while(i*(i+1)//2<n):
  i+=1
print(i)

Submission status: Runtime Error

Solution code:
import itertools
import numpy as np

X = int(input())
L = list(range(X))
L = list(itertools.accumulate(L))

def getNearestValue(list, num):
    idx = np.abs(np.asarray(list) - num).argmin()
    return list[idx]

tmp = getNearestValue(L, X)
tmp1 = abs(X-tmp)
print(L.index(tmp)+tmp1)

Submission status: Runtime Error

Solution code:
N, K = map(int, input().split())
A = list(map(int, input().split()))
A = [a for a in A if a <K]
N = len(A)
dp2 = [1] + [0]*K
dpm = [[0]*(K+1) for _ in range(N+1)]
dpm[0][0] = 1
for i, a in enumerate(A):
    for j in range(K, -1, -1):
        dpm[i+1][j] = dpm[i][max(0, j-a)] + dpm[i][j]
#print(dpm)

r = 0
for i, a in enumerate(A[::-1]):
    f = True
    for j in range(K, -1, -1):
        # 後ろiこの合計がjのもの
        if f and dp2[j] > 0:
            # K-j > x >= K-j-a
            if dpm[N-i-1][max(0, K-j-a)] > dpm[N-i-1][K-j]:
                f = False
        if j-a>=0:
            dp2[j] = dp2[j] + dp2[j-a]
    if f:
        r += 1
#    for j in range(K-1, 0, -1):
#        print("aa", i, N-i-1)
print(r)

Submission status: Runtime Error

Solution code:
import itertools
import bisect
x = int(input())
acc = list(itertools.accumulate(list(range(1, x+1))))
index = bisect.bisect_left(acc, x)
#print(acc)
if acc[index] == x:
    print(index+1)
else:
    print(index+1)

Submission status: Runtime Error

Solution code:
#include <bits/stdc++.h>
using namespace std;
// 287644PV
#define FIXED_FLOAT(x) std::fixed <<std::setprecision(6)<<(x)
const long long mod = 1000000007;

void addSelf(long long&x, long long y)
{
    x+= y;
    if(x >= mod)
        x-=mod;
}
void subSelf(long long&x, long long y)
{
    x -= y;
    if(x < 0)
        x += mod;
}

long long gcd(long long a, long long b)
{
    if(b == 0)
        return a;
    else
        return gcd(b,a%b);
}

long long power(long long base, long long expo)
{
    long long sol = 1;
    for (long long i = 0; i <expo ; ++i) {
        sol *= base;
    }
    return sol;
}

bool compare1(pair<long long,long long> i,pair<long long,long long> j) // 1 < i < n
{
    return i.second < j.second;
}

bool compare2(pair<long long,long long> i, pair<long long,long long> j) //n > n-i > 1
{
    return i.first > j.first;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int x;
    cin >> x;
    int lower = sqrt((double) 2*x+0.25)-0.5;
    lower--;
    int curr = (lower*(lower+1))/2;
    int i = 1;
    while(true)
    {
        if(curr + i == x)
        {
            cout << i;
            break;
        }
        i++;
    }



    return 0;
}

Submission status: Runtime Error

Solution code:
X=int(input())
i=1
sum1=1
while sum<X:
  i+=1
  sum1=sum1+i
print(i)

Submission status: Runtime Error

Solution code:
X=int(input())
import numpy as np
dp=np.array([0]*X)
i=0
while X not in dp:
  i+=1
  dp+=np(dp+np.array(X*[i]))
print(i)

Submission status: Runtime Error

Solution code:
import numpy as np
N, K = map(int, raw_input().split())
A = np.array(map(int, raw_input().split()))
A = np.sort(A)
Sum = A.sum()
if Sum < K:
    print N
else:
    # Find the Smallest Necessary Number 
    # SmallNec = N-1
    A_cumsum = np.concatenate(([0], np.cumsum(A)))
    # SubSet A[0:I]
    I = np.where(A_cumsum<K)[0][-1] + 1
    Sum_ = A_cumsum[I]
    while Sum_ >= K:
        for J in xrange(I-1, -1, -1):
            if A[J] >= Sum_ - K:
                # A[J] is Necessary
                I = J
                pass
            else:
                # A[J] Maybe Unnecessary
                break
        Sum_ = A_cumsum[I]
    print I

Submission status: Runtime Error

Solution code:
import sys
import numpy as np
N, K = map(int, raw_input().split())
A = np.array(map(int, raw_input().split()))
A = np.sort(A)
Sum = A.sum()
if Sum < K:
    print N
    sys.exit()
   
A_cumsum = np.concatenate(([0], np.cumsum(A)))
I = np.where(A_cumsum<K)[0][-1] + 1

Sum_ = A_cumsum[I]
while Sum_ > K:
    for J in xrange(I-1, -1, -1):
        if A[J] <= Sum_ - K:
            break
    I = J + 1
    Sum_ = A_cumsum[I]

print I

Submission status: Runtime Error

Solution code:
def main():
  n,k = map(int,input().split())
  a = list(filter(lambda x:x<k,list(map(int,input().split()))))
  n = len(a)
  a.sort(reverse=True)
  ng = -1
  ok = n
  while ok-ng > 1:
    mid = (ok+ng)//2
    dp = [False]*(k+1)
    dp[0] = True
    f = 0
    for j in range(n):
      if j == mid:
        continue
      w = a[j]
      for i in range(k,w-1,-1):
        if dp[i-w]:
          dp[i] = True
          if k-a[mid] <= i < k:
            ng = mid
            f = 1
            break
      if f:
        break
    else:
      ok = mid
      
  print(n-ok)

if __name__ == "__main__":
  main()

Submission status: Runtime Error

Solution code:
x = int(input())

t = (-1 + math.sqrt(1 + 8 * x))
if t % 2 == 0:
  print(t//2)
else:
  print(t//2+1)

Submission status: Runtime Error

Solution code:
x = int(input())
i = 0
while x>0
  i = i+1
  x = x-i
print(i)

Submission status: Runtime Error

Solution code:
x = int(input())
i=0
while x>0
  i++
  x=x-i
print(i)

Submission status: Runtime Error

Solution code:
###template###
import sys
def input(): return sys.stdin.readline().rstrip()
from collections import defaultdict, Counter
from itertools import product, groupby, count, permutations, combinations
from math import pi, sqrt, ceil, floor
from collections import deque
from bisect import bisect, bisect_left, bisect_right
from string import ascii_lowercase
import heapq
INF = float("inf")
MOD = 10**9 + 7
sys.setrecursionlimit(10**7)
# 4近傍（右, 下, 左, 上）
dy = [0, -1, 0, 1]
dx = [1, 0, -1, 0]
def inside(y: int, x: int, H: int, W: int) -> bool: return 0 <= y < H and 0 <= x < W
def mi(): return map(int, input().split())
def ii(): return int(input())
###template###


N = ii()

print('1' + ''.join(['0'] * (N-1)))

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline

N, K = map(int, input().split())
a = list(map(int, input().split()))
S, f = [set() for i in range(N+1)], [[0] * K for i in range(N+1)]
S[0].add(0)
f[N][0] = 1
for i, (al, ar) in enumerate(zip(a, a[::-1]), 1):
    for j in S[i-1]:
        S[i].add(j)
        x = al + j
        if x < K:
            S[i].add(x)
    for j in range(K):
        if f[-i][j]:
            f[-i-1][j] = 1
            if ar+j < K:
                f[-i-1][ar+j] = 1
for i in range(N):
    for j in range(1, K):
        f[i][j] += f[i][j-1]
cnt = 0
for i, x in enumerate(a):
    if x >= K:
        cnt += 1
        continue
    for j in S[i]:
        if K-x-j-1 < 0 or f[i+1][K-j-1]-f[i+1][K-x-j-1] > 0:
            cnt += 1
            break
print(N - cnt)

Submission status: Runtime Error

Solution code:
X = int(input())
def dfs(t, x):
    global X
    if t>X:
        return X
    if x==X:
        return t-1
    return min(dfs(t+1,x+t),dfs(t+1,x))
print(dfs(0,0))

Submission status: Runtime Error

Solution code:
def reduce (last, count, time):
    if last == 0:
        return time-1
    if last-time==0 or last-time > time:
        return reduce(last-time, count+1, time+1)
    else:
        return reduce(last, count, time+1)
        

if __name__ == '__main__':
    X = int(input())
    ret = reduce(X, 0, 1)
    print(ret)

Submission status: Runtime Error

Solution code:
x = int(input())

for i in range(1,x//2+1):
    a = a + i

if a >= x:
    print(x//2)
else:
    print(x//2+1)

Submission status: Runtime Error

Solution code:
N, K = map(int, input().split())
a = list(map(int, input().split()))
 
a = sorted(a)
ans = N
t = 0

for i in range(N-1, -1, -1) :
    if t+a[i] < K :
        t += a[i]
    else :
        ans = min(ans, i)
 
print(ans)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
def inpl(): return list(map(int, input().split()))
from copy import deepcopy
from operator import add
from itertools import accumulate

N, K = inpl()
A = sorted(inpl())
S = list(accumulate(A, add))
A = A[::-1]
DP = [False for _ in range(K)]
DP[0] = 1
OK = [False for _ in range(N)]

for i, a in enumerate(A):
    DP0 = deepcopy(DP)
    if a >= K:
        OK[i] = True
        continue
    for j, d in enumerate(DP0[-S[::-1][i]:], max(0, K-S[::-1][i])):
        if d:
            if j + a >= K:
                OK[i] = True
                break
            else:
                DP[j+a] = True

if sum(OK) == 0:
    print(N)
else:
    print(OK[::-1].index(True))

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
def inpl(): return list(map(int, input().split()))
from copy import deepcopy

N, K = inpl()
A = sorted(inpl(), reverse=True)

DP = [False for _ in range(K)]
DP[0] = 1
OK = [False for _ in range(N)]

for i, a in enumerate(A):
    DP0 = deepcopy(DP)
    if a >= K:
        OK[i] = True
        continue
    for j, d in enumerate(DP0):
        if d:
            if j + a >= K:
                OK[i] = True
                break
            else:
                DP[j+a] = True

if sum(OK) == 0:
    print(N)
else:
    print(OK[::-1].index(True))

Submission status: Runtime Error

Solution code:
import sys
sys.stdin = open('d3.in')

n, k = map(int, input().split())
a = list(map(int, input().split()))
a.sort()

prefix = [set() for _ in range(n + 1)]
# suffix = [set() for _2 in range(n + 1)]

prefix[0] = {0}
for i in range(n):
    for v in prefix[i]:
        prefix[i+1].add(v)
        if v + a[i] <= k:
            prefix[i+1].add(v + a[i])

suffix_i = {0}

# Cumulative sums
c_suffix = [[0] * (k+1) for _3 in range(n + 1)]

for j in range(k):
    c_suffix[n][j + 1] = c_suffix[n][j] + (j in suffix_i)

for i in range(n - 1, -1, -1):
    to_add = set()
    for v in suffix_i:
        if v + a[i] <= k:
            to_add.add(v + a[i])
    suffix_i.update(to_add)
    for j in range(k):
        c_suffix[i][j + 1] = c_suffix[i][j] + (j in suffix_i)


def find(i):
    if k <= a[i]:
        return 0
    for s in prefix[i]:
        start = max(0, k - a[i] - s)
        stop = k - s
        if c_suffix[i + 1][stop] - c_suffix[i + 1][start] > 0:
            return 0
    return 1


res = 0
for i in range(n):
    res += find(i)
print(res)

Submission status: Runtime Error

Solution code:
# import sys
# sys.stdin = open('d3.in')

n, k = map(int, input().split())
a = list(map(int, input().split()))
a.sort()

prefix = [set() for _ in range(n + 1)]
suffix = [set() for _2 in range(n + 1)]

prefix[0] = {0}
for i in range(n):
    for v in prefix[i]:
        if v + a[i] <= k:
            prefix[i+1].add(v + a[i])

suffix[n] = {0}
for i in range(n - 1, -1, -1):
    suffix[i] = set(suffix[i + 1])
    for v in suffix[i + 1]:
        if v + a[i] <= k:
            suffix[i].add(v + a[i])

# Cumulative sums
c_suffix = [[0] * (k+1) for _3 in range(n + 1)]
for i in range(n + 1):
    for j in range(k):
        c_suffix[i][j + 1] = c_suffix[i][j] + (j in suffix[i])


def find(i):
    if k <= a[i]:
        return 0
    for s in prefix[i]:
        start = max(0, k - a[i] - s)
        stop = k - s
        if c_suffix[i + 1][stop] - c_suffix[i + 1][start] > 0:
            return 0
    return 1


res = 0
for i in range(n):
    res += find(i)
print(res)

Submission status: Runtime Error

Solution code:
import sys
[n, k] = [int(x) for x in input().strip().split()]
a = [int(x) for x in input().strip().split()]

a.sort()

if sum(a) < k:
  print(n)
  sys.exit()

s = 0
for i in range(len(a)):
  s += a[i]
  if s >= k:
    break

aa = [x for x in a if x < a[i]]
bb = [x for x in a if x < k]

cc = []
for i in range(len(aa)):
  c = bb[:i] + bb[i+1:]
  t = k - bb[i]
  c.reverse()
  #print(c)
  flg = 0
  j = 0
  s = 0
  f = [0 for x in range(len(c))]
  while True:
    f[j] = 1
    #print(c)
    #print(f)
    s += c[j]
    if s >= t and s < k:
      flg = 1
      #print(c)
      #print(f)
      break
    if s >= k:
      f[j] = 0
      s -= c[j]
    j += 1
    if j == len(c):
      ii = -1
      for jj in range(len(c) - 1):
        if f[jj] == 1:
          ii = jj
      if ii == -1:
        break
      else:
        for l in range(ii, len(c)):
          f[l] = 0
      j = ii + 1
      s = sum([c[l] * f[l] for l in range(len(c))])
  if flg== 0:
    cc.append(bb[i])
#print(cc)
print(len(cc))