Problem:


Problem A: Pablo Squarson's Headache

Pablo Squarson is a well-known cubism artist.  This year's theme for Pablo Squarson is "Squares".  Today we are visiting his studio to see how his masterpieces are given birth.

At the center of his studio, there is a huuuuuge table and beside it are many, many squares of the same size.  Pablo Squarson puts one of the squares on the table.  Then he places some other squares on the table in sequence.  It seems his methodical nature forces him to place each square side by side to the one that he already placed on, with machine-like precision.

Oh!  The first piece of artwork is done.  Pablo Squarson seems satisfied with it.  Look at his happy face.

Oh, what's wrong with Pablo?  He is tearing his hair!  Oh, I see.  He wants to find a box that fits the new piece of work but he has trouble figuring out its size.  Let's help him!

Your mission is to write a program that takes instructions that record how Pablo made a piece of his artwork and computes its width and height.  It is known that the size of each square is 1.  You may assume that Pablo does not put a square on another.

I hear someone murmured "A smaller box will do".  No, poor Pablo, shaking his head, is grumbling "My square style does not seem to be understood by illiterates".

Input

The input consists of a number of datasets.  Each dataset represents the way Pablo made a piece of his artwork.  The format of a dataset is as follows.

N

n1 d1

n2 d2

...

nN-1 dN-1

The first line contains the number of squares (= N) used to make the piece of artwork.  The number is a positive integer and is smaller than 200.

The remaining (N-1) lines in the dataset are square placement instructions.  The line &ldquo;ni di&rdquo; indicates placement of the square numbered i (≤ N-1).  The rules of numbering squares are as follows.  The first square is numbered "zero".  Subsequently placed squares are numbered 1, 2, ..., (N-1).  Note that the input does not give any placement instruction to the first square, which is numbered zero.

A square placement instruction for the square numbered i, namely &ldquo;ni di&rdquo;, directs it to be placed next to the one that is numbered ni, towards the direction given by di, which denotes leftward (= 0), downward (= 1), rightward (= 2), and upward (= 3).
 

For example, pieces of artwork corresponding to the four datasets shown in Sample Input are depicted below. Squares are labeled by their numbers.

The end of the input is indicated by a line that contains a single zero.

Output

For each dataset, output a line that contains the width and the height of the piece of artwork as decimal numbers, separated by a space.  Each line should not contain any other characters.

Sample Input

1
5
0 0
0 1
0 2
0 3
12
0 0
1 0
2 0
3 1
4 1
5 1
6 2
7 2
8 2
9 3
10 3
10
0 2
1 2
2 2
3 2
2 1
5 1
6 1
7 1
8 1
0

Output for the Sample Input

1 1
3 3
4 4
5 6



Sample input:
1
5
0 0
0 1
0 2
0 3
12
0 0
1 0
2 0
3 1
4 1
5 1
6 2
7 2
8 2
9 3
10 3
10
0 2
1 2
2 2
3 2
2 1
5 1
6 1
7 1
8 1
0


Sample output:
1 1
3 3
4 4
5 6

Submission status: Wrong Answer

Solution code:
while True:
    n = int(input())
    if n == 0 : break
    w, h = 1, 1
    edges = [[0], [0], [0], [0]]  #[left, bottom, right, top]
    for i in range(1, n):
        p, d = map(int, input().split())
        if d == 0 or d == 2:
            if p in edges[d]:
                w += 1
                edges[d] = [i]
            if p in edges[1]:
                edges[1].append(i)
            if p in edges[3]:
                edges[3].append(i)
        elif d == 1 or d == 3:
            if p in edges[d]:
                h += 1
                edges[d] = [i]
            if p in edges[0]:
                edges[0].append(i)
            if p in edges[2]:
                edges[2].append(i)
        #print(edges)
    print(w,h)

Submission status: Wrong Answer

Solution code:
while True:
    N=int(input())
    if N==0:break
    t=[0]
    y=[0]
    lst=list(range(N))
    for k in lst[1:]:
        [x,d]=input().split()
        [x,d]=[int(x),int(d)]
        if d==0:
            t=t+[t[x]]
            y=y+[y[x]-1]
        if d==1:
            t=t+[t[x]-1]
            y=y+[y[x]]
        if d==2:
            t=t+[t[x]]
            y=y+[y[x]+1]
        if d==3:
            t=t+[t[x]+1]
            y=y+[y[x]]
    ht=0
    lt=0
    hy=0
    ly=0
    for f in range(N):
        if ht<t[f]:
            ht+=1
        if lt>t[f]:
            lt-=1
        if hy<y[f]:
            hy+=1
        if ly>y[f]:
            ly-=1
    print(ht-lt+1,hy-ly+1)

Submission status: Wrong Answer

Solution code:
dx,dy = [-1,0,1,0],[0,-1,0,1]
while 1:
	N = input()
	if N == 0: break
	x,y = [0]*N,[0]*N
	for i in range(N-1):
		n,d = map(int,raw_input().split())
		x[i] = x[n] + dx[d]
		y[i] = y[n] + dy[d]
	print max(x) - min(x) + 1, max(y) - min(y) + 1

Submission status: Accepted

Solution code:
# AOJ 1165: Pablo Squarson's Headache
# Python3 2018.7.14 bal4u

rr, cc = [0]*202, [0]*202
while True:
	n = int(input())
	if n == 0: break
	rr[0] = cc[0] = r1 = r2 = c1 = c2 = 200
	for i in range(1, n):
		m, d = map(int, input().split())
		r, c = rr[m], cc[m]
		if   d == 0: c -= 1
		elif d == 1: r += 1
		elif d == 2: c += 1
		else:        r -= 1
		rr[i], cc[i] = r, c
		if r < r1: r1 = r
		if r > r2: r2 = r
		if c < c1: c1 = c
		if c > c2: c2 = c
	print(c2-c1+1, r2-r1+1)

Submission status: Accepted

Solution code:
ans_list = []

while True:
    N = int(input())
    if N == 0:
        break

    square = [[0, 0]]
    for i in range(N - 1):
        n, d = map(int, input().split())
        #print(n, d)
        if d == 0:
            square.append([square[n][0], square[n][1] - 1])
        elif d == 2:
            square.append([square[n][0], square[n][1] + 1])
        elif d == 1:
            square.append([square[n][0] - 1, square[n][1]])
        elif d == 3:
            #print(100, square, square[n - 1])
            square.append([square[n][0] + 1, square[n][1]])

    #print(square)

    mini = 10 ** 10
    minj = 10 ** 10
    maxi = -10 ** 9
    maxj = -10 ** 9

    if N == 1:
        ans_list.append([1, 1])
    else:
        for i in range(len(square)):
            mini = min(square[i][0], mini)
            minj = min(square[i][1], minj)
            maxi = max(square[i][0], maxi)
            maxj = max(square[i][1], maxj)

    #print(maxi, maxj, mini, minj)
        ans_list.append([maxj - minj + 1, maxi - mini + 1])

for i in ans_list:
    print(i[0], i[1])

Submission status: Accepted

Solution code:
#! /usr/bin/env python
# -*- coding: utf-8 -*-

import os
import sys
import itertools
import math
from collections import Counter, defaultdict

class Main(object):
    
    def __init__(self):
        pass

    def solve(self):
        '''
        insert your code
        '''
        while True:
            n = input()
            if n == 0:
                break
            pos = [(0, 0) for i in range(n)]
            for i in range(1, n):
                n, d = map(int, raw_input().split())
                if d == 0:
                    pos[i] = (pos[n][0] - 1, pos[n][1])
                elif d == 1:
                    pos[i] = (pos[n][0], pos[n][1] - 1)
                elif d == 2:
                    pos[i] = (pos[n][0] + 1, pos[n][1])
                elif d == 3:
                    pos[i] = (pos[n][0], pos[n][1] + 1)
            width = max(x for x, y in pos) - min(x for x, y in pos) + 1
            height = max(y for x, y in pos) - min(y for x, y in pos) + 1
            print width, height
        return None

if __name__ == '__main__':
    m = Main()
    m.solve()

Submission status: Accepted

Solution code:
D = ((-1,0),(0,1),(1,0),(0,-1))
while 1:
    N = int(input())
    if not N:break

    min_x = min_y = max_x = max_y = 0

    a = [(0,0)]
    for i in range(N-1):
        n1, d1 = list(map(int, input().split()))
        spam = (lambda x: (x[0] + D[d1][0],  x[1] + D[d1][1]))(a[n1])
        min_x = min(spam[0],min_x)
        min_y = min(spam[1],min_y)
        max_x = max(spam[0],max_x)
        max_y = max(spam[1],max_y)
        a.append(spam)

    print('%d %d' % (max_x - min_x + 1, max_y - min_y + 1))

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

while True:
    N = int(input())
    if N == 0:
        break
    square = []
    direct = [(-1,0),(0,-1),(1,0),(0,1)]
    square.append((0,0))
    topleft = (0,0)
    bottomright = (0,0)
    for i in range(N-1):
        n,d = map(int,input().split(" "))
        nextSquare = (square[n][0]+direct[d][0],square[n][1]+direct[d][1])
        topleft = (min(topleft[0],nextSquare[0]),max(topleft[1],nextSquare[1]))
        bottomright = (max(bottomright[0],nextSquare[0]),min(bottomright[1],nextSquare[1]))
        square.append(nextSquare)
    print(bottomright[0]-topleft[0]+1,topleft[1]-bottomright[1]+1)

Submission status: Accepted

Solution code:
while 1:
	N = int(raw_input())
	if N == 0:
		break
	x = [0]
	y = [0]
	put = [(-1,0),(0,-1),(1,0),(0,1)]
	for i in range(1, N):
		n,d = map(int, raw_input().split(" "))
		x.append(x[n]+put[d][0])
		y.append(y[n]+put[d][1])
	print max(x)-min(x)+1, max(y)-min(y)+1

Submission status: Accepted

Solution code:
#! /usr/bin/env python
# -*- coding: utf-8 -*-

n = int(raw_input())
while n!=0:
    SQ = [[0]*500 for i in range(500)]

    Max = [250, 250, 250, 250]
    Map = {0:[250, 250]}
    for i in range(1, n):
        (b, p) = map(int, raw_input().split())
        if p == 0:
            SQ[(Map[b])[0]-1][(Map[b])[1]] = i
            if Max[p] > Map[b][0]-1:
                Max[p] = Map[b][0]-1
            Map[i] = [(Map[b])[0]-1, (Map[b])[1]]
        elif p == 1:
            SQ[(Map[b])[0]][(Map[b])[1]-1] = i
            if Max[p] > Map[b][1]-1:
                Max[p] = Map[b][1]-1
            Map[i] = [(Map[b])[0], (Map[b])[1]-1]
        elif p == 2:
            SQ[(Map[b])[0]+1][(Map[b])[1]] = i
            if Max[p] < Map[b][0]+1:
                Max[p] = Map[b][0]+1
            Map[i] = [(Map[b])[0]+1, (Map[b])[1]]
        elif p == 3:
            SQ[(Map[b])[0]][(Map[b])[1]+1] = i
            if Max[p] < Map[b][1]+1:
                Max[p] = Map[b][1]+1
            Map[i] = [(Map[b])[0], (Map[b])[1]+1]

    print Max[2]-Max[0]+1, Max[3]-Max[1]+1

    n = int(raw_input())

Submission status: Accepted

Solution code:
while True:
    n = int(input())
    if n == 0: break
    squares = [(0,0)]
    x_max, x_min, y_max, y_min = 0, 0, 0, 0
    for i in range(1,n):
        p, d = map(int, input().split())
        x, y = squares[p]
        if d == 0:
            x -= 1
        elif d == 1:
            y -= 1
        elif d == 2:
            x += 1
        elif d == 3:
            y += 1
        squares.append((x,y))
        x_max = max(x_max, x)
        x_min = min(x_min, x)
        y_max = max(y_max, y)
        y_min = min(y_min, y)
    print(x_max - x_min + 1, y_max - y_min + 1)

Submission status: Accepted

Solution code:
def main():
    D = ((-1,0), (0,-1), (1,0), (0,1))
    while True:
        n = int(input())
        if n==0:
            exit()
        sx = [0]
        sy = [0]

        for i in range(n-1):
            ni, di = [int(x) for x in input().split()]
            sx.append(sx[ni]+D[di][0])
            sy.append(sy[ni]+D[di][1])
        w = max(sx)-min(sx)+1
        h = max(sy)-min(sy)+1
        print(w,h)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:

dirs = [(-1,0), (0,1), (1,0), (0,-1)]

while True:
	n = int(input())
	if n == 0:
		break
	x, y = 0, 0
	nd = [[0, 0, 0, 0]]
	for i in range(n-1):
		n, d = map(int, input().split())
		nd.append([n, d, 0, 0])
	for i in range(1, len(nd)):
		nd[i][2] = nd[nd[i][0]][2] + dirs[nd[i][1]][0]
		nd[i][3] = nd[nd[i][0]][3] + dirs[nd[i][1]][1]
	w = max(nd, key=lambda x:x[2])[2] - min(nd, key=lambda x:x[2])[2]
	h = max(nd, key=lambda x:x[3])[3] - min(nd, key=lambda x:x[3])[3]
	print('{} {}'.format(w+1, h+1))

Submission status: Accepted

Solution code:
while True:
    n = int(input())
    if n == 0: break
    xs = [(0, 0)]
    dic = [(-1, 0), (0, 1), (1, 0), (0, -1)]
    maxX, minX, maxY, minY = 0, 0, 0, 0
    for i in range(n - 1):
        n, d = map(int, input().split())
        xs.append((xs[n][0] + dic[d][0], xs[n][1] + dic[d][1]))
        if xs[-1][0] > maxX: maxX = xs[-1][0]
        elif xs[-1][0] < minX: minX = xs[-1][0]
        if xs[-1][1] > maxY: maxY = xs[-1][1]
        elif xs[-1][1] < minY: minY = xs[-1][1]
    print(maxX - minX + 1, maxY - minY + 1)

Submission status: Accepted

Solution code:
while True:
    N=int(input())
    if N==0:break
    t=[0]
    y=[0]
    lst=list(range(N))
    for k in lst[1:]:
        [x,d]=input().split()
        [x,d]=[int(x),int(d)]
        if d==0:
            t=t+[t[x]]
            y=y+[y[x]-1]
        if d==1:
            t=t+[t[x]-1]
            y=y+[y[x]]
        if d==2:
            t=t+[t[x]]
            y=y+[y[x]+1]
        if d==3:
            t=t+[t[x]+1]
            y=y+[y[x]]
    ht=0
    lt=0
    hy=0
    ly=0
    for f in range(N):
        if ht<t[f]:
            ht+=1
        if lt>t[f]:
            lt-=1
        if hy<y[f]:
            hy+=1
        if ly>y[f]:
            ly-=1
    print(hy-ly+1,ht-lt+1)

Submission status: Accepted

Solution code:


adjacent_vector = [
    (-1, 0), # left
    (0, -1), # down
    (1, 0),  # right
    (0, 1)   # up
]

while True:
    num_squares = int(input())

    if num_squares == 0:
        break

    x_coordinates = [0] # x??§?¨?????????????
    y_coordinates = [0] # y??§?¨?????????????

    for _ in range(num_squares-1):
        # adjacent_square: ??£??\????????£?????¢?????????
        adjacent_square, direction = map(int, input().split())

        x = x_coordinates[adjacent_square] # ??£??\????????£?????¢???x??§?¨?
        y = y_coordinates[adjacent_square] # ??£??\????????£?????¢???y??§?¨?

        (dx, dy) = adjacent_vector[direction]

        x_coordinates.append(x + dx)
        y_coordinates.append(y + dy)

    max_x = max(x_coordinates)
    min_x = min(x_coordinates)
    max_y = max(y_coordinates)
    min_y = min(y_coordinates)

    print(max_x - min_x + 1, max_y - min_y + 1)

Submission status: Accepted

Solution code:
'''
hardest 2.
Aizu Online Judge 1165: Pablo Squarson's Headache
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1165

## ?§£??¬

??£?????¢?????????????????£?????§???????????¢?????\????????????????????¢???????°????????????¨???????????????????????????????????§???
??£?????¢???????????¢???????????????????????????????????¨???????????¶???????????????

?´°????????¬?????????????????????????????§?????????????????\???????????????????????§?§£?????????

1. ?°´????????????x???,?????´?????????y?????¨?????????
2. ???????????£?????¢??????????????§?¨????(0, 0)??¨????????????????????£?????¢?????§?¨?????±???????
3. ????????¢????????????  (?????£?????¢???x??§?¨?????????§???) - (?????£?????¢???x??§?¨????????°????) + 1
4. ????????¢???????????????(?????£?????¢???y??§?¨?????????§???) - (?????£?????¢???y??§?¨????????°????) + 1

?????±???????????????????????°?????????????????????(AOJ?????????????????????????????????????????????????????¨????????????????????????)

'''

adjacent_vectors = [
    (-1, 0), # left
    (0, -1), # down
    (1, 0),  # right
    (0, 1)   # up
]

while True:
    num_squares = int(input())

    if num_squares == 0:
        break

    x_coordinates = [0] # x??§?¨?????????????
    y_coordinates = [0] # y??§?¨?????????????

    for _ in range(num_squares-1):
        # adjacent_square: ??£??\????????£?????¢?????????
        adjacent_square, direction = map(int, input().split())

        x = x_coordinates[adjacent_square] # ??£??\????????£?????¢???x??§?¨?
        y = y_coordinates[adjacent_square] # ??£??\????????£?????¢???y??§?¨?

        (dx, dy) = adjacent_vectors[direction]

        x_coordinates.append(x + dx)
        y_coordinates.append(y + dy)

    max_x = max(x_coordinates)
    min_x = min(x_coordinates)
    max_y = max(y_coordinates)
    min_y = min(y_coordinates)

    print(max_x - min_x + 1, max_y - min_y + 1)

Submission status: Accepted

Solution code:
d = [[-1,0],[0,1],[1,0],[0,-1]]
while True:
    n = int(input())
    if not(n): break
    # l = [[1,1]]
    w,h = [1],[1]
    for i in range(n-1):
        l = list(map(int,input().split()))
        w.append(w[l[0]]+d[l[1]][0])
        h.append(h[l[0]]+d[l[1]][1])
    print(max(w)-min(w)+1,max(h)-min(h)+1)

Submission status: Accepted

Solution code:
# coding: utf-8
# Here your code !
#coding: utf-8

while True:
    n = int(raw_input())
    if n == 0:
        break
    coolist = [(0, 0)]
    xmax = 0
    xmin = 0
    ymax = 0
    ymin = 0
    for i in range(n-1):
        l = map(int, raw_input().split())
        if l[1] == 0:
            coo = (coolist[l[0]][0] - 1,coolist[l[0]][1])
            if xmin > coolist[l[0]][0] - 1:
                xmin = coolist[l[0]][0] - 1
            coolist.append(coo)
        if l[1] == 1:
            coo = (coolist[l[0]][0],coolist[l[0]][1] - 1)
            if ymin > coolist[l[0]][1] - 1:
                ymin = coolist[l[0]][1] - 1
            coolist.append(coo)
        if l[1] == 2:
            coo = (coolist[l[0]][0] + 1,coolist[l[0]][1])
            if xmax < coolist[l[0]][0] + 1:
                xmax = coolist[l[0]][0] + 1
            coolist.append(coo)
        if l[1] == 3:
            coo = (coolist[l[0]][0],coolist[l[0]][1] + 1)
            if ymax < coolist[l[0]][1] + 1:
                ymax = coolist[l[0]][1] + 1
            coolist.append(coo)
    print xmax-xmin+1,ymax-ymin+1

Submission status: Accepted

Solution code:
d = [[-1,0],[0,1],[1,0],[0,-1]]
while True:
    n = int(input())
    if n==0: break
    x,y = [0],[0]
    for _ in range(n-1):
        vn,vd = map(int,input().split())
        x,y = x+[x[vn]+d[vd][0]],y+[y[vn]+d[vd][1]]
    print(max(x)-min(x)+1,max(y)-min(y)+1)

Submission status: Accepted

Solution code:
import sys

def solve():
    dx = (-1, 0, 1, 0,)
    dy = (0, -1, 0, 1,)

    while 1:
        N = int(sys.stdin.readline().rstrip())

        if N == 0:
            return

        pos = [None] * N
        pos[0] = (0, 0)

        top = 0
        btm = 0
        left = 0
        right = 0

        for i in range(N - 1):
            ni, di = map(int, sys.stdin.readline().split())
            x, y = pos[ni]
            x += dx[di]
            y += dy[di]
            pos[i + 1] = (x, y)
            top = max(top, y)
            btm = min(btm, y)
            left = min(left, x)
            right = max(right, x)

        print(right - left + 1, top - btm + 1)


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
while 1:
    n = input()
    if not n:
        break
    s = [(0, 0)]
    for i in xrange(n-1):
        p, d = map(int, raw_input().split())
        x, y = s[p]
        dx, dy = dd[d]
        s.append((x + dx, y + dy))
    xs = [e[0] for e in s]
    ys = [e[1] for e in s]
    print max(xs)-min(xs)+1, max(ys)-min(ys)+1

Submission status: Accepted

Solution code:
dir = [(-1,0),(0,1),(1,0),(0,-1)]
while True:
    N = int(input())
    if N == 0: break
    sq = [(0,0)]
    for i in range(1,N):
        n,d = map(int,input().split())
        dx,dy = dir[d]
        sq.append((sq[n][0]+dx, sq[n][1]+dy))
    maxx = maxy = minx = miny = 0
    for x,y in sq:
       maxx = max(maxx,x)
       maxy = max(maxy,y)
       minx = min(minx,x)
       miny = min(miny,y)
    w = maxx - minx + 1
    h = maxy - miny + 1
    print('{0} {1}'.format(w,h))

Submission status: Accepted

Solution code:
while 1:
    N = int(input())
    if N ==0:break
    max_h = 0
    min_h = 0
    max_w = 0
    min_w = 0
    data=[(0,0)]
    for _ in range(N-1):
        n,d = list(map(int,input().split()))
        if d ==0:current = (data[n][0]-1,data[n][1])
        if d ==1:current = (data[n][0],data[n][1]-1)
        if d ==2:current = (data[n][0]+1,data[n][1])
        if d ==3:current = (data[n][0],data[n][1]+1)
        if max_h < current[1]:max_h = current[1]
        if min_h > current[1]:min_h = current[1]
        if max_w < current[0]:max_w = current[0]
        if min_w > current[0]:min_w = current[0]
        data.append(current)
    print(abs(max_w-min_w)+1,abs(max_h-min_h)+1)

Submission status: Accepted

Solution code:
while True:
    N = int(input())
    if N == 1:
        print(1, 1)
    elif N == 0:
        quit()
    else:
        h, w = [0], [0]
        for i in range(N-1):
            n, d = map(int, input().split())
            if d == 0:
                x, y = -1, 0
            elif d == 1:
                x, y = 0, -1
            elif d ==2:
                x, y = 1, 0
            else:
                x, y = 0, 1
            h.append(h[n] + y)
            w.append(w[n] + x)
        print(abs(max(w)-min(w))+1, abs(max(h)-min(h))+1)

Submission status: Accepted

Solution code:
dx = (-1, 0, 1, 0)
dy = (0, 1, 0, -1)

while True:
    n = int(input())
    if n == 0:
        break

    x = list()
    y = list()
    x.append(0)
    y.append(0)
    for i in range(n - 1):
        k, d = map(int, input().split())
        x.append(x[k] + dx[d])
        y.append(y[k] + dy[d])
    
    print(max(x) - min(x) + 1, max(y) - min(y) + 1)

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

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():
    rr = []

    dd = [(0,-1),(1,0),(0,1),(-1,0)]

    while True:
        n = I()
        if n == 0:
            break
        a = [(0,0)]
        for _ in range(n-1):
            i,di = LI()
            ai = a[i]
            d = dd[di]
            a.append((ai[0]+d[0], ai[1]+d[1]))
        y = sorted(list(map(lambda x: x[0], a)))
        x = sorted(list(map(lambda x: x[1], a)))
        rr.append('{} {}'.format(x[-1]-x[0]+1, y[-1]-y[0]+1))

    return '\n'.join(map(str, rr))


print(main())

Submission status: Accepted

Solution code:
while 1:
    n=int(input())
    if not n:break
    p=[(0,0)]
    b=[0,0]
    for _ in range(n-1):
        idx,d=map(int,input().split())
        b=list(p[idx])
        if d==0:
            b[0]-=1
        elif d==1:
            b[1]-=1
        elif d==2:
            b[0]+=1
        elif d==3:
            b[1]+=1
        p.append(tuple(b))
    w=len({i[0] for i in p})
    h=len({i[1] for i in p})
    print(w,h)

Submission status: Accepted

Solution code:
import sys
import collections

while True:
    N = int(sys.stdin.readline())
    if N == 0:
        break
    
    pos = {0:(0, 0)}
    
    for i in xrange(N - 1):
        n, d = map(int, sys.stdin.readline().split())
        if d == 0:
            pos[i + 1] = (pos[n][0] - 1, pos[n][1])
        elif d == 1:
            pos[i + 1] = (pos[n][0], pos[n][1] - 1)
        elif d == 2:
            pos[i + 1] = (pos[n][0] + 1, pos[n][1])
        elif d == 3:
            pos[i + 1] = (pos[n][0], pos[n][1] + 1)
    
    max_x = min_x = max_y = min_y = 0
    for x, y in pos.values():
        max_x = max(x, max_x)
        min_x = min(x, min_x)
        max_y = max(y, max_y)
        min_y = min(y, min_y)
    
    print max_x - min_x + 1, max_y - min_y + 1

Submission status: Accepted

Solution code:
while True:
    N=input()
    if N==0:break
    x,y=[0]*N,[0]*N
    tx,ty=(-1,0,1,0),(0,-1,0,1)
    for i in range(1,N):
        n,d=map(int,raw_input().split())
        x[i]=x[n]+tx[d]
        y[i]=y[n]+ty[d]
    print max(x)-min(x)+1,max(y)-min(y)+1

Submission status: Accepted

Solution code:
dx,dy = [-1,0,1,0],[0,-1,0,1]
while 1:
	N = input()
	if N == 0: break
	x,y = [0]*N,[0]*N
	for i in range(1,N):
		n,d = map(int,raw_input().split())
		x[i] = x[n] + dx[d]
		y[i] = y[n] + dy[d]
	print max(x) - min(x) + 1, max(y) - min(y) + 1

Submission status: Accepted

Solution code:
dx,dy = [-1,0,1,0],[0,-1,0,1]
while 1:
	N = input()
	if N == 0: break
	x,y = [0]*N,[0]*N
	for i in range(1,N):
		n,d = map(int,raw_input().split())
		x[i] = x[n]+dx[d]
		y[i] = y[n]+dy[d]
	print max(x)-min(x)+1,max(y)-min(y)+1

Submission status: Accepted

Solution code:
#21:35

offset_y = [0,-1,0,1]
offset_x = [-1,0,1,0]

while True:
    num_sqale = int(input())
    if num_sqale ==0:
        break
    work =  [[-1] * num_sqale*2 for i in range(num_sqale*2)]
    # 真ん中を初期化
    work[num_sqale][num_sqale] = 0
    index_x = [num_sqale]
    index_y = [num_sqale]

    for i in range(1,num_sqale):
        target,offset = map(int,input().split())
        hight = index_y[target]
        witdh = index_x[target]
        n_hight = hight + offset_y[offset]
        n_width = witdh + offset_x[offset]
        work[n_hight][n_width] = i
        index_x.append(n_width)
        index_y.append(n_hight)
        
    print(str(max(index_x)-min(index_x)+1)+" "+str(max(index_y)-min(index_y)+1))

Submission status: Accepted

Solution code:
def put_S(n, d) :
    global square
    if d == 0 :
        new_i = square[n][0] - 1
        new_j = square[n][1]
    elif d == 1 :
        new_i = square[n][0]
        new_j = square[n][1] - 1
    elif d == 2 :
        new_i = square[n][0] + 1
        new_j = square[n][1]
    elif d == 3 :
        new_i = square[n][0]
        new_j = square[n][1] + 1
        
    square.append([new_i, new_j])
    
while True :
    N = int(input())
    if N == 0 :
        break
    square = [[0, 0]]
    for i in range(N-1) :
        n, d = map(int, input().split())
        put_S(n, d) 
    
    sort_x_square = sorted(square)
    sort_y_square = sorted(square, key=lambda x:x[1])
    print(sort_x_square[-1][0] - sort_x_square[0][0]+1, sort_y_square[-1][1] - sort_y_square[0][1]+1)

Submission status: Accepted

Solution code:
while True:
    N = int(input())
    
    w=[0]*N
    h=[0]*N
    wx=[-1,0,1,0]
    hy=[0,-1,0,1]
    
    if N == 0:
        break
    
    for i in range(1,N):
        n,d = map(int,input().split())
        w[i] = w[n]+wx[d]
        h[i] = h[n]+hy[d]
        
    print(max(w)-min(w)+1,max(h)-min(h)+1)

Submission status: Accepted

Solution code:
while 1:
    n = int(input())
    if n==0: break
    if n==1: print(1, 1); continue
    a = [0]
    b = [0]
    for i in range(n-1):
        m, d = map(int,input().split())
        if d == 0:
            a.append(a[m]-1)
            b.append(b[m])
        elif d == 1:
            a.append(a[m])
            b.append(b[m]-1)
        elif d == 2:
            a.append(a[m]+1)
            b.append(b[m])
        else:
            a.append(a[m])
            b.append(b[m]+1)
    print(max(a)-min(a)+1, max(b)-min(b)+1)

Submission status: Accepted

Solution code:
"""

二次元のデータセットをリスト1つとして管理し
これを１つの正方形とする。

まず、指定されたindexのx,y座標リストを取得する
それぞれの方向によって、




"""

while(1):

	blocks = []
	blocks.append([0,0])
	#print(blocks[0])
	#print(blocks[0][1])
	N = input()
	
	N = int(N)
	
	if N == 0:
		break
	list_y = []
	list_x = []
	
	l_count = N-1
	num = 1
	
	while(1):
		
		if l_count == 0:
			break
			
		place,vector = input().split() #nはindex indexは正方形を１つずつおいていくときに、1ずつ上がっていく
		# まず、n番目のリストを取得し, dによって4通りの数値演算。それはリストの0番目がx, 1番目がyとして判断すれば良い
		place = int(place)
		vector = int(vector)
		
		get_x = blocks[place][0]
		get_y = blocks[place][1]
		
		if vector == 0:
			get_x -= 1
			blocks.append([get_x,get_y])
		elif vector == 1:
			get_y -= 1
			blocks.append([get_x,get_y])
		elif vector == 2:
			get_x += 1
			blocks.append([get_x,get_y])
		elif vector == 3:
			get_y += 1
			blocks.append([get_x,get_y])
		
		l_count -= 1
		num += 1
	
	#print(blocks)	
	
	
	for i in range(N):
		list_x.append(blocks[i][0])
		list_y.append(blocks[i][1])
	
	#print(list_x)
	#print(list_y)
	"""
	print(max(list_x))
	print(min(list_y))
	"""	
	
	print('%d %d' % (max(list_x)-min(list_x)+1,max(list_y)-min(list_y)+1))	
		
	
	#max_x =  [kv for kv in blocks[0] if kv[0] == max(blocks[0])] 
	
	#print(max_x)

Submission status: Accepted

Solution code:
def solve(N, nd):
    dire = [(0,-1), (-1,0), (0,1), (1,0)]
    table = [[0]*(2*N+1) for i in range(2*N+1)]
    table[N][N] = 1
    position = [None]*N
    position[0] = (N, N)
    for i,ndi in enumerate(nd,start=1):
        n, d = ndi
        y, x = position[n]
        ny, nx = y+dire[d][0], x+dire[d][1]
        table[ny][nx] = 1
        position[i] = (ny, nx)

    left, right, top, bottom = 2*N, 0, 2*N, 0
    for i in range(2*N):
        for j in range(2*N):
            if (table[i][j]):
                left = min(left, j)
                right = max(right, j)
                top = min(top, i)
                bottom = max(bottom, i)
    return (right-left+1, bottom-top+1)

def main():
    ans = []
    while True:
        N = int(input())
        if (not N):
            break
        nd = [list(map(int, input().split())) for i in range(N-1)]
        ans.append(solve(N, nd))
    for i in ans:
        print(*i)
    
main()

Submission status: Accepted

Solution code:
move = [[-1, 0], [0, 1], [1, 0], [0, -1]]
def main(n):
    field = [(0, 0)]
    for _ in range(n - 1):
        ni, di = map(int, input().split())
        field.append((field[ni][0] + move[di][0], field[ni][1] + move[di][1]))
    minx = field[0][0]
    maxx = field[0][0]
    miny = field[0][1]
    maxy = field[0][1]
    for fx, fy in field:
        minx = min(minx, fx)
        maxx = max(maxx, fx)
        miny = min(miny, fy)
        maxy = max(maxy, fy)
    print(maxx - minx + 1, maxy - miny + 1)


while 1:
    n = int(input())
    if n == 0:
        break
    main(n)

Submission status: Accepted

Solution code:
"角角画伯，かく悩みき"

# それぞれの座標を記録していく（一度設置したタイルの座標が変わることはない）

while True:
    N = int(input())
    if N == 0:
        break
    tile_coodinates = {}
    tile_coodinates[0] = (0, 0)
    for i in range(1, N):
        n, d = map(int, input().split())
        if d == 0:
            tile_coodinates[i] = (tile_coodinates[n][0]-1, tile_coodinates[n][1])
        if d == 1:
            tile_coodinates[i] = (tile_coodinates[n][0], tile_coodinates[n][1]-1)
        if d == 2:
            tile_coodinates[i] = (tile_coodinates[n][0]+1, tile_coodinates[n][1])
        if d == 3:
            tile_coodinates[i] = (tile_coodinates[n][0], tile_coodinates[n][1]+1)

    zahyou_list = list(tile_coodinates.values())

    min_x = 300
    max_x = -300
    min_y = 300
    max_y = -300

    for x, y in zahyou_list:
        min_x = min(min_x, x)
        max_x = max(max_x, x)

        min_y = min(min_y, y)
        max_y = max(max_y, y)

    print(max_x-min_x+1, max_y-min_y+1)

Submission status: Accepted

Solution code:
while True:
    N = int(input())
    if N == 0:
        break
    min_w = 0
    max_w = 0
    min_h = 0
    max_h = 0
    points = [[0, 0]]
    for i in range(N-1):
        n, d = map(int, input().split())
        w = points[n][0]
        h = points[n][1]
        if d == 0:
            w -= 1
            min_w = min(min_w, w)
        elif d == 1:
            h -= 1
            min_h = min(min_h, h)
        elif d == 2:
            w += 1
            max_w = max(max_w, w)
        elif d == 3:
            h += 1
            max_h = max(max_h, h)
        points.append([w, h])
    print(max_w + 1 - min_w, max_h + 1 - min_h)