PYTHON LIBRARY

 

  1. import sys
  2. input = sys.stdin.readline
  3. read = lambda: map(int, input().split())
  4. # from bisect import bisect_left as lower_bound;
  5. # from bisect import bisect_right as upper_bound;
  6. # from math import ceil, factorial;
  7.  
  9. def ceil(x):
  10. if x != int(x):
  11. x = int(x) + 1
  12. return x
  14. def factorial(x, m):
  15. val = 1
  16. while x>0:
  17. val = (val * x) % m
  18. x -= 1
  19. return val
  20.  
  21. def fact(x):
  22. val = 1
  23. while x > 0:
  24. val *= x
  25. x -= 1
  26. return val
  28. # swap_array function
  29. def swaparr(arr, a,b):
  30. temp = arr[a];
  31. arr[a] = arr[b];
  32. arr[b] = temp;
  34. ## gcd function
  35. def gcd(a,b):
  36. if b == 0:
  37. return a;
  38. return gcd(b, a % b);
  39.  
  40. ## lcm function
  41. def lcm(a, b):
  42. return (a * b) // math.gcd(a, b)
  44. ## nCr function efficient using Binomial Cofficient
  45. def nCr(n, k):
  46. if k > n:
  47. return 0
  48. if(k > n - k):
  49. k = n - k
  50. res = 1
  51. for i in range(k):
  52. res = res * (n - i)
  53. res = res / (i + 1)
  54. return int(res)
  56. ## upper bound function code -- such that e in a[:i] e < x;
  57.  
  59. ## prime factorization
  60. def primefs(n):
  61. ## if n == 1 ## calculating primes
  62. primes = {}
  63. while(n%2 == 0 and n > 0):
  64. primes[2] = primes.get(2, 0) + 1
  65. n = n//2
  66. for i in range(3, int(n**0.5)+2, 2):
  67. while(n%i == 0 and n > 0):
  68. primes[i] = primes.get(i, 0) + 1
  69. n = n//i
  70. if n > 2:
  71. primes[n] = primes.get(n, 0) + 1
  72. ## prime factoriazation of n is stored in dictionary
  73. ## primes and can be accesed. O(sqrt n)
  74. return primes
  76. ## MODULAR EXPONENTIATION FUNCTION
  77. def power(x, y, p):
  78. res = 1
  79. x = x % p
  80. if (x == 0) :
  81. return 0
  82. while (y > 0) :
  83. if ((y & 1) == 1) :
  84. res = (res * x) % p
  85. y = y >> 1
  86. x = (x * x) % p
  87. return res
  89. ## DISJOINT SET UNINON FUNCTIONS
  90. def swap(a,b):
  91. temp = a
  92. a = b
  93. b = temp
  94. return a,b;
  96. # find function with path compression included (recursive)
  97. # def find(x, link):
  98. # if link[x] == x:
  99. # return x
  100. # link[x] = find(link[x], link);
  101. # return link[x];
  103. # find function with path compression (ITERATIVE)
  104. def find(x, link):
  105. p = x;
  106. while( p != link[p]):
  107. p = link[p];
  109. while( x != p):
  110. nex = link[x];
  111. link[x] = p;
  112. x = nex;
  113. return p;
  116. # the union function which makes union(x,y)
  117. # of two nodes x and y
  118. def union(x, y, link, size):
  119. x = find(x, link)
  120. y = find(y, link)
  121. if size[x] < size[y]:
  122. x,y = swap(x,y)
  123. if x != y:
  124. size[x] += size[y]
  125. link[y] = x
  127. ## returns an array of boolean if primes or not USING SIEVE OF ERATOSTHANES
  128. def sieve(n):
  129. prime = [True for i in range(n+1)]
  130. prime[0], prime[1] = False, False
  131. p = 2
  132. while (p * p <= n):
  133. if (prime[p] == True):
  134. for i in range(p * p, n+1, p):
  135. prime[i] = False
  136. p += 1
  137. return prime
  138.  
  139. # Euler's Toitent Function phi
  140. def phi(n) :
  142. result = n
  143. p = 2
  144. while(p * p<= n) :
  145. if (n % p == 0) :
  146. while (n % p == 0) :
  147. n = n // p
  148. result = result * (1.0 - (1.0 / (float) (p)))
  149. p = p + 1
  150. if (n > 1) :
  151. result = result * (1.0 - (1.0 / (float)(n)))
  153. return (int)(result)
  154.  
  155. def is_prime(n):
  156. if n == 0:
  157. return False
  158. if n == 1:
  159. return True
  160. for i in range(2, int(n ** (1 / 2)) + 1):
  161. if not n % i:
  162. return False
  164. return True
  166. #### PRIME FACTORIZATION IN O(log n) using Sieve ####
  167. MAXN = int(1e5 + 5)
  168. def spf_sieve():
  169. spf[1] = 1;
  170. for i in range(2, MAXN):
  171. spf[i] = i;
  172. for i in range(4, MAXN, 2):
  173. spf[i] = 2;
  174. for i in range(3, ceil(MAXN ** 0.5), 2):
  175. if spf[i] == i:
  176. for j in range(i*i, MAXN, i):
  177. if spf[j] == j:
  178. spf[j] = i;
  179. ## function for storing smallest prime factors (spf) in the array
  181. ################## un-comment below 2 lines when using factorization #################
  182. spf = [0 for i in range(MAXN)]
  183. # spf_sieve();
  184. def factoriazation(x):
  185. res = []
  186. for i in range(2, int(x ** 0.5) + 1):
  187. while x % i == 0:
  188. res.append(i)
  189. x //= i
  190. if x != 1:
  191. res.append(x)
  192. return res
  193. ## this function is useful for multiple queries only, o/w use
  194. ## primefs function above. complexity O(log n)
  195.  
  196. def factors(n):
  197. res = []
  198. for i in range(1, int(n ** 0.5) + 1):
  199. if n % i == 0:
  200. res.append(i)
  201. res.append(n // i)
  202. return list(set(res))
  204. ## taking integer array input
  205. def int_array():
  206. return list(map(int, input().strip().split()));
  208. def float_array():
  209. return list(map(float, input().strip().split()));
  211. ## taking string array input
  212. def str_array():
  213. return input().strip().split();
  214.  
  215. def binary_search(low, high, w, h, n):
  216. while low < high:
  217. mid = low + (high - low) // 2
  218. # print(low, mid, high)
  219. if check(mid, w, h, n):
  220. low = mid + 1
  221. else:
  222. high = mid
  223. return low
  224.  
  225. ## for checking any conditions
  226. def check(councils, a, k):
  227. summ = 0
  228. for x in a:
  229. summ += min(x, councils)
  230. return summ // councils >= k
  232.  
  234. #defining a couple constants
  235. MOD = int(1e9)+7;
  236. CMOD = 998244353;
  237. INF = float('inf'); NINF = -float('inf');
  239. ################### ---------------- TEMPLATE ENDS HERE ---------------- ###################
  241. from itertools import permutations
  242. import math
  243. import bisect as bis
  244. import random
  245. import sys

Comments

Post a Comment

Popular Posts