CSES - HIIT Open 2024 - Results
Submission details
Task:Equilateral numbers
Sender:ht
Submission time:2024-11-16 16:43:26 +0200
Language:Python3 (PyPy3)
Status:READY
Result:
Test results
testverdicttime
#1ACCEPTED0.04 sdetails
#2ACCEPTED0.04 sdetails
#3ACCEPTED0.04 sdetails
#4ACCEPTED0.04 sdetails
#5ACCEPTED0.04 sdetails
#6--details
#70.08 sdetails
#80.08 sdetails
#90.04 sdetails
#10ACCEPTED0.04 sdetails
#110.08 sdetails
#120.07 sdetails

Code

def eqnum(k):
if k % 2 == 1:
return k*((k+1)//2)
else:
return (k//2)*(k+1)
# print(eqnum(120000), 10**12)
# exit()
def binsearch(n, k0, k1):
mid = (k0 + k1) // 2
e = eqnum(mid)
# print(n, k0, k1, e)
if e == n:
return mid
elif k0 >= k1:
if e > n:
return k1-1
else:
return k1
elif e > n:
return binsearch(n, k0, mid-1)
else:
return binsearch(n, mid+1, k1)
n0 = int(input())
others = [([], 10**13, n0, 0)]
completed = []
while len(others):
nums, k, n, c = others[0]
others = others[1:]
while(n):
e = eqnum(k)
e2 = eqnum(k-1)
e3 = eqnum(k-2)
if e2 >= 1 and 2*e2 <= n:
nums2 = [x for x in nums]
nums2.append(e2)
nums2.append(e2)
others.append([nums2, k-1, n-e2*2, c+2])
if e3 >= 1 and 3*e3 <= n:
nums3 = [x for x in nums]
nums3.append(e3)
nums3.append(e3)
nums3.append(e3)
others.append([nums3, k-2, n-e3*3, c+3])
for l in range(k-2,k-32,-1):
if l < 1:
break
eee = eqnum(l)
if eee >= 1 and (k - l)*eee <= n:
nums3 = [x for x in nums]
for _ in range(k - l):
nums3.append(eee)
others.append([nums3, l, n-(k - l) * eee, 0])
if e <= n:
c += 1
n -= e
nums.append(e)
else:
k = binsearch(n,1,k)
# print(len(others))
completed.append([x for x in nums])
mc = 10**12
mp = None
# print(len(completed), completed)
for c in completed:
if len(c) < mc:
mp = c
mc = len(c)
# print("val", c)
print(mc)
# print(len(mc), sum(nums), nums)
# print(c, sum(nums), nums)

Test details

Test 1

Verdict: ACCEPTED

input
1

correct output
1

user output
1

Test 2

Verdict: ACCEPTED

input
2

correct output
2

user output
2

Test 3

Verdict: ACCEPTED

input
3

correct output
1

user output
1

Test 4

Verdict: ACCEPTED

input
5

correct output
3

user output
3

Test 5

Verdict: ACCEPTED

input
33

correct output
3

user output
3

Test 6

Verdict:

input
12385719843

correct output
3

user output
(empty)

Test 7

Verdict:

input
10935032

correct output
3

user output
4

Test 8

Verdict:

input
659023495928

correct output
3

user output
5

Test 9

Verdict:

input
913591235689

correct output
2

user output
5

Test 10

Verdict: ACCEPTED

input
999999911791

correct output
1

user output
1

Test 11

Verdict:

input
1000000000000

correct output
2

user output
5

Test 12

Verdict:

input
999999999998

correct output
3

user output
5