Given N stacks, each stack contains Si elements, find the maximum sum of the M numbers in the N stacks. To get the number of the stack, only supporting get the top number. For example, S=[1,200,1,2,3], if you want to get the number 200, you need choose 3,2,1 first. EX: S1=[1,1,100,3] S2=[2000,2,3,1] S3=[10,1,4] the maximum sum of the 3 numbers in the above stacks is 3+100+4=107. Any better solution for this problem?

You are given an array A of length N. For any given integer X, you need to find an integer Z strictly greater than X such that Z is not present in the array A. You need to minimise the value of Z.

Input format :

First line : Two space seperated integers N and Q denoting the number of elements in array A and the number of queries respectively Second line : N space seperated integers denoting the array elements Next Q lines : Each line consists of an integer X Output fomat :

Print Q lines, each line denoting the answer to the corresponding query. Constraints :

Sample Input 5 2 2 7 5 9 15 3 9 Sample Output 4 10 Explanation For the first query, the minimum element greater than 3 and not present in the given array is 4. Similarly, for the second query, the answer is 10.

------------------------------------------------------------------------ for this problem i write this code

https://ideone.com/x5LZfC

can anyone tell me where it is failing thanx in advance

The Travelling Ant There is an Ant that lives in Baskerville and loves to travel. As Baskerville is a small place, it consists of only 5 cities placed one next to each other.

There is a train between each successive cities ie between City 1 — City 2, City 2 — City 3, ... City 5 — City 1. Note that our Ant loves to travel and gets happy after making exactly N train trips and returning back to home. Ant lives in the city 1 from where she begins her journey. She asks you to find the number of ways she can make N train trips and come back to home.

Since the number of ways can be huge, print that number modulo 10^9 + 7.

Input First line contains T, the number of test cases. Then T lines follow. Each line contains a single integer n, representing the number of train trips the ant needs to make.

Output For each test case, print a single line containing the answer to the problem.

Constraints 1 <= T <= 1000 0 <= n <= 10^18

Sample Input 3 0 3 4 Sample Output 1 0 6 Explanation In first case, ant has to make 0 trips. So the ant stays at city 1 and has only 1 option. In second case, ant has to make 3 trips. No matter what combination we try, we can never reach back to city 1 back after 3 trips. So answer is 0. In third case, ant makes 4 trips. There are 6 ways in which it can reach back to city 1. Way 1: 1-->2-->1-->2-->1 Way 2: 1-->2-->3-->2-->1 Way 3: 1-->5-->1-->5-->1 Way 4: 1-->5-->4-->5-->1 Way 5: 1-->5-->1-->2-->1 Way 6: 1-->2-->1-->5-->1

how can i solve this

for this problem i write this code can anyone tell me where this one is wrong problem: https://www.codechef.com/JAN17/problems/DIGITSEP solution: http://ideone.com/j5o0Iz

can someone tell me how we can find longest palindrom substring in O(nlogn) complexity using hashing thanx in advance.........

problem //////////////////////////////////////////////////// Expected Xor

Given a random variable X , and another integer N, this random variable X can take any value between 1 and N

with equal probability.

Now, we define a function F(X)

:

F(X)

The bitwise exclusive OR of all the digits of X. For example, for X=34536,F(X)=3⊕4⊕5⊕3⊕6=7

.

Considering X can take any value between 1 and N with equal probability, you are to find expected value of F(X)

. Can you do it ?

The answer equals to P/Q where P/Q is an irreducible fraction, i.e, P and Q

are co-prime to each other.

You can read more about expected value of a random variable here.

Input:

The first line of the input contains T

, denoting the number of test cases.

The next T lines contain a single positive integer N

.

Output:

For each test-case, print the answer in a separate line in the form of P/Q where P/Q is an irreducible fraction i.e. P and Q

are co-prime to each other.

Constraints:

1≤T≤105

1≤N≤1018

Sample Input (Plaintext Link)

4 1 3 5 10

Sample Output (Plaintext Link)

1/1 2/1 3/1 23/5

Explanation

For N=1 , there is only one possible value X can take which is 1. Hence expected value of X=1

.

For N=3 , there are three possible values of X ,i.e, 1,2 and 3. Hence, expected value of X=1/3∗1+1/3∗2+1/3∗3=2

.

For N=10 , X can take all the values from 1 to 9 where X will be equal to 1 for both 1 and 10. Hence, X=2/10∗1+1/10∗(2+3+4+5+6+7+8+9)=23/5

. my code

http://ideone.com/SRbjnv

please anyone great guy tell me where this code is going on wrong thanx in advance And explain how I can solve this

i m tring to solve this question this gives me correct o/p but in 10th case it gives me wrong where i m wrong http://www.spoj.com/problems/AE2A/ https://ideone.com/0fOUqn SPOJ.com — Problem AE2A ... spoj.com

can anyone tell me why my code gives tle and hows i can remove this i apply mo algo correctly for this than why this gives me tle http://codeforces.net/contest/703/submission/19736475 thanx in advance

for this problem You will get 2 points for solving this problem.

You are given a rooted tree. The tree is not necessarily binary. The tree contains N nodes, labeled 1 to N. You are given the tree in the form of an array P[1..N] of size N. P[i] denotes label of the parent of node labeled i. For clarity, you may assume that the tree satisfies the following conditions.

The root of the tree is labeled 1. Hence P[1] is set to 0. The parent of node T will always have a label less than T. Hence P[i] < i will always be true. All nodes contain a mutable value (or, more simply, a variable), which is initially set to 0. You are asked to perform several operations of the following type

ADD X Y: add Y to the value at node X.

ADDUP X Y: add Y to the value at node X. Then, add Y to the value at P[X] (i.e. the parent of X). The, add Y to the value at P[P[X]] (i.e. the parent of P[X]).. and so on, till you add Y to the value at root.

After you have performed all the given operations, you are asked to answer several queries of the following type

VAL X: print the value at node X.

VALTREE X: print the sum of values at all nodes in the subtree rooted at X (including X).

Input

The first line of input contains the number T, the number of test cases. Then follows the description of T test cases. The first line of each test case contains the numbers N, M and Q respectively (separated by single space character). N depicts the number of nodes. M depicts the number of operations you must perform. Q depicts the number of queries you must answer.

The next N lines contain a number each, depicting the array P[1..N]. Of course the number on the first such line is always 0.

The next M lines contain description of the respective operation. An operation will be either "ADD X Y" or "ADDUP X Y" (without the quotes). Please refer to the problem statement and sample I/O explanation for clarity on the meaning of the operations.

After the operations, the next Q lines contain description of the queries. A query will be either "VAL X" or "VALTREE X" (without the quotes). Please refer to the problem statement and sample I/O explanation for clarity on the meaning of the queries.

Output

Print the result of each query on a line by itself. Since the answer for some queries may be too large, please print the result modulo 1,000,000,007. Do not print any blank lines between test cases.

Constraints

1 ≤ T ≤ 10 1 ≤ N ≤ 50000 1 ≤ M ≤ 50000 1 ≤ Q ≤ 50000 1 ≤ X ≤ N 1 ≤ Y ≤ 50000

The input file will be smaller than 2 MB. Sample Input

2 5 5 3 0 1 1 1 3 ADD 1 10 ADD 2 20 ADD 3 30 ADD 4 40 ADDUP 5 50 VAL 3 VALTREE 3 VALTREE 1 7 4 5 0 1 2 2 2 1 2 ADD 6 76 ADDUP 1 49 ADD 4 48 ADDUP 2 59 VALTREE 1 VALTREE 5 VAL 5 VALTREE 2 VAL 2

Sample Output

80 130 250 291 0 0 107 59

i write this code https://ideone.com/H0fZZR

but this gives me WA plz help me that where i was wrong plz ............... thanx in advance

http://codeforces.net/contest/580/submission/18724460

this is my submission i am unable to memoize this because each mask value is different so plz help me that how i memoize this and plz tell me some memoization tricks thanks in advance.....