AtCoder Grand Contest 047 Participation Report

AtCoder Grand Contest 047 Participation Report

Since only people with a rating of 1200 or higher are related to the rating, I thought that 0 completion would not be a problem, but I was indignant at Pafo 915. When I completed 0 before, it was Pafo 339, so it is better than that.

AGC047A - Integer Product

I couldn't break through. Some people said on Twitter that they would multiply by 10 9 </ sup> to find out how many 2s and 5s were included, and I couldn't understand that person's explanation. However, since it is a decimal number, 2 and 5 should be enough. 2.4 that appears in the input example, but of course if you multiply it by 10, it becomes an integer, but even if you multiply it by 1.25, it becomes an integer. In short, 2 2 </ sup> × 3 × 5 -1 </ sup>, so if you cancel even 5 -1 </ sup>, up to 2 -2 </ sup> Once you know this, find out what the power of 2 and 5 is for each A i </ sub>, and if the sum of the multipliers of 2 and 5 is 0 or more for each combination, it is an integer. The total number of combinations of 2 and 5 is not so large, and * O * ( N </ i> 2 </ sup>) is enough.

def conv(s):
    if s.find('.') == -1:
        s += '.'
    s = s.rstrip('0')
    t = len(s) - s.find('.') - 1
    a = int(s.replace('.', ''))
    if a == 0:
        return (0, 0)
    x, y = -t, -t
    while a % 5 == 0:
        x += 1
        a //= 5
    while a % 2 == 0:
        y += 1
        a //= 2
    return (x, y)


N, *A = open(0).read().split()
N = int(N)

d = {}
for a in A:
    t = conv(a)
    d.setdefault(t, 0)
    d[t] += 1

result = 0
xs = list(d.keys())
for i in range(len(xs)):
    x, y = xs[i]
    t = d[xs[i]]
    if x >= 0 and y >= 0:
        result += t * (t - 1) // 2
    for j in range(i + 1, len(xs)):
        m, n = xs[j]
        if x + m >= 0 and y + n >= 0:
            result += t * d[xs[j]]
print(result)

Recommended Posts

AtCoder Grand Contest 041 Participation Report
AtCoder Grand Contest 047 Participation Report
AtCoder Beginner Contest 181 Participation Report
AtCoder Beginner Contest 161 Participation Report
AtCoder Beginner Contest 176 Participation Report
AtCoder Beginner Contest 154 Participation Report
AtCoder Beginner Contest 166 Participation Report
AtCoder Beginner Contest 153 Participation Report
AtCoder Beginner Contest 145 Participation Report
AtCoder Beginner Contest 184 Participation Report
AtCoder Beginner Contest 160 Participation Report
AtCoder Beginner Contest 169 Participation Report
AtCoder Beginner Contest 178 Participation Report
AtCoder Beginner Contest 163 Participation Report
AtCoder Beginner Contest 159 Participation Report
AtCoder Beginner Contest 164 Participation Report
AtCoder Regular Contest 105 Participation Report
AtCoder Beginner Contest 168 Participation Report
AtCoder Beginner Contest 150 Participation Report
AtCoder Beginner Contest 158 Participation Report
AtCoder Beginner Contest 180 Participation Report
AtCoder Regular Contest 104 Participation Report
AtCoder Beginner Contest 162 Participation Report
AtCoder Beginner Contest 157 Participation Report
AtCoder Beginner Contest 167 Participation Report
AtCoder Beginner Contest 179 Participation Report
AtCoder Beginner Contest 182 Participation Report
AtCoder Beginner Contest 146 Participation Report
AtCoder Beginner Contest 152 Participation Report
AtCoder Beginner Contest 155 Participation Report
AtCoder Beginner Contest 174 Participation Report
AtCoder Beginner Contest 148 Participation Report
AtCoder Beginner Contest 188 Participation Report
AtCoder Beginner Contest 170 Participation Report
AtCoder Beginner Contest 187 Participation Report
AtCoder Chokudai Contest 005 Participation Report
AtCoder Beginner Contest 183 Participation Report
AtCoder HHKB Programming Contest 2020 Participation Report
AtCoder Acing Programming Contest 2020 Participation Report
AtCoder Keyence Programming Contest 2020 Participation Report
AtCoder Grand Contest 041 Review
AtCoder Library Practice Contest Participation Report (Python)
AtCoder Grand Contest 048 Review
AtCoder Grand Contest 045 Review
AtCoder Grand Contest 044 Review
AtCoder Introduction to Heuristics Contest Participation Report
AtCoder Grand Contest 046 Review
AtCoder Judge System Update Test Contest 202004 Participation Report
AtCoder Beginner Contest # 003 Participation Note
ACL Beginner Contest Participation Report
Atcoder Beginner Contest 146 Participation Diary
AtCoder Sumitomo Mitsui Trust Bank Programming Contest 2019 Participation Report
AtCoder Grand Contest Past Question Challenge 2
AtCoder Grand Contest Past Question Challenge 1
AtCoder Hitachi, Ltd. Social Systems Division Programming Contest 2020 Participation Report
AtCoder Beginner Contest 177
abc154 participation report
abc155 participation report
AtCoder Beginner Contest 179
AtCoder Beginner Contest 172
AtCoder Beginner Contest 180