ABC D problem
D-question exercises
Policy
Searching for prime numbers is $ O {(\ sqrt {N})} $
When finding a divisor (factorization) also $ O {(\ sqrt {N})} $
Implementation
Prime number search for i in range (int (math.sqrt (N)) +1)
The greatest common divisor is Euclidean algorithm A, B = B, A% B
Remember to add the undivided value to the divisor when factoring
import math
A, B = [int(item) for item in input().split()]
def gdc(A, B):
if B == 0:
return A
else:
return gdc(B, A % B)
def chk_pn(num):
flag = True
if num <= 3:
pass
else:
for i in range(2, int(math.sqrt(num)) + 1):
if num % i == 0:
flag = False
break
return flag
def mk_factor(num):
max_divisor = int(math.sqrt(num))+1
divisor = 2
factor_list = [1]
while divisor <= max_divisor:
if num % divisor == 0:
factor_list.append(divisor)
num /= divisor
else:
divisor += 1
factor_list.append(num) #Don't forget to include the undivided number in the divisor
return factor_list
GDC = gdc(A, B)
pn_factor = [i for i in mk_factor(GDC) if chk_pn(i) is True]
# print(pn_factor)
print(len(set(pn_factor)))
heapq.heapify (list)heapq.heappop (heap) to extract the minimum value with the element negative.heapq.heappush (heap, item)
import heapq as hp
N, M = [int(item) for item in input().split()]
price_list = sorted([-1 * int(item) for item in input().split()])
total_m = 0
def discount(price_list, ticket_num):
total_ticket =0
hp.heapify(price_list)
while total_ticket < ticket_num:
temp = hp.heappop(price_list)
hp.heappush(price_list, -1* (-1*temp//2))
total_ticket += 1
return price_list
res = discount(price_list, M)
print(res)
print(-1 * sum(res))
Policy
Group groups that are facing the same direction
People in the same group are happy
Turn the leftmost person to the left. (If you turn to the right, it will be completely reversed)
The person on the far left is unhappy
When compressed, LRLR is an alternating list, so the number of times R can be inverted * 2 is the number of happiness increases.
However, note that the number of consecutive lines when all Rs are inverted to L when the right end is L and R will deviate by 1.
Implementation
Counting the number of happiness after compressing the list can be stopped by numerical calculation by dividing the number of elements into even and odd numbers and the number of operations that can be performed without having to create an inverted list. It's faster because you don't have to flip the list.
def compress(arr):
"""The person who compressed and disappeared is happy"""
cnt_h = 0
new_arr = []
comp_arr = ['L']
#At first, the beginning is L. This rotation is no-can
if arr[0] == 'R':
for item in arr:
if item == 'L':
new_arr.append('R')
else:
new_arr.append('L')
prev_item = item
else:
new_arr = arr
#Count compression operations and compressed scraps
for i in range(1, N):
if new_arr[i - 1] == new_arr[i]:
cnt_h += 1
else:
comp_arr.append(new_arr[i])
return [comp_arr, cnt_h]
def execute(arr, cnt_h, K):
#Number of operations required to invert all boundaries
max_rotation = len(arr)//2
#It ends when all become L or the number of inversions reaches K
if max_rotation <= K:
cnt_h += len(arr) - 1
else:
cnt_h += 2*K
return cnt_h
N = int(input())
print((N-1)*N //2 )
.pop () and .append ().form collections import deque to speed up stacking. This is faster for putting in and out of the tip and rear end.N, Q = [int(item) for item in input().split()]
tree_list = [input().split() for j in range(1, N)]
query_list = [input().split() for k in range(Q)]
query_list_int = [[int(k) for k in i] for i in query_list]
val_list = [0 for _ in range(N)]
linked_node_list = [[] for _ in range(N)]
#Create a link relationship for undirected graphs (including upstream connections)
for a, b in tree_list:
a, b = int(a)-1, int(b) -1
linked_node_list[a].append(b) #Add child
linked_node_list[b].append(a) #Add parent
for index, val in query_list_int:
val_list[index-1] += val
stack = [0] #Generates a stack containing the value of the root node and stores the target to be patrolled
parent = [0] * (N+1) #Stores a stack that stores visited nodes
#If you use a recursive function, you will get stuck in the memory limit, so execute it sequentially with while
#Use LIFO on the stack. Since it becomes a LIFO, you can perform a depth-first search while looking at the youngest person.
#Remember the parent node and try to play it
#If you define it with a directed graph, you don't need to play the parent
while True:
#Patrol in order from the route
v=stack.pop()
for child in linked_node_list[v]:
if child != parent[v]:
parent[child] = v #Store visited nodes
stack.append(child) #Store the connection destination node of this node v on the stack
val_list[child] += val_list[v] #Cumulative sum
if not stack:
#The patrol ends when the stack runs out
break
print(*val_list)
from collections import deque
N, Q = [int(item) for item in input().split()]
tree_list = [input().split() for j in range(1, N)]
query_list = [input().split() for k in range(Q)]
class Node:
def __init__(self, val):
self.val = val
self.child_list = []
self.cnt = 0
class my_tree:
def __init__(self, tree_list):
self.node_list = []
for i in range(N):
self.node_list.append(Node(i+1))
for a, b in tree_list:
a, b = int(a), int(b)
child_node = self.node_list[b-1]
parent_node = self.node_list[a-1]
self.node_list[a-1].child_list.append(child_node)
self.node_list[b-1].child_list.append(parent_node)
def adding(self, query_list):
for a, data in query_list:
a, data = int(a), int(data)
self.node_list[a-1].cnt += data
stack = deque([self.node_list[0]])
parent_node_list = [self.node_list[0]]*(N + 1)
while True:
v = stack.pop()
for child in v.child_list:
if child != parent_node_list[v.val -1]:
child.cnt += v.cnt
parent_node_list[child.val -1] = v
stack.append(child)
if not stack:
break
ins = my_tree(tree_list)
ins.adding(query_list)
print(*[node.cnt for node in ins.node_list])
N = int(input())
A_list = [int(item) for item in input().split()]
all_sum = sum(A_list)
F_sum_list = [A_list[0]]
for j in range(1,N):
F_sum_list.append(F_sum_list[-1] + A_list[j])
delta_list = [abs(all_sum - 2* i) for i in F_sum_list]
print(min(delta_list))
A, B, X = [int(item) for item in input().split()]
res_list = []
left = 1 -1
right = 10 ** 9 + 1
is_search = True
while is_search:
N = (left + right)//2
res = A * N + B * len(str(N))
if res > X:
right = N
elif res <= X:
res_list.append(N)
left = N
if right - left <= 1:
is_search = False
if res_list == []:
print(0)
else:
print(max(res_list))
import math
A, B, X = [int(item) for item in input().split()]
res = 0
res_list = []
delta = 10**9 // 4
N= 10**9 // 2
is_search = True
while is_search:
res = A * N + B * len(str(N))
if res > X:
N = N -delta
elif res <= X:
res_list.append(N)
N = N + delta
if delta <= 0:
break
delta = delta // 2
new_res_list = []
for i in range(N - 1000, N + 1000):
res = A * i + B * len(str(i))
if res <= X:
new_res_list.append(i)
if new_res_list == [] or max(new_res_list) <1:
print(0)
else:
if 1<= max(new_res_list) < 10**9:
print(max(new_res_list))
else:
print(10**9)
Recommended Posts