Robots in Chefland

All submissions for this problem are available.
### Read problems statements in [Hindi](http://www.codechef.com/download/translated/COOK112/hindi/ROBOTS.pdf), [Mandarin Chinese](http://www.codechef.com/download/translated/COOK112/mandarin/ROBOTS.pdf), [Russian](http://www.codechef.com/download/translated/COOK112/russian/ROBOTS.pdf), [Vietnamese](http://www.codechef.com/download/translated/COOK112/vietnamese/ROBOTS.pdf), and [Bengali](http://www.codechef.com/download/translated/COOK112/bengali/ROBOTS.pdf) as well. Chefland is a big city which consists of infinite number of junctions on a 2D plane. The junctions are depicted below and they form a hexagonal grid — they satisfy the following conditions:  Two of the junctions have coordinates $(0,0)$ and $(1,0)$.  Each junction $J$ is connected by line segments with six other junctions. These junctions are the vertices of a regular hexagon with side length $1$ and their distances from $J$ are also all equal to $1$. ![](https://codechef_shared.s3.amazonaws.com/download/Images/COOK112/ROBOTS/...) Chef created a robot that can traverse the junctions. Initially, it is in some junction and oriented towards another junction which is connected to it by a line segment. The robot accepts a string of instructions — decimal digits $0$ through $5$. It executes the instructions one by one and stops after executing the final instruction. When the robot executes an instruction denoted by a digit $d$, it first rotates by $60 \cdot d$ degrees counterclockwise and then moves $1$ unit forward, to the junction it is oriented towards. Chef wants to test the robot, so he wrote a string $S$ of $N$ instructions. You should answer $Q$ queries. In each query, Chef wants to give the robot a substring of instructions $S_L, S_{L+1}, \ldots, S_R$; the robot starts in the junction $(0, 0)$ and it is oriented towards $(1, 0)$. You should find the final position (the $x$ and $y$coordinates) of the robot. ### Input  The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.  The first line of each test case contains two spaceseparated integers $N$ and $Q$.  The second line contains a single string $S$ with length $N$.  $Q$ lines follow. Each of these lines contains two spaceseparated integers $L$ and $R$ describing a query. ### Output For each query, print a single line containing two spaceseparated real numbers — the coordinates of the robot. Your answer will be considered correct if the absolute or relative error of each coordinate does not exceed $10^{6}$. **Warning:** Outputting more than 8 digits after floating point may result in exceeding output size limit and receiving "Runtime error" verdict. ### Constraints  $1 \le T \le 1,000$  $1 \le N, Q \le 2 \cdot 10^5$  $1 \le L \le R \le N$  $S$ contains only characters '0', '1', '2', '3', '4' and '5'  the sum of $N$ over all test cases does not exceed $10^6$  the sum of $Q$ over all test cases does not exceed $10^6$ ### Example Input ``` 1 3 3 012 1 1 1 2 2 2 ``` ### Example Output ``` 1.00000000 0.00000000 1.50000000 0.86602540 0.50000000 0.86602540 ```Author:  kingofnumbers 
Editorial  https://discuss.codechef.com/problems/ROBOTS 
Tags  cook112, easymedium, geometry, kingofnumbers, prefixsum, taran_1407, trigonometry 
Date Added:  17112019 
Time Limit:  4 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, SQL, kotlin, PERL6, TEXT, SCM chicken, PYP3, CLOJ, R, COB, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 