| # | Problem | Pass Rate (passed user / total user) |
|---|---|---|
| 4013 | Lattice Squares |
|
| 4014 | Trip Compulsion |
|
| 4015 | Visible Lattice |
|
| 4016 | XOR Sum |
|
| 4017 | Find The Number |
|
| 4018 | Love for Pizza |
|
Description
Count the number of distinct squares you can draw using only integer co-ordinates for its 4 corners with the following restrictions.
- The edges should be parallel to the x and y axes
- The x and y co-ordinate of each corner should be within the range 0 to 2*n (range includes 0 and 2*n).
- None of the corners should lie in the central 2*k by 2*k square. It means both x and y co-ordinates of the corners should not lie in the range (n-k) to (n+k) (range inclusive of both ends) at the same time.
Two squares are distinct if and only if at least one of its corners is different.
Note that the edges can go through the central forbidden square. The only condition is that the corners itself should not lie in the central forbidden square.
The above figure shows the case n = 2 and k = 1. In the figure the central 2 x 2 square is forbidden and the forbidden lattice points are marked with red. When drawing a square you cannot use these points (marked red) for any of the corners. You are allowed to use only the points marked with black. So the only allowed square you can draw is the 4 x 4 square. Hence the answer for this case is 1.
Input
The first line contains one integer t, the number of testcases. (1 <= t <= 50)
This will be followed by t test cases. Each case is specified in a separate line containing two space separated integers n and k.
Constraints:
- The numbers n and k will be between 1 and 500.
- k will be strictly less than n (k
Output
For each testcase print the number of distinct squares you can draw under the given constraints.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Being a very quirky person, you've modeled your large neighbourhood as a set of numbered junctions and two-way roads connecting these junctions. Somewhat disturbingly, you've actually measured the length of each road in nanometers! Whenever you take a trip from one junction to another, you always note down the lengths of the longest road and the shortest road in your trip and then compute the difference between the two. One day, before you set out on a trip, you're overwhelmed by a strong desire to find out what the lowest possible difference is among all trips that have the same starting and ending junction as yours. Of course, computing all this on paper will take you ages and your trip is a little urgent (you must leave in the next 5 hours), so you decide to write a program.
Input
The first line contains T, the number of test cases. The first line of each test case contains two space separated numbers - N (the number of junctions) and R (the number of roads). The second line of each test case contains the two space separated numbers - start (the starting junction of your trip) and end (the ending junction of your trip). Each of the next R lines contains three space separated numbers - from (the starting junction of a road), to (the ending junction of a road) and length (the length of the two-way road connecting from and to).
Constraints:
1 <= T <= 10
2 <= N <= 2000
0 <= R <= 3000
0 <= start, end, from, to < N
1 <= length <= 2,000,000,000
start and end will be different.
Output
For each test case, output a single line containing one integer - the lowest possible difference. If no trip is possible between start and end, output a single line saying "NO PATH" (quotes for clarity).
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Consider a N*N*N lattice. One corner is at (0,0,0) and the opposite one is at (N,N,N). How many lattice points are visible from corner at (0,0,0)? A point X is visible from point Y iff no other lattice point lies on the segment joining X and Y.
Input
The first line contains the number of test cases T. The next T lines contain an interger N.
Constraints :
T <= 100 1 <= N <= 100
Output
Output T lines, one corresponding to each test case.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Given an array of N numbers, we wish to choose a contiguous sub-sequence of the array, so that the bitwise XOR of all chosen numbers is maximum. Bitwise XOR is defined as follows: every bit in the answer is obtained by applying XOR logic on the corresponding bits of the set of numbers. For example 7, 8 and 5 are XORed as follows,
Numbers in binary: 0111 1000 0101 ----- 1010
So the answer is 10 (in decimal). The same answer can be obtained in C/C++/Java by using the XOR operator as 7^8^5.
Input
The first line contains the number of test cases T. The first line of each test-case contains one integer, N (size of the array). The next N lines of each test-case contain integers denoting the elements of the array.
Constraints:
1 <= T <= 10
1 <= N <= 100,000
All input integers will be non-negative and fit into 32 bit signed integer.
Output
For each test case, output a single line containing the maximum sum that can be obtained.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
ABC University has k departments. Each department is assigned a department number. There are many students in each department. The university assigns roll numbers to each student such that the number is divisible by the department number. For example if department number is 5, the students can only get roll numbers 5, 10, 15, etc. The purpose is to identify the department of a student easily from his roll number. So if a number is divisible by more than one department number, then that number will not be assigned to any student (so that there will not be any ambiguity). For example if we have departments 5 and 7, then 35, 70, 105, etc are not used because they are divisible by both numbers. Everything was going fine until one day, someone hacked into the University database and erased the roll number column in the students table! The Database administrator knows that,
- All valid roll numbers (the valid roll numbers are numbers divisible by one and only one department number) less than 1015 were there in the Database.
- All the records were sorted by roll number before the hacker erased them, and the hacking did not change the order of records
Now given the position (1 based index) of the record in the database, can you find out the roll number corresponding to that record quickly?
Input
The first line contains one integer t, the number of testcases (1 <= t <= 50).
This will be followed by 't' test cases, each containing 2 lines.
- The first line of each test case gives two numbers k and n separated by space.
- The second line contains k space separated integers specifying the department numbers of each department.
Constraints:
- 1<=k<=12
- The department numbers will be between 2 and 10^5 (range inclusive of both ends).
- n will fit into a 32 bit signed integer.
- The input will be such that, the answer will always be less than 1015.
- There will not be two departments with same number.
- One department number will not be divisible by another.
Output
For each test case print the roll number corresponding to the nth record in the database. Output of each test-case should be on a separate line.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
My brother and I love pizza. My brother ordered a pizza today with a number of toppings. Some of those toppings I love, like mushrooms, while there are some others that I hate, like olives. Even among the toppings I like (or the ones that I don't like), I like some more than the other, depending on the amount.
Now my brother will let me take a wedge of any size from the pizza. This means I am allowed to make two cuts from the center of the pizza to its circumference, and can keep one of the two resulting pieces. If either cut goes through a topping, the entire topping belongs to that piece which contains the centre of the topping. I am not allowed to cut exactly through the centre of a topping. Each topping will thus remain entirely on one of the pieces. I would like to cut and choose the best piece possible for myself.
Input
Input contains multiple test-cases. The first line of the input contains T, the number of test cases, followed by T testcases. The first line of each test case contains one integer N, the number of toppings. It is followed by N lines containing three space-separated integers each. Each line described a single topping. The first integer denotes my preference for the topping. The next two integers denote respectively the x and y co-ordinates of the centre of the topping.
Input Constraints:
1 ≤ T ≤ 25
1 ≤ N ≤ 105
-105 ≤ preference ≤ 105
The point (x,y) will lie within the pizza, which is assumed to be a circle centered at (0, 0) with a radius of 109.
The point will not be the centre itself.
Multiple toppings may be centred at the same point.
A set of test cases will not exceed 4MB in file size.
Output
Output a single line per test-case, indicating the sum of the preferences of all the toppings on the best piece. The best piece is the one that has the maximum sum possible.