All Tracks Algorithms Greedy Algorithms Basics of Greedy Algorithms Problem

The Infinite String
Tag(s):

Binary Search, Greedy, Hard

Problem
Editorial
Analytics

You are given N words, each of length at max \(50\).
All words consist of small case alphabets and digits 0 to 9.

You concatenate all the N words to form a bigger string A.

An infinite string S is built by performing infinite steps on A recursively:
In \(i^{th}\) step, A is concatenated with \('$'\) i times followed by reverse of A.

\(A = A | $...$ | reverse(A)\), where | denotes concatenation.

Eg: let \(A = 123\)
Step \(1: A = 123$321\)
Step \(2: A = 123$321$\$123$321\)
And so on… The infinite string thus obtained is S.

You are given Q queries.
For each query, you are given an integer \(POS\) and you have to print the character at position \(POS\) in the infinite string S.

Input Format
First line contains an integer N, the size of array.
Next line contains N space separated integers \(W_1, W_2, … , W_N\).
Next line contains Q, the number of queries.
Q lines follow.
Each line contains an integer \(POS\) i.e the position for query.

Output Format
For each query, print the answer in a new line.

Constraints
\(1 <= N <= 10^4\)
\(0 < |W_i| <= 50\)
\(1 <= Q <= 10^4\)
\(1 <= POS <= 10^{18}\)

SAMPLE INPUT
3
rac 1e ffjn
2
3
10
SAMPLE OUTPUT
c
$
Explanation

The string \(A = rac1effjn\).
The infinite string \(S = rac1effjn$njffe1car\)…..
The \(3^{rd}\) character is c.
The \(10^{th}\) character is \(\\)$.

Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: Bash, C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Swift-4.1, TypeScript, Visual Basic

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

This Problem was Asked in

National Instruments

Challenge Name

National Instruments Intern Hiring Challenge

OTHER PROBLEMS OF THIS CHALLENGE
Notifications
View All Notifications

?