Past questions solved a few days ago It's typical of Sasuga, so I couldn't solve it
It's easy considering how many times biscuits are manufactured.
answerA.py
a,b,t=map(int,input().split())
print(b*(t//a))
Access in ascending order from the smallest index and count the larger one compared to 0.
answerB.py
n=int(input())
v=input().split()
c=input().split()
co=0
for i in range(n):
co+=max(0,int(v[i])-int(c[i]))
print(co)
In the four-question era, the C problem is more difficult than the D problem, isn't it? Well, that's the typical problem ... Since you can select one integer and rewrite it to any number you like, you can find the greatest common divisor of the remaining N-1 integers and think about the maximum value. However, if implemented purely, it will be O ($ N ^ 2 \ times log (maxA) $), which will exceed the constraint with a margin. Here, for some reason (I think I had a bug in my head), I was trying to experiment without a policy or use an appropriate algorithm (such as binary search). While considering the reason why this is not possible, I made the following important discoveries. (Basics in the basics ...)
In other words, the first thing to consider in this problem is ** the cause of the large amount of calculation **, and it is easy to notice that ** there is a part that is calculated multiple times in the calculation of gcd . I will. For example, comparing the case of selecting the kth integer and the case of selecting the k + 1th integer, gcd is gcd (gcd ($ A_1 $ ~ $ A_ {k-1}
answerC.py
from fractions import gcd
n=int(input())
a=[int(i) for i in input().split()]
a1=[a[0]]
for i in range(1,n-1):
a1.append(gcd(a1[-1],a[i]))
a2=[a[-1]]
for i in range(n-2,0,-1):
a2.append(gcd(a2[-1],a[i]))
m=[]
for i in range(n-2):
m.append(gcd(a1[i],a2[-i-2]))
m.append(a1[-1])
m.append(a2[-1])
print(max(m))
First of all, I will also experiment with this. In this problem, we want to maximize the sum, so the idea is to increase the number of positives in the integer sequence as much as possible. Here, if you repeat the experiment, you will find that ** most of the elements can be corrected **. Furthermore, since most of the elements are positive, the operation defined in this problem could ** create an operation that selects any i, j and multiplies $ A_i $ and $ A_j $ by -1 **. I thought. This hypothesis is correct: $ A_i $ and $ A_ {i + 1} $, $ A_ {i + 1} $ and $ A_ {i + 2} $,…, $ A_ {j-2} $ and $ A_ { This can be achieved by performing the operations defined in this problem in the order of j-1} $, $ A_ {j-1} $ and $ A_ {j} $. If the above can be shown, only an even number of negative elements can be made positive, and when there are an even number of negative elements, all can be made positive. When there are an odd number of SUMs, you can find SUM excluding ** the smallest element of absolute value **.
answerD.py
n=int(input())
a=[int(i) for i in input().split()]
a.sort()
j=n
for i in range(n):
if a[i]>=0:
j=i
break
a=list(map(abs,a))
a.sort()
if j%2==0:
print(sum(a))
else:
print(sum(a)-2*a[0])
Recommended Posts