나눗셈 실수오차가 생긴다면 직접 나눗셈을 구현하기

1206번: 사람의 수 (acmicpc.net)  n명의 사람이 0점부터 10점까지 정수로 존재하는 설문조사 문항에 점수를 내서 각 문항마다 평균을 낸 점수가 실수로 주어질때, n이 될 수 있는 가장 작은 정수를 구하는 문제 평균이 소수점 셋째자리까지만 주어진다 예를 들어 32/106 = 0.3018867924528302... 인데 0.301만 주어지는 ---------------------------------------------------------------------------------------------------------------------------------- 만약 설문조사한 사람 수가 x명이고 i번째 문항의 점수 합이 v이면 $$\frac{v}{x} \approx A[i]$$ A..

• format_list_bulleted 정수론
• · 2024. 9. 26.
• textsms

n,m이 매우 클 때 (a1a2a3...an)/(b1b2b3...bm) 분수를 계산하는 마법같은 방법

28828번: Упражнения в умножении (acmicpc.net)  $\frac{a_{1}a_{2}...a_{n}}{b_{1}b_{2}...b_{m}}$과 $10^{6}$ 이하로 차이나는 정수를 구하는 문제 n,m이 $10^{5}$까지이고, $a_{i}, b_{i}$가 $10^{9}$이라 단순하게 곱하고 나누면 시간초과가 난다 v1 = 1for i in range(n): v1 *= A[i]v2 = 1for j in range(m): v2 *= B[j]print(v1//v2)  곱셈을 덧셈으로 바꾸는 대표적인 방법이 로그를 취하는 것이다 $\frac{a_{1}a_{2}...a_{n}}{b_{1}b_{2}...b_{m}} = X$라고 하면 $$logX = log(a_{..

• format_list_bulleted 알고리즘/애드 혹 알고리즘
• · 2024. 7. 25.
• textsms

파이썬 실수 오차 없이 정확하게 계산하게 해주는 Decimal

1. 문제 12727번: Numbers (Small) (acmicpc.net) 12727번: Numbers (Small) The first line of input gives the number of cases, T. T test cases follow, each on a separate line. Each test case contains one positive integer n. Limits 1

• format_list_bulleted 알고리즘/정밀도
• · 2023. 4. 8.
• textsms