[PYTHON] Codeforces Round # 676 (Div. 2) Bacha Review (10/31)

This time's results

Impressions of this time

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 **.

Problem A

(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)

Problem B

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])

C problem

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}")

D problem

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.

c\_1:(a,b) \rightarrow (a+1,b+1) c\_2:(a,b) \rightarrow (a,b+1) c\_3:(a,b) \rightarrow (a-1,b) c\_4:(a,b) \rightarrow (a-1,b-1) c\_5:(a,b) \rightarrow (a,b-1) c\_6:(a,b) \rightarrow (a+1,b)

Then, when ** $ c \ _i $ is moved by $ x \ _i $, it moves to $ (0,0) \ rightarrow (x, y) $, so the following conditions are required ..

x\_1-x\_3-x\_4+x\_6=x \leftrightarrow (x\_1-x\_4)+(x\_6-x\_3)=x x\_1+x\_2-x\_4-x\_5=y \leftrightarrow (x\_1-x\_4)+(x\_2-x\_5)=y

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 $ x\_1=0,x\_4=0

[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 $ x\_6=0,x\_3=0

[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 $ x\_2=0,x\_5=0

[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))

After the E problem

I will not solve this time.