The Robot (Codeforces 1468K)
Tags: Implement, brute force

There is a robot on a checkered field that is endless in all directions. Initially, the robot is located in the cell with coordinates $$$(0, 0)$$$. He will execute commands which are described by a string of capital Latin letters 'L', 'R', 'D', 'U'. When a command is executed, the robot simply moves in the corresponding direction:  'L': one cell to the left (the $$$x$$$-coordinate of the current cell decreases by $$$1$$$);  'R': one cell to the right (the $$$x$$$-coordinate of the current cell is increased by $$$1$$$);  'D': one cell down (the $$$y$$$-coordinate of the current cell decreases by $$$1$$$);  'U': one cell up (the $$$y$$$-coordinate of the current cell is increased by $$$1$$$). Your task is to put an obstacle in one cell of the field so that after executing the commands, the robot will return to the original cell of its path $$$(0, 0)$$$. Of course, an obstacle cannot be placed in the starting cell $$$(0, 0)$$$. It is guaranteed that if the obstacle is not placed, then the robot will not return to the starting cell.An obstacle affects the movement of the robot in the following way: if it tries to go in a certain direction, and there is an obstacle, then it simply remains in place (the obstacle also remains, that is, it does not disappear).Find any such cell of the field (other than $$$(0, 0)$$$) that if you put an obstacle there, the robot will return to the cell $$$(0, 0)$$$ after the execution of all commands. If there is no solution, then report it.

Input: The first line contains one integer $$$t$$$ ($$$1 \le t \le 500$$$) — the number of test cases.Each test case consists of a single line containing $$$s$$$ — the sequence of commands, which are uppercase Latin letters 'L', 'R', 'D', 'U' only. The length of $$$s$$$ is between $$$1$$$ and $$$5000$$$, inclusive. Additional constraint on $$$s$$$: executing this sequence of commands leads the robot to some cell other than $$$(0, 0)$$$, if there are no obstacles.The sum of lengths of all $$$s$$$ in a test doesn't exceed $$$5000$$$.

Output: For each test case print a single line:  if there is a solution, print two integers $$$x$$$ and $$$y$$$ ($$$-10^9 \le x,y \le 10^9$$$) such that an obstacle in $$$(x, y)$$$ will force the robot to return back to the cell $$$(0, 0)$$$;  otherwise, print two zeroes (i. e. 0 0). If there are multiple answers, you can print any of them.


Sample Inputs:
4
L
RUUDL
LLUU
DDDUUUUU

Sample Outputs:
-1 0
1 2
0 0
0 1

Solution (Python):
import sys
import math

def walk(ind, r_x, r_y, x, y):
    global n
    for k in range(ind + 1, n):
        if st[k] == 'D':
            y -= 1
            if x == r_x and y == r_y:
                y += 1
        elif st[k] == 'L':
            x -= 1
            if x == r_x and y == r_y:
                x += 1
        elif st[k] == 'U':
            y += 1
            if x == r_x and y == r_y:
                y -= 1
        else:
            x += 1
            if x == r_x and y == r_y:
                x -= 1
    if x == 0 and y == 0:
        return True
    else:
        return False
for _ in range(int(input())):
    st = sys.stdin.readline().strip()
    n = len(st)
    x = 0
    y = 0
    r_x = 0
    r_y = 0
    s = set()
    for i in range(n):
        if st[i] == 'D':
            r_y -= 1
        elif st[i] == 'L':
            r_x -= 1
        elif st[i] == 'U':
            r_y += 1
        else:
            r_x += 1
        if (r_x, r_y) not in s:
            ch = walk(i, r_x, r_y, x, y)
            if ch == True:
                print(r_x, r_y)
                break
            s.add((r_x, r_y))
        x = r_x
        y = r_y
    else:
        print(0, 0)

Solution (Python):
import sys
import math
from bisect import bisect_right as br
from statistics import mode
from itertools import combinations as cb

def int_arr():
    return list(map(int, sys.stdin.readline().strip().split()))

def str_arr():
    return list(map(str, sys.stdin.readline().strip().split()))

def input():
    return sys.stdin.readline().strip()

def walk(ind, r_x, r_y, x, y):
    global n
    for k in range(ind + 1, n):
        if st[k] == 'D':
            y -= 1
            if x == r_x and y == r_y:
                y += 1
        elif st[k] == 'L':
            x -= 1
            if x == r_x and y == r_y:
                x += 1
        elif st[k] == 'U':
            y += 1
            if x == r_x and y == r_y:
                y -= 1
        else:
            x += 1
            if x == r_x and y == r_y:
                x -= 1
    if x == 0 and y == 0:
        return True
    else:
        return False
for _ in range(int(input())):
    st = input()
    n = len(st)
    x = 0
    y = 0
    r_x = 0
    r_y = 0
    s = set()
    for i in range(n):
        if st[i] == 'D':
            r_y -= 1
        elif st[i] == 'L':
            r_x -= 1
        elif st[i] == 'U':
            r_y += 1
        else:
            r_x += 1
        if (r_x, r_y) not in s:
            ch = walk(i, r_x, r_y, x, y)
            if ch == True:
                print(r_x, r_y)
                break
            s.add((r_x, r_y))
        x = r_x
        y = r_y
    else:
        print(0, 0)

Solution (Python):
def get_cmd(c):
    if c == 'U':
        return (0, 1)
    if c == 'D':
        return (0, -1)
    if c == 'L':
        return (-1, 0)
    return (1, 0)
t = int(input())
for _ in range(t):
    cmd = [get_cmd(c) for c in input()]
    vars = []
    cx = cy = 0
    for (dx, dy) in cmd:
        cx += dx
        cy += dy
        vars.append((cx, cy))
    for (ox, oy) in vars:
        cx = cy = 0
        for (dx, dy) in cmd:
            nx = cx + dx
            ny = cy + dy
            if (nx, ny) != (ox, oy):
                (cx, cy) = (nx, ny)
        if (cx, cy) == (0, 0):
            print(ox, oy)
            break
    else:
        print(0, 0)