# [AtCoder explanation] Control the A, B, C problems of ABC182 with Python!

** A, B, C problems ** of ** AtCoder Beginner Contest 182 ** will be explained as carefully as possible with ** Python3 **.

I am aiming to explain a solution that satisfies the following three points, not just a method that can be solved.

--Simple: You don't have to think about anything extra --Easy to implement: I'm glad that mistakes and bugs are reduced ――It doesn't take long: The performance goes up and you have more time left for later problems.

[ABC182 Summary](# abc182-Summary) [A problem "twiblr"](#a problem twiblr) [B problem "Almost GCD"](#b problem almost-gcd) [C problem "To 3"](#c problem to-3)

# ABC182 Summary

Total number of submissions: 7497

## performance

Performance AC Score time Ranking(Within Rated)
200 AB---- 300 37 minutes 5814(5649)Rank
400 ABC--- 600 96 minutes 4832(4668)Rank
600 ABC--- 600 44 minutes 3991(3829)Rank
800 ABCD-- 1000 100 minutes 3118(2956)Rank
1000 ABCD-- 1000 50 minutes 2306(2144)Rank
1200 ABCDE- 1500 96 minutes 1631(1475)Rank
1400 ABCDE- 1500 67 minutes 1117(965)Rank
1600 ABCDE- 1500 50 minutes 744(596)Rank
1800 ABCDE- 1500 37 minutes 483(341)Rank
2000 ABCDE- 1500 27 minutes 304(181)Rank
2200 ABCDEF 2100 97 minutes 185(88)Rank
2400 ABCDEF 2100 80 minutes 110(40)Rank

## Correct answer rate by color

color Number of people A B C D E F
Ash 3040 99.1 % 69.9 % 42.3 % 12.5 % 2.9 % 0.0 %
tea 1461 99.5 % 97.7 % 87.7 % 51.8 % 12.7 % 0.1 %
Green 1122 99.5 % 99.5 % 97.2 % 87.5 % 50.7 % 0.6 %
water 692 100.0 % 100.0 % 98.8 % 97.7 % 86.6 % 3.6 %
Blue 357 100.0 % 100.0 % 99.2 % 98.9 % 97.2 % 24.4 %
yellow 134 96.3 % 96.3 % 95.5 % 96.3 % 91.8 % 59.7 %
orange 27 100.0 % 100.0 % 100.0 % 100.0 % 100.0 % 77.8 %
Red 7 100.0 % 100.0 % 100.0 % 100.0 % 100.0 % 100.0 %
• Display rate, ash does not include first-time participants </ font>

## Brief commentary

A problem (7436 people AC) "twiblr"
Arithmetic.
B problem (6249 AC) "Almost GCD"
\$ A_i \$ can be up to \$ 1000 \$. \$ 1000 \$ is never divisible by numbers greater than \$ 1001 \$. You can actually try how many \$ 2 \$ to \$ 1000 \$ are divisible by each and output the maximum number.
C problem (5077 people AC) "To 3"
\$ N \$ is less than \$ 10 ^ {18} \$. That is, there are only up to \$ 18 \$ digits. There are \$ 2 \$ ways to erase digits, up to \$ 18 \$ for each digit, with or without erasing. There are about \$ 26 \$ 10,000 in \$ 2 ^ {18} \$ streets, so you can try erasing all the digits and see if it's a multiple of 3. This is the so-called ** bit full search ** algorithm. Note that you are not allowed to erase everything to \$ 0 \$, in which case you will print \$ -1 \$.
Use the cumulative sum. You may understand it by writing it on paper.
For all up to \$ 50 \$ million light bulbs, it's too late to look at the light bulbs. ** "I know that the future is already illuminated" ** If you stop at this point, the amount of calculation will be \$ O (HW + N + M) \$ and it will be in time.
F problem (233 people AC) "Valid payments" [not explained in this article]
It seems to be dynamic programming.

### Results of me (Unidayo) (reference)

I think I should have thought about the D problem a little more calmly.

# A problem "twiblr"

** Problem page **: A --twiblr ** <font color = # 808080> Gray </ font> Coder Correct Answer Rate **: 99.1% ** <font color = # 804000> Brown </ font> Coder Correct Answer Rate **: 99.5% ** <font color = # 008000> Green </ font> Coder Correct Answer Rate **: 99.5%

## Consideration

It's a simple math, but it's a waste to get a penalty with momentum, so you may want to stop and check it.

## code

``````A, B = map(int, input().split())
print(2 * A + 100 - B)
``````

# Problem B "Almost GCD"

** Problem page **: B --Almost GCD ** <font color = # 808080> Gray </ font> Coder Correct Answer Rate **: 69.9% ** <font color = # 804000> Brown </ font> Coder Correct Answer Rate **: 97.7% ** <font color = # 008000> Green </ font> Coder Correct Answer Rate **: 99.5%

## Consideration

** Suppose you have a positive integer \$ K \$. \$ K \$ is never divisible by a number greater than \$ K \$. ** For example, \$ 6 \$ is never divisible by numbers greater than \$ 7 \$.

The maximum value of the sequence in this problem is set to \$ 1000 \$, so it is certain that numbers greater than \$ 1001 \$ will not be divisible by \$ 1 \$ given.

You can try all the divisible sequences, from \$ 2 \$ to \$ 1000 \$, which are candidates for the answer.

## code

``````N = int(input())
A = list(map(int, input().split()))

ans = 0
current_max = 0

for x in range(2, 1001):
score = 0  #Divided number (GCD degree)
for a in A:
if a % x == 0:
score += 1
if score > current_max:
ans = x
current_max = score

print(ans)
``````

# C problem "To 3"

** Problem page **: C --To 3 ** <font color = # 808080> Gray </ font> Coder Correct Answer Rate **: 42.3% ** <font color = # 804000> Brown </ font> Coder Correct Answer Rate **: 87.7% ** <font color = # 008000> Green </ font> Coder Correct Answer Rate **: 97.2%

## Consideration

It may seem like a problem that requires mathematical consideration, but in fact, it can be solved without devising ** "Search all possible ways to erase digits and judge" **.

The \$ N \$ constraint is less than \$ 10 ^ {18} \$. It has a maximum of \$ 18 \$ digits. For each digit, there are \$ 2 \$ ways to erase or not erase. Therefore, there are up to \$ 2 ^ {18} \$ ways to erase digits. \$ 2 ^ {18} = 262,144 \$. You can try them all in time.

(The \$ 1 \$ way to erase all digits is not allowed, so it's actually \$ 2 ^ {18} -1 = 262,143 \$, but it's included for simplicity)

## Implementation

### The two ways of "use / not use" are "bit full search"

When you want to search all \$ 2 \$ streets of "use / not use" like this problem, use the so-called ** "bit full search" ** method.

The details of bit full search are omitted. (Actually I want to write in detail, but it is hard to write in detail every time a full bit search comes out, so I may summarize it somewhere)

In python, full bit search is easier with the `product` of the` itertools` module.

``````from itertools import product
product((True, False), repeat=l)
``````

If you write this, all combinations that can be made with either `True` or` False` for each element will be generated with a length of \$ l \$.

### How to judge multiples of 3

** "Erase the numbers, stick them together back to an integer, and determine if it's divisible by \$ 3 \$" seems obviously annoying. ** **

Therefore, it can be easily implemented by using ** "a certain integer \$ N \$ is a multiple of \$ 3 \$" ⇔ "the sum of the numbers in each digit of \$ N \$ is a multiple of \$ 3 \$". ** **

(Example: \$ 18 → 1 + 8 = 9 \$, \$ 762 → 7 + 6 + 2 = 15 \$)

Specifically, create a list of \$ N \$ decomposed by \$ 1 \$ digits. For example, \$ 1234567 \$ would be `[1,2,3,4,5,6,7]`. If you want to use a certain digit without erasing it, add it to the sum of digits, and if you erase it, do not add it. And finally, you just have to determine if the sum of digits is a multiple of \$ 3 \$.

### You can't erase everything

If you erase all the digits, the sum of digits will be \$ 0 \$, so it will always be a multiple of \$ 3 \$. However, this issue is not allowed.

It is troublesome to exclude it, so if the answer is the default value, you can output \$ -1 \$.

## code

``````from itertools import product

#For the time being, after receiving it as a character string S, it is easier to handle if it is made into a list A of numbers for each digit.
# N = 6227384 -> A = [6,2,2,7,3,8,4]

S = input()
A = [int(x) for x in S]

l = len(S)  #The number of digits in S (since S was received as a string, len(S)Can be used)
ans = l

for bits in product((True, False), repeat=l):
digit_sum = 0  #It is the sum of the unerased digits
score = 0  #The number with the digits erased, the smaller the number, the better
for i, bit in enumerate(bits):
if bit:
#Use without erasing the i-th digit from the top
digit_sum += A[i]
else:
#Erase the i-th digit from the top
score += 1

if digit_sum % 3 == 0:
#If the erase method is a multiple of 3, update the minimum value.
ans = min(ans, score)

if ans == l:
#It wasn't a multiple of 3, so-Output 1
print(-1)
else:
print(ans)
``````