Problem:


Problem B: The Last Ant

A straight tunnel without branches is crowded with busy ants coming and going. Some ants walk left to right and others right to left. All ants walk at a constant speed of 1 cm/s. When two ants meet, they try to pass each other. However, some sections of the tunnel are narrow and two ants cannot pass each other. When two ants meet at a narrow section, they turn around and start walking in the opposite directions. When an ant reaches either end of the tunnel, it leaves the tunnel.

The tunnel has an integer length in centimeters. Every narrow section of the tunnel is integer centimeters distant from the both ends. Except for these sections, the tunnel is wide enough for ants to pass each other. All ants start walking at distinct narrow sections. No ants will newly enter the tunnel. Consequently, all the ants in the tunnel will eventually leave it. Your task is to write a program that tells which is the last ant to leave the tunnel and when it will.

Figure B.1 shows the movements of the ants during the first two seconds in a tunnel 6 centimeters long. Initially, three ants, numbered 1, 2, and 3, start walking at narrow sections, 1, 2, and 5 centimeters distant from the left end, respectively. After 0.5 seconds, the ants 1 and 2 meet at a wide section, and they pass each other. Two seconds after the start, the ants 1 and 3 meet at a narrow section, and they turn around.

Figure B.1 corresponds to the first dataset of the sample input.

Figure B.1. Movements of ants

Input

The input consists of one or more datasets. Each dataset is formatted as follows.

n l
d1 p1
d2 p2
...
dn pn

The first line of a dataset contains two integers separated by a space. n (1 ≤ n ≤ 20) represents the number of ants, and l (n + 1 ≤ l ≤ 100) represents the length of the tunnel in centimeters. The following n lines describe the initial states of ants. Each of the lines has two items, di and pi, separated by a space. Ants are given numbers 1 through n. The ant numbered i has the initial direction di and the initial position pi. The initial direction di (1 ≤ i ≤ n) is L (to the
left) or R (to the right). The initial position pi (1 ≤ i ≤ n) is an integer specifying the distance from the left end of the tunnel in centimeters. Ants are listed in the left to right order, that is, 1 ≤ p1 < p2 < ... < pn ≤ l - 1.

The last dataset is followed by a line containing two zeros separated by a space.

Output

For each dataset, output how many seconds it will take before all the ants leave the tunnel, and which of the ants will be the last. The last ant is identified by its number. If two ants will leave at the same time, output the number indicating the ant that will leave through the left end of the tunnel.

Sample Input

3 6
R 1
L 2
L 5
1 10
R 1
2 10
R 5
L 7
2 10
R 3
L 8
2 99
R 1
L 98
4 10
L 1
R 2
L 8
R 9
6 10
R 2
R 3
L 4
R 6
L 7
L 8
0 0

Output for the Sample Input

5 1
9 1
7 1
8 2
98 2
8 2
8 3



Sample input:
3 6
R 1
L 2
L 5
1 10
R 1
2 10
R 5
L 7
2 10
R 3
L 8
2 99
R 1
L 98
4 10
L 1
R 2
L 8
R 9
6 10
R 2
R 3
L 4
R 6
L 7
L 8
0 0


Sample output:
5 1
9 1
7 1
8 2
98 2
8 2
8 3

Submission status: Wrong Answer

Solution code:
while 1:
    n,l = map(int,raw_input().split())
    if n == 0: break
    
    tunnel = [[] for i in xrange(l-1)]
    for i in xrange(1,n+1):
        d,p = raw_input().split()
        tunnel[int(p)-1].append(i if d == "R" else -i)
    t = num = 0
    while sum(sum(unit) for unit in tunnel) != 0:
        for i in xrange(l-2,-1,-1):
            for a in tunnel[i]:
                if a > 0:
                    tunnel[i].remove(a)
                    if i == l-2:
                        num = a
                    else:
                        tunnel[i+1].append(a)
        for i in xrange(l-1):
            for a in tunnel[i]:
                if a < 0:
                    tunnel[i].remove(a)
                    if i == 0:
                        num = -a
                    else:
                        tunnel[i-1].append(a)
        for i in xrange(l-1):
            if len(tunnel[i]) > 1:
                tunnel[i] = [-a for a in tunnel[i]]
        t += 1
    print t,num

Submission status: Wrong Answer

Solution code:
while 1:
    n,l = map(int,raw_input().split())
    if n == 0: break
    
    R = [0]*(l-1)
    L = [0]*(l-1)
    for i in xrange(1,n+1):
        d,p = raw_input().split()
        p = int(p)-1
        if d == "R": R[p] = i
        else: L[p] = i
    t = num = 0
    while sum(R)+sum(L) != 0:
        if R[-1] > 0: num = R[-1]
        R = [0]+R[:-1]
        if L[0]  > 0: num = L[0]
        L = L[1:]+[0]
        for i in xrange(l-1):
            if min(L[i],R[i]) > 0: R[i],L[i] = L[i],R[i]
        t += 1
        print R
    print t,num

Submission status: Accepted

Solution code:
while 1:
    n,l = map(int,raw_input().split())
    if n == 0: break
    
    tunnel = [[] for i in xrange(l-1)]
    for i in xrange(1,n+1):
        d,p = raw_input().split()
        tunnel[int(p)-1].append(i if d == "R" else -i)
    t = num = 0
    while sum(len(unit) for unit in tunnel) != 0:
        for i in xrange(l-2,-1,-1):
            for a in tunnel[i]:
                if a > 0:
                    tunnel[i].remove(a)
                    if i == l-2:
                        num = a
                    else:
                        tunnel[i+1].append(a)
        for i in xrange(l-1):
            for a in tunnel[i]:
                if a < 0:
                    tunnel[i].remove(a)
                    if i == 0:
                        num = -a
                    else:
                        tunnel[i-1].append(a)
        for i in xrange(l-1):
            if len(tunnel[i]) > 1:
                tunnel[i] = [-a for a in tunnel[i]]
        t += 1
    print t,num

Submission status: Accepted

Solution code:
while 1:
    n,l = map(int,raw_input().split())
    if n == 0: break
    
    tube = [[] for i in xrange(l-1)]
    for i in xrange(1,n+1):
        d,p = raw_input().split()
        tube[int(p)-1].append(i if d == "R" else -i)
    t = num = 0
    while sum(len(ele) for ele in tube) != 0:
        for s in [-1,1]:
            for i in range(l-1)[::s]:
                for a in tube[i]:
                    if -s*a > 0:
                        tube[i].remove(a)
                        if i == (l-2 if s == -1 else 0):
                            num = abs(a)
                        else:
                            tube[i-s].append(a)
        for i in xrange(l-1):
            if len(tube[i]) > 1:
                tube[i] = [-a for a in tube[i]]
        t += 1
    print t,num

Submission status: Accepted

Solution code:
while 1:
    n,l = map(int,raw_input().split())
    if n == 0: break
    R = [0]*(l-1)
    L = [0]*(l-1)
    for i in xrange(1,n+1):
        d,p = raw_input().split()
        p = int(p)-1
        if d == "R": R[p] = i
        else: L[p] = i
    t = num = 0
    while sum(R)+sum(L) != 0:
        if R[-1] > 0: num = R[-1]
        R = [0]+R[:-1]
        if L[0]  > 0: num = L[0]
        L = L[1:]+[0]
        for i in xrange(l-1):
            if min(L[i],R[i]) > 0: R[i],L[i] = L[i],R[i]
        t += 1
    print t,num

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 = 998244353
dd = [(0,-1),(1,0),(0,1),(-1,0)]
ddn = [(0,-1),(1,-1),(1,0),(1,1),(0,1),(-1,-1),(-1,0),(-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():
    rr = []

    while True:
        n,l = LI()
        if n == 0:
            break
        a = []
        b = []
        for _ in range(n):
            d,p = LS()
            if int(p) % 2 == 0:
                a.append((d,int(p),_+1))
            else:
                b.append((d,int(p),_+1))

        lc = 0
        rm = 0
        rf = False
        for d,p,i in a:
            if d == 'L':
                lc += 1
            m = int(p)
            if d == 'R':
                m = l - m
            if rm < m or (rm == m and d == 'L'):
                rm = m
                rf = d == 'R'
        ri = lc
        if rf:
            ri = lc + 1
        ari = -1
        if a:
            ari = a[ri-1][2]

        lc = 0
        rf = False
        af = True
        for d,p,i in b:
            if d == 'L':
                lc += 1
            m = int(p)
            if d == 'R':
                m = l - m
            if rm < m or (rm == m and d == 'L'):
                rm = m
                rf = d == 'R'
                af = False
        ri = lc
        if rf:
            ri = lc + 1
        bri = -1
        if b:
            bri = b[ri-1][2]

        if af:
            rr.append('{} {}'.format(rm, ari))
        else:
            rr.append('{} {}'.format(rm, bri))

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


print(main())

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline

LR = "LR".index

def solve(A, L):
    K = len(A)
    if K == 0:
        return -1, -1, -1
    T = []
    v = -1; last = None
    left = 0
    for i in range(K):
        di, pi, ki = A[i]
        for j in range(i+1, K):
            dj, pj, kj = A[j]
            if di > dj:
                T.append(((pj - pi)//2, i, j))
        if di == 0:
            if v <= pi:
                v = pi
                last = i
                left = 1
        else:
            if v < L - pi:
                v = L - pi
                last = i
                left = 0
    T.sort()
    for _, i, j in T:
        A[i], A[j] = A[j], A[i]
    return v, A[last][2], left

ans = []
while 1:
    N, L = map(int, readline().split())
    if N == 0:
        break
    A = []; B = []
    for i in range(N):
        d, p = readline().split(); d = LR(d); p = int(p)
        if p % 2:
            A.append((d, p, i+1))
        else:
            B.append((d, p, i+1))
    v0, i0, l0 = solve(A, L)
    v1, i1, l1 = solve(B, L)
    if v0 > v1:
        ans.append("%d %d\n" % (v0, i0))
    elif v0 < v1:
        ans.append("%d %d\n" % (v1, i1))
    else:
        if l0:
            ans.append("%d %d\n" % (v0, i0))
        else:
            ans.append("%d %d\n" % (v1, i1))
sys.stdout.writelines(ans)