An endless floor is covered with tiles, and at first every tile is white.
A tile's position is written as two integers (x, y). x grows to the right and y grows upward.
A robot starts on tile (0, 0). The tile it stands on at the start is not flipped.
You are given n commands in order. A command is a direction and a step count k, and the robot tries to walk k steps in that direction, one tile per step. The direction is one of U (up), D (down), L (left), R (right).
If the tile the robot steps onto is white, that tile turns black and the robot goes on with its remaining steps.
If the tile it steps onto is black, that tile turns white, and the robot stays on that tile and drops the remaining steps of that command. The next command starts from there.
After all commands, print the number of black tiles and the position where the robot stands.
Input
The first line has n. Each of the next n lines has one command: a direction letter and k separated by one space. 1 ≤ n ≤ 2,000, 1 ≤ k ≤ 9,000, and the sum of k over all commands is at most 9,000
Output
On the first line the number of black tiles; on the second line the x and y of the robot's position separated by one space
Example 1 · stdin
3
R 3
L 5
R 2
stdout
1
3 0
Example 2 · stdin
6
R 11
U 10
L 10
D 12
L 3
R 5
stdout
41
-1 0
main.py
Error List00F8 ↓ · ⇧F8 ↑
Input (stdin)
When you run, these lines are fed to input()/stdin in order (the program doesn't stop to ask).
$ Ready
Open this on a computer to write and run code. On mobile you can read the problem and the solutions.
In other languagesShow solutions by language · 8 languages
Keep the positions of the black tiles in a set and ask at every step whether the tile is in it (Python in, JS has, Java contains, C# Contains, C++ find, Craykon Contains). The hard part is that each language has its own way to store a two-number position as one element. Python takes a tuple (x, y), C# takes a tuple in HashSet<(int, int)>, and C++ takes a pair in std::set; all three compare by value (C++ unordered_set has no hash for pair, so it does not compile as is). In Java a record gets value-based equals and hashCode. JS/TS and Craykon turn the position into a string "x,y"; Craykon uses the keys of Dict() as a set and deletes with Remove. C has no set, so the positions go into an array that is searched from the start. With only 9,000 steps that is still fast enough. Trap one: if you put arrays [x, y] into a JS/TS Set, arrays with the same contents count as different elements, so has is always false. In example 1 the robot never recognises a black tile and you get 10 and 0 0. Java's HashSet<int[]> and C#'s HashSet<int[]> give false in the same way. Trap two: putting a list [x, y] into a Python set stops with TypeError (unhashable type: 'list'). Use a tuple instead of a changeable list. Trap three: if you build the string key without a separator, different positions get the same key. In example 2 both (11, 0) and (1, 10) become "110", so the white tile (1, 10) is taken for a black one, the robot stops, and you get 39 instead of 41.
Pythonmain.py · 20 lines
import sysMOVES = {"U": (0, 1), "D": (0, -1), "L": (-1, 0), "R": (1, 0)}lines = sys.stdin.read().split("\n")n = int(lines[0])black = set() # 검은 타일의 자리 (x, y)x = y = 0for line in lines[1:n + 1]: d, k = line.split() dx, dy = MOVES[d] for _ in range(int(k)): x += dx y += dy if (x, y) in black: black.remove((x, y)) # 검은 타일: 흰색으로 뒤집고 남은 걸음을 버린다 break black.add((x, y)) # 흰 타일: 검은색으로 뒤집고 이어 간다print(len(black))print(x, y)
JavaScriptmain.js · 23 lines
const lines = require("fs").readFileSync(0, "utf8").split("\n");const n = Number(lines[0]);const MOVES = { U: [0, 1], D: [0, -1], L: [-1, 0], R: [1, 0] };// 배열 [x, y]는 내용이 같아도 다른 원소로 치므로, 문자열 "x,y"를 넣는다const black = new Set();let x = 0;let y = 0;for (let i = 1; i <= n; i++) { const [d, k] = lines[i].trim().split(" "); const [dx, dy] = MOVES[d]; for (let step = 0; step < Number(k); step++) { x += dx; y += dy; const key = `${x},${y}`; if (black.has(key)) { black.delete(key); // 검은 타일: 흰색으로 뒤집고 남은 걸음을 버린다 break; } black.add(key); // 흰 타일: 검은색으로 뒤집고 이어 간다 }}console.log(black.size);console.log(`${x} ${y}`);
TypeScriptmain.ts · 25 lines
import { readFileSync } from "node:fs";const lines: string[] = readFileSync(0, "utf8").split("\n");const n: number = Number(lines[0]);const MOVES: Record<string, [number, number]> = { U: [0, 1], D: [0, -1], L: [-1, 0], R: [1, 0] };// 배열 [x, y]는 내용이 같아도 다른 원소로 치므로, 문자열 "x,y"를 넣는다const black = new Set<string>();let x = 0;let y = 0;for (let i = 1; i <= n; i++) { const [d, k]: string[] = lines[i].trim().split(" "); const [dx, dy]: [number, number] = MOVES[d]; for (let step = 0; step < Number(k); step++) { x += dx; y += dy; const key: string = `${x},${y}`; if (black.has(key)) { black.delete(key); // 검은 타일: 흰색으로 뒤집고 남은 걸음을 버린다 break; } black.add(key); // 흰 타일: 검은색으로 뒤집고 이어 간다 }}console.log(black.size);console.log(`${x} ${y}`);
JavaMain.java · 40 lines
import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.HashSet;import java.util.Set;public class Main { // record는 equals와 hashCode를 값으로 만들어 주므로 집합에 그대로 넣을 수 있다 record Tile(int x, int y) {} public static void main(String[] args) throws IOException { BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); int n = Integer.parseInt(in.readLine().trim()); Set<Tile> black = new HashSet<>(); int x = 0, y = 0; for (int i = 0; i < n; i++) { String[] parts = in.readLine().trim().split(" "); int dx = 0, dy = 0; switch (parts[0]) { case "U" -> dy = 1; case "D" -> dy = -1; case "L" -> dx = -1; default -> dx = 1; } int k = Integer.parseInt(parts[1]); for (int step = 0; step < k; step++) { x += dx; y += dy; Tile tile = new Tile(x, y); if (black.contains(tile)) { black.remove(tile); // 검은 타일: 흰색으로 뒤집고 남은 걸음을 버린다 break; } black.add(tile); // 흰 타일: 검은색으로 뒤집고 이어 간다 } } System.out.println(black.size()); System.out.println(x + " " + y); }}
C#Main.cs · 39 lines
using System;using System.Collections.Generic;class Program{ static void Main() { int n = int.Parse(Console.ReadLine().Trim()); // 튜플 (x, y)는 값이 같으면 같은 원소다 var black = new HashSet<(int, int)>(); int x = 0, y = 0; for (int i = 0; i < n; i++) { string[] parts = Console.ReadLine().Trim().Split(' '); int dx = 0, dy = 0; switch (parts[0]) { case "U": dy = 1; break; case "D": dy = -1; break; case "L": dx = -1; break; default: dx = 1; break; } int k = int.Parse(parts[1]); for (int step = 0; step < k; step++) { x += dx; y += dy; if (black.Contains((x, y))) { black.Remove((x, y)); // 검은 타일: 흰색으로 뒤집고 남은 걸음을 버린다 break; } black.Add((x, y)); // 흰 타일: 검은색으로 뒤집고 이어 간다 } } Console.WriteLine(black.Count); Console.WriteLine($"{x} {y}"); }}
C++main.cpp · 36 lines
#include <iostream>#include <set>#include <utility>using namespace std;int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; // pair는 값으로 견주므로 std::set에 그대로 넣을 수 있다 set<pair<int, int>> black; int x = 0, y = 0; for (int i = 0; i < n; i++) { char d; int k; cin >> d >> k; int dx = 0, dy = 0; if (d == 'U') dy = 1; else if (d == 'D') dy = -1; else if (d == 'L') dx = -1; else dx = 1; for (int step = 0; step < k; step++) { x += dx; y += dy; auto it = black.find({x, y}); if (it != black.end()) { black.erase(it); // 검은 타일: 흰색으로 뒤집고 남은 걸음을 버린다 break; } black.insert({x, y}); // 흰 타일: 검은색으로 뒤집고 이어 간다 } } cout << black.size() << '\n' << x << ' ' << y << '\n'; return 0;}
Cmain.c · 49 lines
#include <stdio.h>#define MAXSTEPS 9000/* C에는 집합이 없다. 검은 타일의 자리를 배열에 모아 두고 처음부터 찾는다. 걸음이 많아야 9,000번이라 검은 타일도 9,000개를 넘지 않는다. */static int bx[MAXSTEPS], by[MAXSTEPS];static int count = 0;/* (x, y)가 든 칸 번호를 돌려준다. 없으면 -1 */static int find(int x, int y) { for (int i = 0; i < count; i++) { if (bx[i] == x && by[i] == y) return i; } return -1;}int main(void) { int n; scanf("%d", &n); int x = 0, y = 0; for (int i = 0; i < n; i++) { char d; int k; scanf(" %c %d", &d, &k); int dx = 0, dy = 0; if (d == 'U') dy = 1; else if (d == 'D') dy = -1; else if (d == 'L') dx = -1; else dx = 1; for (int step = 0; step < k; step++) { x += dx; y += dy; int at = find(x, y); if (at >= 0) { /* 검은 타일: 마지막 칸을 그 자리로 옮겨 지우고, 남은 걸음을 버린다 */ count--; bx[at] = bx[count]; by[at] = by[count]; break; } bx[count] = x; /* 흰 타일: 검은색으로 뒤집고 이어 간다 */ by[count] = y; count++; } } printf("%d\n%d %d\n", count, x, y); return 0;}
Craykonmain.cray · 43 lines
n = Console.ReadLine().ToNumber();// 사전의 열쇠를 집합처럼 쓴다. 자리는 문자열 "x,y"로 바꿔 넣는다black = Dict();x = 0;y = 0;for (i = 0; i < n; i++){ parts = Console.ReadLine().Trim().Split(); dx = 0; dy = 0; switch (parts[0]) { case "U": dy = 1; break; case "D": dy = -1; break; case "L": dx = -1; break; default: dx = 1; break; } k = parts[1].ToNumber(); for (step = 0; step < k; step++) { x += dx; y += dy; key = x + "," + y; if (black.Contains(key)) { // 검은 타일: 흰색으로 뒤집고 남은 걸음을 버린다 black.Remove(key); break; } // 흰 타일: 검은색으로 뒤집고 이어 간다 black[key] = true; }}Console.WriteLine(black.Count);Console.WriteLine(x + " " + y);