I feel that everything has been solved properly for the first time in a long time. However, since the D problem was deceived by the shape and decided the algorithm, I regret it.
Just output the smaller one
answerA.py
n,a,b=map(int,input().split())
print(min(a*n,b))
To find the sum of each digit, divide by 10 in the while statement.
answerB.py
n=int(input())
k=n
f=0
while k!=0:
f+=(k%10)
k//=10
print("Yes" if n%f==0 else "No")
The problem of such a pattern makes you want to doubt DP etc., but even if you decide in advance whether to open in each time zone and do a full search, at most $ 2 ^ {10} -1 = 1023 $ (always once) Because it is open), I know I'll be in time. To see what happens to your profits when you decide whether to open or not in each time zone, check whether n stores in the shopping district are open in the time zone you decided to open (up to 10). Since it is recorded, it is O (n), and since it is O (n) because it calculates the profit corresponding to the number of checked stores, it can be seen that the calculation amount is in time.
answerC.py
n=int(input())
f=[list(map(int,input().split())) for i in range(n)]
p=[list(map(int,input().split())) for i in range(n)]
ma=-10000000000000
for i in range(1,2**10):
check=[0]*n
for j in range(10):
if (i>>j) & 1:
for k in range(n):
check[k]+=f[k][j]
ma_sub=0
for i in range(n):
ma_sub+=p[i][check[i]]
ma=max(ma,ma_sub)
print(ma)
At first, I doubted the interval scheduling because I thought about the overlap of the sections, but it is not suitable for the interval scheduling to think about how many intervals ** overlap ** (it is suitable for choosing so that they do not overlap). I thought. As a result, this change in policy was successful. In the end, it was possible to think about ** how many sections are covered at the maximum **, so in other words, ** how many TV programs are being performed at each time **. After that, when updating the value of the interval **, it is efficient to use the imos method **, so I used imos. Furthermore, in this problem, ** the same channel can be recorded continuously even if the end and start times of a certain TV program are the same **, so make sure to use the imos method for each channel when counting the last I tried to calculate all together.
answerD.py
n,c=map(int,input().split())
imos=[[0 for i in range(c)] for j in range(10**5+1)]#1~10**5+1
for i in range(n):
s,t,_c=map(int,input().split())
imos[s-1][_c-1]+=1
imos[t][_c-1]-=1
for i in range(1,10**5+1):
for j in range(c):
imos[i][j]+=imos[i-1][j]
imosans=[0]*(10**5+1)
for i in range(10**5+1):
for j in range(c):
imosans[i]+=(imos[i][j]>=1)
print(max(imosans))
Recommended Posts