Greedy Manager

PKJ

 Practice Questions 

 Greedy Manager 

 Problem Statement 

You are a resource manager and you need to manage gold, you already have enough to fulfill everyone's need. There is a line of people who either give gold to you represented by positive value or take gold from you represented by a negative values.

You are greedy so you decided to get maximum profit so you decided to skip people but as you are under surveillance once you start accepting the person request you can only stop once and you need to take at least one person. You already have a list of people and their requests, so you can decide beforehand.

 Boundary Condition(s) 

1 <= t <= 10⁵
1 <= n <= 10⁵
-10⁴ <= a[i] <= 10⁴

 Input Format 

First line represents the number of test cases.
Second line represents the number of people.
Third line represents the input array.

 Output Format 

Number of extra gold, -ve if you give the gold.

 Example Input/Output 1 

 Input 

1
7
-2 -3 4 -1 2 -1 -1

 Output 

5

 Explanation 

You decided to skip the first two and then take 4 gold from the 3rd person, give 1 gold to the 4th person and again take 2 gold from the 5th person and then stop. In the end, you have 5 extra gold.

Solution for Greedy Manager

Comments

Post a Comment

Popular Posts

Count Number of Occurrences of a Character

PKJ
 Count Number of Occurrences of a Character   Problem Statement:  The program must accept a string S and a character CH as the input. The program must print the number of occurrences of CH in the string S as the output.  Boundary Condition(S):  1 <= Length of S <=1000  Input Format:  The first line contains the string S. The second line contains the character CH.  Output Format:  The first line contains the number of occurrences of CH in the string S.  Example Input/Output 1:   Input:  pineapple p  Output:  3  Explanation:  The character p has occurred three times in the string " p inea pp le". So 3 is printed as the output.  Example Input/Output 2:   Input:  Encyclopedia e  Output:  1 Explanation: The character e has occurred only once in the string "Encyclop e dia". So 1 is printed as the output. Example Input/Output 3: Input: KEYBOARD y Output: 0  Note: M...
Click to Continue...

Print Prime Numbers from 2 to N

PKJ
 Coding Problem Keys   Print Prime Numbers from 2 to N   Problem Statement  The program accepts an integers N as the input. The program must print all the prime numbers from 2 to N (inclusive of N) as the output.  Input Format  The first line contains the value of N.  Output Format  The first line contains all the prime numbers from 2 to N.  Boundary Condition(s)  2 <= N <= 999999  Example Input/Output 1   Input  11   Output  2 3 5 7 11  Example Input/Output 2   Input  120  Output  2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113  Max Execution Time Limit: 3000 millisecs   Solution   Programming Language: Python 3 Language  n= int ( input ()) l=[ True for i in range (n+ 1 )] j= 2 while (j*j<=n): if l[j]== True : for i in range (j*j,n+ 1 ,j):l[i]= False j+= 1 ...
Click to Continue...

Cities and Population

PKJ
 Coding Problem Keys   Cities & Population   Problem Statement  The program must accept the name and population of N cities as the input. The program must print the total population in the given N cities as the output. Then the program must print the name and population of each city separated by a colon as the output.   Example Input/Output 1   Input  3 KKTCity 19000 URCity 81000 MCCity 21000  Output  121000 KKTCity:19000 URCity:81000 MCCity:21000  Explanation  Here N = 3 and the total population in the given 3 cities is 121000. Hence the output is 121000 KKTCity:19000 URCity:81000 MCCity:21000  Example Inpu...
Click to Continue...

K Palindrome Integers

PKJ
 Coding Problem Keys   K Palindrome Integers   Problem Statement  The program accepts two integers  N  and  K  as the input. The program must print the first K palindrome integers greater than N as the output.  Input Format  The first line contains the value of N and K separated by a space.  Output Format  The first line contains K integers representing the first K palindrome integers greater than N.  Boundary Condition(s)  1 <= N <= 10 ⁷ 1 <= K <= 1000  Example Input/Output 1   Input  1221 5   Output  1331 1441 1551 1661 1771   Explanation  Here N = 1221 and K = 5. The first 5 palindrome integers greater than 1221 are 1331, 1441, 1551, 1661 and 1771 . Hence the output is 1331 1441 1551 1661 1771  Example Input/Output 2   Input  658100 10  Output  658856 659956 660066 661166 662266 663366 664466 665566 666666 667766  Max E...
Click to Continue...

Most Vowels in Row

PKJ
 Most Vowels in Row   Problem Statement:  The program must accept a character matrix of size NxN as the input. The program must print the row which contains most number of vowels in it. If more than one row has same number of most number vowels then print the last occurring row. Boundary Condition(s): 1 <= N <= 50 Input Format: The first line contain N. The next N lines contain N characters each separated by a space. Output Format:  The first line contains  C characters.  Example Input/Output 1:   Input:  5 G w w t e H d E o P Z D H e W Z l H e A H o O D e  Output:  H o O D e Explanation: The last two rows have 3 vowels. So the last occurring row with most number of vowels is the last row. Example Input/Output 2: Input: 4 w y o o g g t t t o e t a q r q Output: t o e t  Note: Max Execution Time Limit: 4000 millisecs  Solution:   Programming Language: C Language  #include <stdio.h> #include ...
Click to Continue...

Sum - Odd Number of Digits

PKJ
 Coding Problem Keys   Sum - Odd Number of Digits   Problem Statement  The program must accept N integers as the input. The program must print the sum of integers having odd number of digits in the given N integers. If there is no such integer, the program must print -1 as the output.  Boundary Condition(S)  1 <= N <= 100 1 <= Each integer value <= 10 ⁹  Input Format  The first line contains N. The second line contains N integers separated by a space.  Output Format  The first line contains the sum of integers having odd number of digits in the given N integers or -1.  Example Input/Output 1   Input  5 12 488 1 78 200  Output  689  Explanation  The integers with odd number of digits are 488 , 1 and 200 . So their sum is 689 (488 + 1 + 200).  Example Input/Output 2   Input  4 98 45 5000 11  Output  -1  Note: Max Execution Time Limit: 500 m...
Click to Continue...

Sum of Numbers - XOR and OR

PKJ
 Coding Problem Keys   Sum of Numbers - XOR and OR   Problem Statement  In the faculty of Informatics Engineering, the Teacher of Mathematics gave a lecture on bits and explained XOR and OR. Then he decided to test the competence of his students by giving them this question. He will give the students an array A of N numbers and then give them Q queries. Each query will consist of three numbers Type ᵢ , L ᵢ  and R ᵢ . Each of the queries can be one of the following types.     - If Type ᵢ is 1, then the student has to replace each A ᵢ with (A ᵢ | (A ᵢ - 1)) for every i between L ᵢ and R ᵢ.     - If Type ᵢ is 2, this means that the student must replace each A ᵢ with (A ᵢ ^ (A ᵢ - 1)) for each i between the L ᵢ and R ᵢ. After each query, the professor asks his students to calculate the sum of the numbers from array A. You need to find the sum of the answers to all the queries modulo 10^9+7. Note The sign | represents the logical OR....
Click to Continue...