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)


Recommended Posts

Learn exploration in Python # 1 Full exploration
Learn cumulative sum in Python
Quadtree in Python --2
Python in optimization
CURL in python
Learn the design pattern "Builder" in Python
Metaprogramming in Python
Python 3.3 in Anaconda
Geocoding in python
SendKeys in Python
Meta-analysis in Python
Learn the design pattern "Flyweight" in Python
Learn the design pattern "Observer" in Python
Learn the design pattern "Memento" in Python
Unittest in python
Learn the design pattern "Proxy" in Python
Epoch in Python
Discord in Python
Learn the design pattern "Visitor" in Python
Sudoku in Python
Learn the design pattern "Bridge" in Python
DCI in Python
Learn the design pattern "Mediator" in Python
quicksort in python
Learn the design pattern "Decorator" in Python
nCr in python
Plink in Python
Constant in python
Learn the design pattern "Iterator" in Python
Lifegame in Python.
FizzBuzz in Python
Sqlite in python
StepAIC in Python
Learn the design pattern "Strategy" in Python
N-gram in python
LINE-Bot [0] in Python
Learn the design pattern "Composite" in Python
Csv in python
Disassemble in Python
Reflection in Python
Constant in python
Learn the design pattern "State" in Python
nCr in Python.
format in python
Scons in Python3
Puyo Puyo in python
python in virtualenv
PPAP in Python
Learn the design pattern "Adapter" in Python
Quad-tree in Python
Learn dynamic programming in Python (A ~ E)
Reflection in Python
Chemistry in Python
Hashable in python
DirectLiNGAM in Python
LiNGAM in Python
Flatten in python
flatten in python
Learn python gestures
Learn the design pattern "Abstract Factory" in Python
Learn the design pattern "Template Method" in Python