[GO] Learn exploration in Python # 1 Full exploration

Full search

The number> 105 has a very special property-even though it is an odd number, there are 8 divisors. Now, the number of odd numbers between 1 and N that have exactly 8 positive divisors. Ask. (N is an integer between 1 and 200) Source: ABC106B-105

ABC106B.py

import math
N = 105
ans=0

def yakusu(num):
  cnt = 0
  for i in range(1,int(math.sqrt(num))+1):
    if num%i==0:
      if i != num//i:
        cnt+=2
      else:
        cnt+=1
  return cnt

ans=0
for i in range(1,N+1,2):
  if yakusu(i) == 8:
    ans+=1
print(ans)

Since N is an integer between 1 and 200, an example where a full search is sufficient.

ABC pastry shops sell $ 4 cakes and $ 7 donuts each. At this time, determine if there is a way to buy a total of $ N. However, two of the same item You may buy the above items, or you may not buy some items. (N is an integer between 1 and 100) Source: ABC105B- Cakes and Donuts

ABC105B.py

N = 3
res=[]
for i in range(int(N//4)+1):
  for j in range(int(N//7)+1):
    res.append(i*4+j*7)
if N in res:
  print('Yes')
else:
  print('No')

There are three types of menus for the fast food chain "Pizza at": "A pizza", "B pizza" and "AB pizza". A pizza and B pizza are completely different pizzas, and AB pizza is a combination of these cut in half. The prices per A pizza, B pizza, and AB pizza are A yen, B yen, and C yen, respectively. Nakahashi needs to have X A pizzas and Y B pizzas for tonight's party. The only way to get these pizzas is to buy A pizza or B pizza directly, or buy two AB pizzas and combine them into one A pizza and one B pizza. How many yen do you need at least for this? By rearranging pizzas, you may generate more pizzas than you need. (1<=A,B,C<=5000) Source: ABC105B- Half and Half

ABC105B.py

A,B,C,X,Y = 1500,2000,1600,3,2
out=float('inf')
#AB only
out = min(out, 2*C*max(X,Y))
#A, B only
out = min(out, X*A+Y*B)
#complex
res = 0
res+=2*C*min(X,Y)
if X>Y:
  res+=A*(X-Y)
else:
  res+=B*(Y-X)
out = min(out,res)
print(out)

Since there are calculation patterns, compare each one.

The integer N is given. Here, for two positive integers A and B, we define F (A, B) as "the larger of the number of digits of A and the number of digits of B in decimal notation". For example, the value of F (3,11) is F (3,11) = 2 because 3 is 1 digit and 11 is 2 digits. Find the minimum value of F (A, B) when two pairs of positive integers (A, B) move to satisfy N = A × B. (1≦N≦10*10) Source: ABC057C --Digits in Multiplication

ABC057C.py

import math
N=10000
combi=[]

def length_count(num):
  return len(str(num))

ans=float('inf')
for i in range(1,int(math.sqrt(N))+1):
  if N%i==0:
    combi.append([i,N//i])
  
for i,j in combi:
  ans = min(ans, max(length_count(i),length_count(j)))
print(ans)

After identifying the divisors, complete the search.

There are N people, and the name of the i-th person is Si. From this, he wants to choose three people to meet the following conditions. Everyone's name starts with M, A, R, C, H No more than one person has a name that starts with the same letter How many ways to choose three people to meet these conditions Please ask. However, I do not consider the order of selection. Be careful if the answer doesn't fit in a 32-bit integer type. (1≦N≦10*5) Source: ABC089C --March

ABC089C.py

import itertools
N=5
S=["MASHIKE","RUMOI","OBIRA","HABORO"
   ,"HOROKANAI"]

march = ['M','A','R','C','H']
dic={}
#dic['M':3,'A':2....]Creating a dictionary of march characters and frequency of occurrence
for ss in S:
  if ss[0] in dic and ss[0] in march:
    dic[ss[0]] += 1
  elif ss[0] not in dic and ss[0] in march:
    dic[ss[0]] = 1
ans=0
#Find combinations in march
combi = list(itertools.combinations(dic.keys(),3))
for i,j,k in combi:
  ans += dic[i]*dic[j]*dic[k]
print(ans)