Majority element problem: – Here we need to find the element from the array of size with occurence>n/2.
1.The algorithm is simple to learn
2.Its complexity is O(n)
Read
Majority Element Problem April 16, 2010
TJU 1138. Binomial Showdown January 26, 2010
TJU 1138. Binomial Showdown
--AC–
#include<iostream>
#include<stdlib.h>
using namespace std;
class A{
long long int i,j,k,N,K,tmp;
public:
void input(){
cin>>N>>K;
if(N==0&&K==0) exit(0);
}
void calc(){
i=N-K;
if(N==K||K==0) {tmp=1;}
else if(K==1){tmp=N;}
else if(i>K)
{
j=1;
tmp=1;
while(j<=K)
{
if(N%j==0)
tmp=tmp*(N/j);
else if(tmp%j==0)
tmp=N*(tmp/j);
else tmp=(N*tmp)/j;
j++;
N--;
}
}
else if(i<=K)
{
j=1;
tmp=1;
while(j<=i)
{
if(N%j==0)
tmp=tmp*(N/j);
else if(tmp%j==0)
tmp=N*(tmp/j);
else tmp=(N*tmp)/j;
j++;
N--;
}
}
}
void output(){
cout<<tmp<<endl;
}
};
int main()
{
A a;
while(1){
a.input();
a.calc();
a.output();
}
return 0;
}
RAM model of computation January 26, 2010
RAM (here Random Access Machine) model of compuation is an abstract model in which we try to analyze the working of our ALGORITHMS . Thought this model is different from real computers, it is helpful in many way.
SPOJ 1025. Fashion Shows December 8, 2009
SPOJ 1025. Fashion Shows
Problem code: FASHION
–AC–
sorting based problem(qsort implemnted)
TJU 3288. Stockholm Numbers December 8, 2009
TJU 3288. Stockholm Numbers
original thinking implemented
1->1*2+1=3 //1 has odd parity
2->2*2+1=5//2has odd parity
3->3*2=6//3has even parity
4->4*2+1=9//4has odd parity
5->5*2=10//5has even parity
and so on
……………….
--AC--
#include<stdio.h>
int main()
{
long long int i,j,k,K,tmp,rem,cases;
scanf("%lld",&cases);
while(cases--)
{
scanf("%lld",&K);
j=0;
tmp=K;
while(K>0)
{
rem=K%2;
if(rem==1)
++j;
K=K/2;
}
if(j%2==0)
printf("%lld\n",2*tmp);
else
printf("%lld\n",2*tmp+1);
}
return 0;
}
TJU 2218. Super Square December 7, 2009
TJU 2218. Super Square
EXPMOD implemented
--AC--
//expmod based program (m^m)%n
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
long long int expmod(long long int n, long long int p,long long int m) {
if (p == 0) return 1;
int nm = n % m;
long long int r = expmod(nm, p / 2, m);
r = (r * r) % m;
if (p % 2 == 0) return r;
return (r * nm) % m;
}
int main()
{
long long int i,j,k,N,n,r,sum,a,b,x,y,acc,m=2006;
while(1)
{
scanf("%lld",&n);
if(n==0) break;
r = 0;
r = (r + expmod(n, n, m)) % m;
printf("%lld\n",r);
}
return 0;
}
TJU 2843. Diamonds November 27, 2009
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
int main()
{
int t,n,i,j,k,l,big,max;
int a[10002][4];
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
for(i=1;i<=n;i++)
for(j=1;j<=3;j++)
scanf("%d",&a[i][j]);
max=0;
for(i=2;i<=n;i++)
{
for(j=1;j<=3;j++)
{
if(j==1) {k=2;l=3;}
else if(j==2){k=1;l=3;}
else if(j==3){k=1;l=2;}
if(a[i-1][k]>a[i-1][l])
big=a[i-1][k];
else
big=a[i-1][l];
a[i][j]=a[i][j]+big;
if(a[i][j]>max)
max=a[i][j];
}
}
printf("%d\n",max);
}
return 0;
}
TJU 2862. CityStar November 25, 2009
[ took 45-55 mins to code, also implemented qsort function to get AC,
other it was in TLE]
<strong>--AC--</strong>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
int compare (int *a, int *b)
{
int *da = (int *) a;
int *db = (int *) b;
return (*da > *db) - (*da < *db);
}
int main()
{
int i,j,k;
int n,a[100002],cases,cs=0;
int min,diff,tmp,index;
scanf("%d",&cases);
while(cases--)
{
scanf("%d",&n);
for(i=1;i<=n;i++)
scanf("%d",&a[i]);
qsort (a+1, n, sizeof (int), compare);
min=99999999;
for(i=1;i<=n-4;i++)
{
diff=a[i+4]-a[i]+1;
if(diff<min)
{
min=diff;
index=i;
}
}
printf("Scenario #%d:\n",++cs);
printf("%d:",min);
for(j=1;j<=5;j++)
printf(" %d",a[index++]);
printf("\n\n");
}
return 0;
}
ACM-ICPC Japan Domestic 2006 October 2, 2009
1.Problem A – Dirichlet’s Theorem on Arithmetic Progressions
2.Problem B – Organize Your Train part II
3.Problem C – Hexerpents of Hexwamp
HeapSort(Array) September 2, 2009
// lab heap sort
#include<stdio.h>
void heapsort(int b[],int n);
void heap(int a[],int n);
int main()
{
int n,i,a[40];
printf("ENTER THE NO.OF ELEMENTS\n");
scanf("%d",&n);
printf("ENTER THE ELEMENTS\n");
for(i=0;i<n;i++)
scanf("%d",&a[i]);
heap(a,n);
return 0;
}
void heap(int a[],int n)
{
int b[40],i,temp,loc,par;
for(i=0;i<n;i++)
{
loc=i;
b[i]=a[i];
while(loc>0)
{
par=(loc-1)/2;
if(b[loc]>b[par])
{
temp=b[loc];
b[loc]=b[par];
b[par]=temp;
}
loc=par;
}
}
printf("HEAP IS \n");
for(i=0;i<n;i++)
printf("%d ",b[i]);
heapsort(b,n);
}
void heapsort(int b[],int n)
{
int l,temp,k,t,left,right,m,i;
l=n-1;
while(l>=0)
{
temp=b[l];
b[l]=b[0];
b[0]=temp;
k=0;
m=l-1;
while(m>=(2*k+1))
{
left=2*k+1;
right=2*k+2;
if(right<=m)
{
if(b[left]>=b[right])
t=left;
else
t=right;
}
else
t=left;
if(b[t]<b[k])
break;
else
{
temp=b[t];
b[t]=b[k];
b[k]=temp;
}
k=t;
}
l--;
}
printf("\nSORTED ARRAY \n");
for(i=0;i<n;i++)
printf("%d ",b[i]);
}
Recent Comments