Facebook Hacker Cup 2021 Round 1

A1.py

T = int(input())
for t in range(T):
  N = int(input())
  S = input()
  ans = 0
  last = ""
  for s in S:
    if (s=="O" or s=="X") and s!=last:
      last = s
      ans += 1
  ans = max(0, ans-1)
  print(f"Case #{t+1}: {ans}")

A2.py

T = int(input())
for t in range(T):
  N = int(input())
  S = input()
  ans = 0
  lastX = -1
  lastO = -1
  a = 0
  for i in range(N):
    if S[i]=="X":
      if lastO>lastX:
        a += lastO+1
        a %= 1000000007
      lastX = i
    if S[i]=="O":
      if lastX>lastO:
        a += lastX+1
        a %= 1000000007
      lastO = i
    ans += a
    ans %= 1000000007
  print(f"Case #{t+1}: {ans}")

A3.py

M = 1000000007

T = int(input())
for t in range(T):
  K = int(input())
  S = input()

  n = 0
  X = 0
  Y = 0
  XY = 0
  first = ""
  first_pos = -1
  last = ""
  last_pos = -1
  c = -1 # change num
  for s in S:
    if s=="F":
      n += 1
    if s=="O" or s=="X":
      if c==-1:
        c = 0
        first = s
        first_pos = n
        last = s
        last_pos = n
      else:
        if s!=last:
          c += 1
          X += last_pos
          Y += n
          XY += last_pos*n%M
          last = s
          last_pos = n
        else:
          last_pos = n
      n += 1
    if s==".":
      if c==-1:
        n *= 2
        n %= M
      else:
        (n, X, Y, XY, last_pos, c) = (
          2*n%M, # n
          ((2*X + n*c) + (last_pos if first!=last else 0))%M, # X
          ((2*Y + n*c) + (n+first_pos if first!=last else 0))%M, # Y
          (XY + XY + (X+Y)*n + n*n*c + (last_pos*(n+first_pos) if first!=last else 0))%M, # XY
          (last_pos + n)%M, # last_pos
          (2*c + (1 if first!=last else 0))%M) # c
  if c==-1:
    ans = 0
  else:
    # print(n, X, Y, XY, c)
    ans = (X*n + n*c - XY - Y)%M
  print(f"Case #{t+1}: {ans}")

"""
FFFOFFFFXFXFF
   x    y

x*N + N - x*y - y

Σ[i](xi+t)*(yi+t)
  = Σ[i](xi*yi+(xi+yi)*t+t*t)
  = Σxi*yi + Σ(xi+yi)*t + t*t*n

0123456789
FXXFXFOOXF
    x y
       xy

0123456789012
XFOFXFOFXFOFX
x y
  x y
    x y
      x y
        x y
          x y
"""

B.py

T = int(input())
for t in range(T):
  N, M, A, B = map(int, input().split())
  a = A-N-M+2
  b = B-N-M+2
  if 1<=a and 1<=b:
    print(f"Case #{t+1}: Possible")
    print(" ".join(map(str, [a]+[1]*(M-2)+[b])))
    for _ in range(N-1):
      print(" ".join(map(str, [1]*M)))
  else:
    print(f"Case #{t+1}: Impossible")

C.cpp

#include <iostream>
#include <vector>
#include <functional>
using namespace std;

int main()
{
    long long M = 1000000007;

    int T;
    cin>>T;
    for (int t=1; t<=T; t++)
    {
        int N;
        cin>>N;
        vector<vector<int>> E(N);
        vector<vector<int>> EC(N);
        for (int i=0; i<N-1; i++)
        {
            int A, B, C;
            cin>>A>>B>>C;
            E[A-1].push_back(B-1);
            EC[A-1].push_back(C);
            E[B-1].push_back(A-1);
            EC[B-1].push_back(C);
        }

        vector<vector<int>> X(N, vector<int>(21));
        vector<long long> S(N);
        function<void(int, int)> f1 = [&](int cur, int par)
        {
            X[cur][20]++;
            for (int i=0; i<(int)E[cur].size(); i++)
            {
                int e = E[cur][i];
                int c = EC[cur][i];
                if (e!=par)
                {
                    f1(e, cur);

                    (S[cur] += S[e]) %= M;
                    int n = 0;
                    for (int j=20; j>=0; j--)
                    {
                        n += X[e][j];
                        (S[cur] += (long long)min(j, c)*n%M*X[cur][j]) %= M;
                    }
                    n = 0;
                    for (int j=20; j>=0; j--)
                    {
                        (S[cur] += (long long)min(j, c)*n%M*X[e][j]) %= M;
                        n += X[cur][j];
                    }

                    for (int j=0; j<c; j++)
                        X[cur][j] += X[e][j];
                    for (int j=c; j<=20; j++)
                        X[cur][c] += X[e][j];
                }
            }
        };
        f1(0, -1);

        //for (int i=0; i<N; i++)
        //{
        //    cout<<"(";
        //    for (int j=0; j<=20; j++)
        //        cout<<X[i][j]<<", ";
        //    cout<<") "<<S[i]<<endl;
        //}

        vector<vector<int>> Y(N, vector<int>(21));
        long long ans = 1;

        function<void(int, int)> f2 = [&](int cur, int par)
        {
            for (int i=0; i<(int)E[cur].size(); i++)
            {
                int e = E[cur][i];
                int c = EC[cur][i];
                if (e!=par)
                {
                    Y[e] = Y[cur];
                    for (int j=0; j<=20; j++)
                        Y[e][j] += X[cur][j];
                    for (int j=0; j<c; j++)
                        Y[e][j] -= X[e][j];
                    for (int j=c; j<=20; j++)
                        Y[e][c] -= X[e][j];
                    for (int j=c+1; j<=20; j++)
                    {
                        Y[e][c] += Y[e][j];
                        Y[e][j] = 0;
                    }

                    long long s = S[0];
                    int n = 0;
                    for (int j=20; j>=0; j--)
                    {
                        n += X[e][j];
                        (s += M - (long long)min(j, c)*n%M*Y[e][j]%M) %= M;
                    }
                    n = 0;
                    for (int j=20; j>=0; j--)
                    {
                        (s += M - (long long)min(j, c)*n%M*X[e][j]%M) %= M;
                        n += Y[e][j];
                    }
                    ans = ans*s%M;

                    f2(e, cur);
                }
            }
        };
        f2(0, -1);

        //for (int i=0; i<N; i++)
        //{
        //    cout<<"(";
        //    for (int j=0; j<=20; j++)
        //        cout<<Y[i][j]<<", ";
        //    cout<<")"<<endl;
        //}

        cout<<"Case #"<<t<<": "<<ans<<endl;
    }
}