Description

Time limit 5000 ms
Mem limit 1048576 kB
OS Linux
Hello Programmers!
pcIST says hello to you! Now you say hello to the world!
Input
There is no input for this problem.
Output
Output should contain one line, containing the string “Hello World!”.
Problem B. Addition and Subtraction Easy
Time limit 2000 ms
Mem limit 262144 kB
Problem Statement
Joisino wants to evaluate the formula “A op B”. Here, A and B are integers, and the binary operator op is either + or – . Your task is to evaluate the formula instead of her.
Constraints
1 ≦ A,B ≦ 109
op is either + or – .
Input
The input is given from Standard Input in the following format:

Output
Evaluate the formula and print the result.
Sample 1
Input Output
1 + 2 3
Since 1 + 2 = 3, the output should be 3.
Sample 2
Input Output
5 – 7 -2
Problem C. 99 Problems
Time limit 1000 ms
Mem limit 1048576 kB
OS Linux
Ingrid is the founder of a company that sells bicycle parts. She used to set the prices of products quite arbitrarily, but now she has decided that it would be more profitable if the prices end in 99.
You are given a positive integer N, the price of a product. Your task is to find the nearest positive integer to N which ends in 99. If there are two such numbers that are equally close, find the bigger one.
Input
The input contains one integer N (1 ≤ N ≤ 104), the price of a product. It is guaranteed that the number N does not end in 99.
Output
Print one integer, the closest positive integer that ends in 99. In case of a tie, print the bigger one.
Sample 1
Input Output
10 99
Sample 2
Input Output
249 299
Sample 3
Input Output
10000 9999
Problem D. Circle in a Rectangle
Time limit 1000 ms
Mem limit 131072 kB
OS Linux
Write a program which reads a rectangle and a circle, and determines whether the circle is arranged inside the rectangle. As shown in the following figures, the upper right coordinate (W,H) of the rectangle and the central coordinate (x,y) and radius r of the circle are given.

Input
Five integers W, H, x, y and r separated by a single space are given in a line.
Output
Print “Yes” if the circle is placed inside the rectangle, otherwise “No” in a line.
Constraints
−100 ≤ x,y ≤ 100 0 < W,H,r ≤ 100
Sample Input 1
5 4 2 2 1
Sample Output 1
Yes
Sample Input 2
5 4 2 4 1
Sample Output 2
No
Problem E. Multidimensional Hangman

Time limit 600 ms
Mem limit 1048576 kB
Statement Statements (pt) Statements (en) Statements (es)
OS Windows
The Multidimensional Hangman Game has very peculiar rules. In a way, it is like you are playing several games of the traditional Hangman game at the same time, with the di erence that the words don’t have to exist in the dictionary. If you’ve never played Hangman, don’t worry: all the information you need is below.
In the multidimensional version of the game, there are several words on a board, initially unknown, all of the same length. At each turn in the game, you discover some characters from certain word positions (how these characters were discovered is not important for this problem). At a certain point, when only one unknown character remains in each word on the board, the game goes into the all or nothing phase. At this point, you must choose a word that maximizes the number of compatibilities with the words on the board. For a choosen word P , we say it is compatible with a word T on the board if all known letters in T occur in exactly the same positions in P .
Given the known information about the words on the board, you must determine which word to choose for all or nothing phase, which maximizes the number of compatibilities. If there is more than one solution, print the lexicographically smallest. We say that a word P is lexicographically smaller than a word Q if Pi < Qi where Pi is the i-th character of P , Qi is the i-th character of Q and i is the smallest index such that Pi = Qi.
Input
The first line of the input contains two integers N and C satisfying 1 ≤ N ≤ 104 and 1 ≤ C ≤ 12, indicating the number of words on the board and the length of the words it contains. Each of the next N lines contains a word of length C composed only of characters from ‘a’ to ‘z’ except for one of its positions, which will contain a character ‘*’ , indicating that the character at that position is still unknown.
Output
Print a single line, containing, in order, a word T , of length C, and an integer M, such that M is the greatest number of compatibilities a word might have with the input words and T is the lexicographically smallest amongst the words with compatibility M.
Sample 1
Input Output
Sample 2
Input Output
5 4 bon* fon* n*no *eto
*ano nano 2

Problem F. Catch the Thief
Time limit 1000 ms
Code length Limit 50000 B
OS Linux
Read problems statements in Hindi, Mandarin Chinese, Russian, Vietnamese, and Bengali as well.
A policeman wants to catch a thief. Both the policeman and the thief can only move on a line on integer coordinates between 0 and N (inclusive).
Will the policeman be able to catch the thief if they both move optimally? The thief is caught as soon as the policeman and thief meet at the same position at the same time. 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 and only line of each test case contains four space-separated integers x, y, K and N.
Output
For each test case, print a single line containing the string “Yes” if the thief can be caught or “No” if the thief cannot be caught (without quotes).
Constraints
1 ≤ T ≤ 1,000
1 ≤ N ≤ 109
1 ≤ K ≤ N 0 ≤ x,y ≤ N x = y
Sample 1
Input Output
5
0 1 1 1 1 4 1 5
4 2 1 7 3 7 2 10
8 2 3 15 No
No Yes
Yes
Yes
Example case 1: The policeman is at 0 and the thief is at 1. After the 1-st second, the policeman is at 1 and the thief is at 0. After the next second, the policeman is again at 0 and the thief at 1. They cannot end up at the same coordinate.
Problem G. Polo the Penguin and the XOR
Time limit 1000 ms
Code length Limit 50000 B
OS Linux
Read problems statements in Russian here
Polo, the Penguin, likes the XOR operation. Please read NOTE if you are not familiar with XOR operation.
XOR-sum of a list of numbers is the result of XOR-ing all of them. XOR-sum of (A[1] XOR A[2] XOR … XOR A[N]) is defined as A[1] XOR (A[2] XOR (A[3] XOR ( … XOR A[N]))).
He has an array A consisting of N integers. Index in the array are numbered from 1 to N, inclusive. Let us denote by F(L, R), the XOR-sum of all integers in the array A whose indices lie from L to R, inclusive, i.e. F(L, R) = A[L] XOR A[L+1] XOR … XOR A[R]. Your task is to find the total sum of XOR-sums F(L, R) over all L and R such that 1 ≤ L ≤ R ≤ N.
Input
The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows. The first line of each test case contains a single integer N denoting the size of A. The second line contains N space-separated integers A[1], A[2], …, A[N].
Output
For each test case, output a single line containing the total sum to the corresponding test case.
Constraints
1 ≤ T ≤ 100,000
1 ≤ N ≤ 100,000
0 ≤ A[i] ≤ 1,000,000,000 (10^9)
The total sum of all N over all test cases will not exceed 100,000.
Example
Input:
1
2
1 2
Output:
6
Explanation
Example case 1. F(1, 1) = A[1] = 1, F(2, 2) = A[2] = 2 and F(1, 2) = A[1] XOR A[2] = 1 XOR 2 = 3. Hence the answer is 1 + 2 + 3 = 6.
NOTE
XOR operation is a bitwise “Exclusive OR” operation performed on two integers in binary representation. First, the shorter number is prepended with leading zeroes until the numbers have equal size in binary. Then the resulting number (also in binary) contains 0 in all positions where the corresponding bits coincide, and 1 on the rest of the positions.
For example, 3 XOR 5 = 0112 XOR 1012 = 1102 = 6.
Problem H. Popatlal ki shaadi
Time limit 1000 ms
Mem limit 1572864 kB
Code length Limit 50000 B
OS Linux
Popatlal from Gokuldham Society is still not married. He approaches a marriage bureau and ask them to hurry the process. The bureau checks the list of eligible girls (n) and hands it over to Popatlal. Popatlal being conscious about his marriage, determined to find a girl with maximum connections so that he can gather more information about her.
Accordingly, he looks to figure out the maximum number of girls (from list) who know each other to achieve above purpose. In order to finalise the girl, he needs to find the Kth prime. Where k = largest group of girls who know each other.
Considering Popat’s poor knowledge in Maths, he seeks for Jethalal’s help for the answer. Now you, being fan of Jethalal, take this prestigious opportunity to solve Popat’s marriage issue.
In case number of connections are zero, print “-1”.
Note: Suppose girl “a” knows girl “b” and girl “b” knows girl “c”, then girl “a” also knows girl “c” – transitivity holds.
Consider 1 to be a composite number.
Input
First line of the input contains t, the number of test cases.
Each line of the test case contains a number n specifying the number of girls and m specifying number of connections.
Each ‘m’ lines contain u and v denoting that girl u and v know each other.
Output
Each new line of the output contains Kth prime number, or -1 if there are no connections.
Constraints
1 <= t <= 100
1 <= n <= 100000
0 <= m <= n
1 <= u, v <= n
Example
Input:
1
10 6
1 2
2 3
3 4
4 5
6 7
9 10
Output:
11
Contributed by: Paras Jain
Problem I. Company Layoffs

Time limit 1000 ms Mem limit 262144 kB
OS Windows
The tech company, Weta, has announced that it will continue to make layo s once a week for the next M weeks.
For the layo s, Weta has established that it will fire all employees who have a score greater than Qi. Qi is di erent every week, and obviously the current week score must be lower than the previous one.
Fortunately, the employees know about this in advance. That is why everyone who would be a ected by the week’s layo must make their score equal to Qi.
Weta will not notice this, since Weta does not care about the number of employees fired, but the sum of the employees score.
You, as the representative of the employees, must give Weta the sum of the scores once they have all adjusted their scores to avoid being fired.
Note that only employees with a score greater than Qi can change their score.
Input
The first line of input contains two integer N, M (1 ≤ M < N ≤ 105), the number of employees in Weta and the number of layo s.
The next line contains N integers Si (1 ≤ Si ≤ 109)
The following M lines describe the layo s. The i-th of them contains Qi, the score for the layo of the i − th week. (1 ≤ Qi ≤ 109)
Output
Print M lines with the sum of employees’ scores.
Sample 1

Input Output
5 3
2 3 5 5 10
8
7
1 23
22
5