Problem:


  MathJax.Hub.Config({ tex2jax: { inlineMath: [["$","$"], ["\\(","\\)"]], processEscapes: true }});

Problem G:
Surface Area of Cubes

Taro likes a single player game "Surface Area of Cubes".

In this game, he initially has an $A \times B \times C$ rectangular solid formed by $A \times B \times C$ unit cubes
(which are all 1 by 1 by 1 cubes). The center of each unit cube is placed at 3-dimentional
coordinates $(x, y, z)$ where $x$, $y$, $z$ are all integers ($0 \leq x \leq A-1, 0 \leq y \leq B -1, 0 \leq z \leq C - 1$).
Then, $N$ distinct unit cubes are removed from the rectangular solid by the game master. After
the $N$ cubes are removed, he must precisely tell the total surface area of this object in order to
win the game.

Note that the removing operation does not change the positions of the cubes which are not
removed. Also, not only the cubes on the surface of the rectangular solid but also the cubes
at the inside can be removed. Moreover, the object can be divided into multiple parts by the
removal of the cubes. Notice that a player of this game also has to count up the surface areas
which are not accessible from the outside.

Taro knows how many and which cubes were removed but this game is very difficult for him,
so he wants to win this game by cheating! You are Taro's friend, and your job is to make a
program to calculate the total surface area of the object on behalf of Taro when you are given
the size of the rectangular solid and the coordinates of the removed cubes.

Input

The input is formatted as follows.

The first line of a test case contains four integers $A$, $B$, $C$, and $N$ ($1 \leq A, B, C \leq 10^8, 0 \leq N \leq
$ min{$1,000, A \times B \times C - 1$}).

Each of the next $N$ lines contains non-negative integers $x$, $y$, and $z$ which represent the coordinate
of a removed cube. You may assume that these coordinates are distinct.

Output

Output the total surface area of the object from which the $N$ cubes were removed.

Sample Input

2 2 2 1
0 0 0

Output for the Sample Input

24

Sample Input

1 1 5 2
0 0 1
0 0 3

Output for the Sample Input

18

Sample Input

3 3 3 1
1 1 1

Output for the Sample Input

60



Sample input:
2 2 2 1
0 0 0


Sample output:
24

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    a,b,c,n = LI()
    aa = [LI() for _ in range(n)]
    r = (a*b+b*c+c*a) * 2

    for d,e,f in aa:
        r += 6
        if d == 0:
            r -= 2
        if e == 0:
            r -= 2
        if f == 0:
            r -= 2
        if d == a-1:
            r -= 2
        if e == b-1:
            r -= 2
        if f == c-1:
            r -= 2

    def k(a,b):
        return sum(map(lambda x: abs(a[x]-b[x]), range(3)))

    for i in range(n):
        ai = aa[i]
        for j in range(i+1,n):
            if k(ai, aa[j]) == 1:
                r -= 2

    return r




print(main())

Submission status: Accepted

Solution code:
a,b,c,n=map(int,input().split())
x=[0]*n;y=[0]*n;z=[0]*n;s=0
for i in range(n):
    x[i],y[i],z[i]=map(int,input().split())
    s+=(x[i]==a-1)+(y[i]==b-1)+(z[i]==c-1)+(x[i]==0)+(y[i]==0)+(z[i]==0)
for i in range(n):
    for j in range(i+1,n):s+=((abs(x[i]-x[j])+abs(y[i]-y[j])+abs(z[i]-z[j]))==1)
print(2*((a*b+b*c+c*a)+3*n-s))

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LS()
    return l
sys.setrecursionlimit(1000000)
mod = 1000000007

#A
def A():
    s = S()
    n = len(s)
    d = [-1 for i in range(n)]
    k = 0
    m = 0
    for i in range(n):
        if s[i] == "[":
            k += 1
        elif s[i] == "]":
            k -= 1
        elif s[i] == "-":
            d[i] = k
        else:
            m += 1
    depth = max(d)
    f = defaultdict(int)
    for i in range(m):
        a,b = input().split()
        f[a] = int(b)

    for i in range(1,depth+1)[::-1]:
        j = 0
        while j < len(s):
            if d[j] == i:
                if f[s[j-1]] == 0:
                    if f[s[j+1]] == 0:
                        print("No")
                        quit()
                    else:
                        w = s[j+1]
                else:
                    if f[s[j+1]] != 0:
                        print("No")
                        quit()
                    else:
                        w = s[j-1]
                f[w] -= 1
                d = d[:j-2]+[None]+d[j+3:]
                s = s[:j-2]+[w]+s[j+3:]
                j -= 2
            j += 1
    if f[s[0]] == 0:
        print("Yes")
    else:
        print("No")
    return

#B
def B():
    n,k = LI()
    s = S()
    t = S()
    q = deque()
    ans = 0
    for i in range(n):
        if s[i] == "B" and t[i] == "W":
            if q:
                x = q.popleft()
                if i-x >= k:
                    ans += 1
                    while q:
                        q.popleft()
            q.append(i)
    if q:
        ans += 1
    for i in range(n):
        if s[i] == "W" and t[i] == "B":
            if q:
                x = q.popleft()
                if i-x >= k:
                    ans += 1
                    while q:
                        q.popleft()
            q.append(i)
    if q:
        ans += 1
    print(ans)
    return

#C
def C():
    n = I()
    s = SR(n)
    t = S()

    return

#D
def D():
    return

#E
def E():
    def surface(x,y,z):
        return ((x == 0)|(x == a-1))+((y == 0)|(y == b-1))+((z == 0)|(z == c-1))+k

    d = [(1,0,0),(-1,0,0),(0,1,0),(0,-1,0),(0,0,1),(0,0,-1)]
    a,b,c,n = LI()
    s = [0 for i in range(7)]
    k = (a==1)+(b==1)+(c==1)
    if k == 0:
        s[1] = 2*(max(0,a-2)*max(0,b-2)+max(0,c-2)*max(0,b-2)+max(0,a-2)*max(0,c-2))
        s[2] = 4*(max(0,a-2)+max(0,b-2)+max(0,c-2))
        s[3] = 8
    elif k == 1:
        s[2] = max(0,a-2)*max(0,b-2)+max(0,c-2)*max(0,b-2)+max(0,a-2)*max(0,c-2)
        s[3] = 2*(max(0,a-2)+max(0,b-2)+max(0,c-2))
        s[4] = 4
    elif k == 2:
        s[4] = max(0,a-2)+max(0,b-2)+max(0,c-2)
        s[5] = 2
    else:
        s[6] = 1
    f = defaultdict(int)
    for i in range(n):
        x,y,z = LI()
        s[surface(x,y,z)] -= 1
        f[(x,y,z)] = -1
        for dx,dy,dz in d:
            if f[(x+dx,y+dy,z+dz)] != -1:
                f[(x+dx,y+dy,z+dz)] += 1
    ans = 0
    for i,j in f.items():
        if j != -1:
            x,y,z = i
            if 0 <= x < a and 0 <= y < b and 0 <= z < c:
                ans += j+surface(x,y,z)
                s[surface(x,y,z)] -= 1
    for i in range(1,7):
        ans += i*s[i]
    print(ans)
    return

#F
def F():
    return

#G
def G():
    return

#H
def H():
    return

#I
def I_():
    return

#J
def J():
    return

#Solve
if __name__ == "__main__":
    E()