Page Contents
Pushpa PUSH7PA Solution Codechef
Pushpa has entered Chefland and wants to establish Pushpa-Raj here too.
Chefland has N towers where the height of the ith tower is Hi. To establish Pushpa-Raj, Pushpa does the following:
Initially, Pushpa chooses any tower i (1≤i≤N) and lands on the roof of that tower.
Let X denote the height of the tower Pushpa is currently on, then, Pushpa can land on the roof of any tower j (1≤j≤N) such that the height of the jth tower is (X+1).
Let i denote the index of the tower on which Pushpa lands, then, the height of all towers except tower i increases by 1 after each jump including the initial jump.
To establish Pushpa-Raj, Pushpa wants to land at the maximum height possible. Determine the maximum height Pushpa can reach.
Input Format
The first line contains a single integer T – the number of test cases. Then the test cases follow.
The first line of each test case contains an integer N – the number of towers
The second line of each test case contains N space-separated integers H1,H2,…,HN denoting the initial heights of each of the towers from the ground.
Output Format
For each test case, output in a single line the maximum height achieved by Pushpa.
Constraints
1≤T≤10
1≤N≤105
1≤Hi≤109
Sample Input 1
2
4
1 2 1 3
1
2
Sample Output 1
3
2
Explanation
Test case 1: If Pushpa chooses to start from tower at index 1 with height of 1 unit, then, the new heights will be [1,3,2,4]. He can then jump to the 3rd tower (with height 2 units). The updated heights of the towers is [2,4,2,5]. Pushpa is unable to make any more jumps.
The optimal way to in this case is to take an initial jump at tower 4 with height 3. The maximum height Pushpa can reach is 3.
Test case 2: There is only 1 tower so Pushpa reaches the maximum height of 2 units.
SOLUTION
Program: Pushpa PUSH7PA Solution Codechef in Python
def mf(List): return max(set(List), key=List.count) t = int(input()) for i in range(0, t): n = int(input()) a = list(map(int, input().split())) x = mf(a) + a.count(mf(a))-1 y = max(a) + a.count(max(a)) - 1 if x > y: print(x) else: print(y)
Program: Pushpa PUSH7PA Solution Codechef in C++
#include <iostream> #include <cstdlib> #include <algorithm> using namespace std; int main() { int t; cin>>t; while(t--){ int n; cin>>n; int h[n]; for(int i=0;i<n;i++) cin>>h[i]; sort(h,h+n); int ans = h[n-1]; int y=0; for(int i=0;i<n-1;i++){ if(h[i]==h[i+1]){ y++; } if(h[i]!=h[i+1] or i==n-2){ ans = max(ans,h[i]+y); y=0; } } cout<<ans<<endl; } return 0; }
Program: Pushpa PUSH7PA Solution Codechef in Java
import java.util.*; import java.lang.*; import java.io.*; class Codechef { public static void main (String[] args) throws java.lang.Exception { Scanner sc=new Scanner(System.in); int t=sc.nextInt(); while(t-->0) { int n=sc.nextInt(); int arr[]=new int[n]; for(int i=0;i<n;i++) { arr[i]=sc.nextInt(); } Arrays.sort(arr); if(n==1) { System.out.println(arr[0]); } else { int max=0; int c=0; for (int i=n-1;i>=1;i--) { if(arr[i]==arr[i-1]) { c++; } else{ if(max<arr[i]+c) { max=arr[i]+c; } c=0; } } System.out.println(max); } } } }
Related:
- The Magical Stone Solution Codechef
- Alternating Diameter ALTDIA Solution Codechef
- Mystical Numbers XORGAND Solution Codechef
- The Attack of Queen Solution Codechef
- Sugarcane Juice Business Solution Codechef
- In The Green Zone ITGRZN Solution Codechef
- Four Arrays FOURARR Solution Codechef
- Miami GP F1RULE Solution Codechef
- Football Cup FOOTCUP Solution Codechef