This time, I was able to abandon the C problem and work on the D problem, so I managed to recover. I think the attitude of not giving up was good.
This problem was a tough result because there were many gag problems, but since it is clearly a gag problem, I would like to ** handle it well **.
(Hereafter, the $ i $ bit is $ a \ _i, b \ _i, x \ _i $)
This is a bit problem that we often see in Codeforces. In such a problem, ** each bit can be calculated independently **, so consider what happens to the $ i $ bit.
(1) When $ a \ _i = 1, b \ _i = 1 $ If $ x \ _ i = 1 $, the $ i $ bit of $ (a \ oplus x) + (b \ oplus x) $ does not stand, so the $ i $ bit is the smallest at 0.
(2) When $ a \ _i = 1, b \ _i = 0 $ or $ a \ _ i = 0, b \ _i = 1 $ Since the $ i $ bit of $ (a \ oplus x) + (b \ oplus x) $ stands out in any of $ x \ _ i = 0,1 $, the $ i $ bit is the smallest at 1.
(3) When $ a \ _i = 0, b \ _i = 0 $ If $ x \ _ i = 0 $, the $ i $ bit of $ (a \ oplus x) + (b \ oplus x) $ does not stand, so the $ i $ bit is 0, which is the minimum.
From the above, the answer can be obtained by adding 1 bit to $ a \ _i and b \ _i $ on only one side.
A.py
for _ in range(int(input())):
a,b=map(int,input().split())
x=0
for i in range(32):
if ((a>>i)&1):
if ((b>>i)&1):
pass
else:
x+=(1<<i)
else:
if ((b>>i)&1):
x+=(1<<i)
else:
pass
print(x)
After taking a long time to come up with the idea, I divided the cases into darkness.
What you do is pretty typical. In any case, it is possible to prevent you from going from the start to the goal, so I think it may be possible to make it difficult to pass near the goal and near the start **.
From here, it's an idea game, but if you think that you only need to change ** the two squares adjacent to the start point and the two squares adjacent to the goal point **, the consideration goes well. In other words, it is sufficient if the two squares adjacent to the start point are 0 (or 1) and the two squares adjacent to the goal point are 1 (or 0). Also, this can be achieved by adjusting only up to two squares with good adjustment.
I think that it can be implemented without difficulty if you pay attention only to the case when two adjacent squares are 0,0 or 1,1. As I noticed while writing this commentary, I tried both (0,0), (1,1) and (1,1), (0,0) and chose the one with the smaller number of cells to change. If so, it will be easier to implement.
B.py
for _ in range(int(input())):
n=int(input())
s=[input() for i in range(n)]
f1=[int(s[0][1]),int(s[1][0])]
f2=[int(s[-1][-2]),int(s[-2][-1])]
ans=[]
if f1==[0,0]:
if f2[0]==0:
ans.append([n,n-1])
if f2[1]==0:
ans.append([n-1,n])
elif f1==[1,1]:
if f2[0]==1:
ans.append([n,n-1])
if f2[1]==1:
ans.append([n-1,n])
elif f2==[0,0]:
if f1[0]==0:
ans.append([1,2])
if f1[1]==0:
ans.append([2,1])
elif f2==[1,1]:
if f1[0]==1:
ans.append([1,2])
if f1[1]==1:
ans.append([2,1])
elif f1==[0,1] or f1==[1,0]:
if f1==[0,1]:
ans.append([2,1])
else:
ans.append([1,2])
if f2[0]==0:
ans.append([n,n-1])
if f2[1]==0:
ans.append([n-1,n])
print(len(ans))
for i in range(len(ans)):
print(ans[i][0],ans[i][1])
I found it very difficult. Since it is difficult to formulate a solution to the gag problem, it tends to rely on ideas and is not stable.
I tried to palindrome it well, but ** I couldn't get away from the solution of $ i = n-1 $ at the beginning **. For problems like this, it's a good idea to focus on the minimum and maximum values when building. In other words, if you pay attention to $ i = 2 $, you can build it by the following method.
By setting $ n = 2 $ at the beginning, you can separate $ S \ _1 $ from the end **, so I think it is possible to think that it can be constructed well by inversion.
C.py
s=input()
n=len(s)
print(3)
print("L 2")
print("R 2")
print(f"R {2*n-1}")
This problem was also a gag. It's all gag ... And since I am not good at implementing it, I divided it into dark cases as in the case of B problem. I'm glad I won.
First, ** the operation is difficult to understand, so organize it **. Considering how to move the coordinates in each operation, there are the following 6 ways.
Then, when ** $ c \ _i $ is moved by $ x \ _i $, it moves to $ (0,0) \ rightarrow (x, y) $, so the following conditions are required ..
At this time, ** $ x \ _1-x \ _4 $ is fixed under the above conditions **, and the values of $ x \ _6-x \ _3 and x \ _2-x \ _5 $ are determined respectively. Furthermore, when the value of $ x \ _6-x \ _3, x \ _2-x \ _5 $ is determined, the value of $ x \ _6, x \ _3, x \ _2, x \ _5 $ is all uniquely determined. Therefore, if you think about which term of ** $ x \ _1-x \ _4, x \ _6-x \ _3, x \ _2-x \ _5 $ should be set to 0 **, the consideration from here will proceed. ..
First, if you don't want to use $ x \ _1-x \ _4 $, set $ x \ _1-x \ _4 = 0 $ (1). Similarly, if you don't want to use $ x \ _6-x \ _2 $, you can use $ x \ _6-x \ _3 = 0 $ (2), if you don't want to use $ x \ _2-x \ _5 $, you can use $. You can set x \ _2-x \ _5 = 0 $ (3).
In addition, the cases (1) to (3) can be classified as follows.
(1) When $ x \ _1-x \ _4 = 0 $
[1] About $ x \ _1, x \ _4 $
[2] About $ x \ _6, x \ _3 $ When $ x \ geqq 0 $, $ x \ _6 = x, x \ _3 = 0 $ When $ x \ leqq 0 $, $ x \ _6 = 0, x \ _3 = -x $
[3] About $ x \ _2, x \ _5 $ When $ y \ geqq 0 $, $ x \ _2 = y, x \ _5 = 0 $ When $ y \ leqq 0 $, $ x \ _2 = 0, x \ _5 = -y $
(2) When $ x \ _6-x \ _3 = 0 $
[1] About $ x \ _6, x \ _3 $
[2] About $ x \ _1, x \ _4 $ When $ x \ geqq 0 $, $ x \ _1 = x, x \ _4 = 0 $ When $ x \ leqq 0 $, $ x \ _1 = 0, x \ _4 = -x $
[3] About $ x \ _2, x \ _5 $ When $ y-x \ geqq 0 $, $ x \ _2 = y-x, x \ _5 = 0 $ When $ y-x \ leqq 0 $, $ x \ _2 = 0, x \ _5 = x-y $
(3) When $ x \ _2-x \ _5 = 0 $
[1] About $ x \ _2, x \ _5 $
[2] About $ x \ _1, x \ _4 $ When $ y \ geqq 0 $, $ x \ _1 = y, x \ _4 = 0 $ When $ y \ leqq 0 $, $ x \ _1 = 0, x \ _4 = -y $
[2] About $ x \ _6, x \ _3 $ When $ x-y \ geqq 0 $, $ x \ _6 = x-y, x \ _3 = 0 $ When $ x-y \ leqq 0 $, $ x \ _6 = 0, x \ _3 = y-x $
Finally, output the minimum cost for $ x \ _1, x \ _2, x \ _3, x \ _4, x \ _5, x \ _6 $ obtained in each of the above cases. Just do it.
D.py
def calc():
global c1,c2,c3,c4,c5,c6,x1,x2,x3,x4,x5,x6
return x1*c1+x2*c2+x3*c3+x4*c4+x5*c5+x6*c6
for _ in range(int(input())):
x,y=map(int,input().split())
c1,c2,c3,c4,c5,c6=map(int,input().split())
ans=[]
if x>0 and y>0:
x1,x2,x3,x4,x5,x6=0,y,0,0,0,x
elif x>0:
x1,x2,x3,x4,x5,x6=0,0,0,0,-y,x
elif y>0:
x1,x2,x3,x4,x5,x6=0,y,-x,0,0,0
else:
x1,x2,x3,x4,x5,x6=0,0,-x,0,-y,0
ans.append(calc())
if x>0 and y-x>0:
x1,x2,x3,x4,x5,x6=x,y-x,0,0,0,0
elif y-x>0:
x1,x2,x3,x4,x5,x6=0,y-x,0,-x,0,0
elif x>0:
x1,x2,x3,x4,x5,x6=x,0,0,0,x-y,0
else:
x1,x2,x3,x4,x5,x6=0,0,0,-x,x-y,0
ans.append(calc())
if y>0 and x-y>0:
x1,x2,x3,x4,x5,x6=y,0,0,0,0,x-y
elif x-y>0:
x1,x2,x3,x4,x5,x6=0,0,0,-y,0,x-y
elif y>0:
x1,x2,x3,x4,x5,x6=y,0,y-x,0,0,0
else:
x1,x2,x3,x4,x5,x6=0,0,y-x,-y,0,0
ans.append(calc())
print(min(ans))
I will not solve this time.
Recommended Posts