1026. Questions and answers
http://acm.timus.ru/problem.aspx?space=1&num=1026
Time Limit: 2.0 second
Memory Limit: 16 MB
Memory Limit: 16 MB
Background
The database of the Pentagon contains a top-secret information. We don’t know what the information is — you know, it’s top-secret, — but we know the format of its representation. It is extremely simple. We don’t know why, but all the data is coded by the natural numbers from 1 up to 5000. The size of the main base (we’ll denote it be N) is rather big — it may contain up to 100 000 those numbers. The database is to process quickly every query. The most often query is: "Which element is i-th by its value?"— with i being a natural number in a range from 1 to N.
Problem
Your program is to play a role of a controller of the database. In the other words, it should be able to process quickly queries like this.
Input
Input of the problem consists of two parts. At first, a database is written, and then there’s a sequence of queries. The format of database is very simple: in the first line there’s a number N, in the next N lines there are numbers of the database one in each line in an arbitrary order. A sequence of queries is written simply as well: in the first line of the sequence a number of queries K (1 ≤ K ≤ 100) is written, and in the next K lines there are queries one in each line. The query "Which element is i-th by its value?" is coded by the number i. A database is separated from a sequence of queries by the string of three symbols "#".
Output
The output should consist of K lines. In each line there should be an answer to the corresponding query. The answer to the query "i" is an element from the database, which is i-th by its value (in the order from the least up to the greatest element).
Sample
| input | output |
|---|---|
5 7 121 123 7 121 ### 4 3 3 2 5 | 121 121 7 123 |
Problem Author: Leonid Volkov
Problem Source: Ural State University Internal Contest October'2000 Junior Session
Problem Source: Ural State University Internal Contest October'2000 Junior Session
My Solution
using System; using System.Collections; using System.Globalization; namespace acm.timus.ru_p1026 { class Program { static void Main(string[] args) { ArrayList list = new ArrayList(100000); NumberFormatInfo nfi = NumberFormatInfo.InvariantInfo; string[] input = Console.In.ReadToEnd().Split(new char[] { ' ', '\t', '\n', '\r' }, StringSplitOptions.RemoveEmptyEntries); int i = 0; int len1 = Int32.Parse(input[0]); for (i = 1; i <= len1; i++) { int n = Int32.Parse(input[i]); list.Add(n); } int len2 = Int32.Parse(input[len1+2]) + len1 + 3; list.Sort(); for (int j = len1 + 3; j < len2; j++) { int n = Int32.Parse(input[j])-1; Console.WriteLine(list[n]); } } } }
Comments
Post new comment