Latest Updates ☛
- Graphs: Introduction of graphs and types of graphs
- SPOJ : Geeky solves geeky solution
- Solution Code : Pass the time problem on SPOJ.
- Find the minimum shortest path solution in c language ! !
- Code
Author
Welcome !
Heya ! Firstly thanks for giving look to this website .Here you can find all the stuff related to programming plus its solutions means a pack for learners and coders.
So keep visiting and enjoy learning and browsing this Code Author ! !
About Me
- Java Programs
- C++
C++ Programs List
- Books
- C & Data Structures
Data Structures
Reference Book
This is a basic book for a starter to learn data structures in c programming language.Filled with total explanation of all programs working and many more.Read more...
- Privacy Policy
- Others
Saturday, September 7, 2013
Geeky person Ross does geeky things himself solution...
Question :
SRoss is a geek but he never admits it. He plays weird geeky games and enjoys them a lot. Recently he started playing a new game. He takes an array of "N" integers. Then he makes another array out of it which contains the sum of all the contiguous sub arrays of the original array. He sorts them is non-increasing order and keeps them in an array S that has 1-based index. Now he wants the find the elements at position K1, K2 and K3 in it.
For ex. if the array has 3 elements {10, 20, 30}, then the formed array will have 6 elements as S[1..6] = { 60, 50, 30, 30, 20, 10 }
SRoss is a geek but he never admits it. He plays weird geeky games and enjoys them a lot. Recently he started playing a new game. He takes an array of "N" integers. Then he makes another array out of it which contains the sum of all the contiguous sub arrays of the original array. He sorts them is non-increasing order and keeps them in an array S that has 1-based index. Now he wants the find the elements at position K1, K2 and K3 in it.
For ex. if the array has 3 elements {10, 20, 30}, then the formed array will have 6 elements as S[1..6] = { 60, 50, 30, 30, 20, 10 }
Inputs :
First line of the input will contain 4 integers "N", "K1", "K2" and "K3". The next line will contain "N" integers A[0], A[1] .. A[N-1].
First line of the input will contain 4 integers "N", "K1", "K2" and "K3". The next line will contain "N" integers A[0], A[1] .. A[N-1].
Outputs :
Output three integers, the elements at position K1, K2 and K3 in the formed array separated by a single space.
Output three integers, the elements at position K1, K2 and K3 in the formed array separated by a single space.
Constraints :
2 <= N <= 10^4, 1 <= K1 <= K2 <= K3 <= 2000, K3 <= N*(N+1)/2, -10^4 <= A[i] <= 10^4
2 <= N <= 10^4, 1 <= K1 <= K2 <= K3 <= 2000, K3 <= N*(N+1)/2, -10^4 <= A[i] <= 10^4
Level :Thinker,admirer
Solution to the Problem :
#include<stdio.h>
#include<limits.h>
#define MAX 4100
#define MAX_TOTAL 10300
class minheap{
public:
minheap()
{
last=1;
a[0]=INT_MIN;
}
void insert(int n)
{
a[last++]=n;
cascadeup(last-1);
}
int top()
{
return a[1];
}
int extractmin()
{
int ans=a[1];
if(size()){
a[1]=a[last-1];
last--;
cascadedown(1);
return ans;
}
else return INT_MIN;
}
int cascadedown(int pos)
{
int key=a[pos];
int child=pos<<1;
while((child<last)){
if(child+1<last)
if(a[child]>a[child+1])
child++;
if(a[child]>key)
break;
else{
a[pos]=a[child];
pos=child;
child<<=1;
}
}
a[pos]=key;
return pos;
}
int cascadeup(int pos)
{
int key=a[pos];
while((pos!=1)&&(key<a[pos/2])){
a[pos]=a[pos/2];
pos>>=1;
}
a[pos]=key;
return pos;
}
int size(){return last-1;}
private:
int last;
int a[MAX+1];
};
int main()
{
int cases,i,n,j,sum;
int k1,k2,k3,heapsize;
int prefix[MAX_TOTAL];
int a[MAX_TOTAL];
int maxsum[MAX];
minheap heap;
scanf("%d",&n);
scanf("%d%d%d",&k1,&k2,&k3);
for(i=1;i<=n;++i)
scanf("%d",&a[i]);
prefix[0]=0;
for(i=1;i<=n;++i) prefix[i]=prefix[i-1]+a[i];
for(heapsize=0,i=0;i<=n;++i)
for(j=i+1;j<=n;++j){
sum=prefix[j]-prefix[i];
if(heapsize<k3){
heap.insert(sum);
heapsize++;
}
else if(sum>heap .top()){
heap. extractmin();
heap .insert(sum);
}
}
for(i=k3;i;--i)
maxsum[i]=heap. extractmin();
printf("%d ",maxsum[k1]);
printf("%d ",maxsum[k2]);
printf("%d\n",maxsum[k3]);
while(1)
{}
}
