knowledgediarybd.com

Your Virtual Knowledge Campus

Introduction & Ad Hoc Problems Solution

Introduction & Ad Hoc Problems Solution

Ad hoc problems Solution are those kinds of problem which cannot be solved by trivial algorithm. Every ad hoc problem is unique, different from other problems and there is no general solution for them.

A programmer uses his skills, previous knowledge to solve this kind of problem. To solve an ad hoc problem someone should think in different ways. So a programmer has to build new data structure, loops and his own algorithm.

Ad hoc problems should be read carefully to identify its input, output and special test case. Also time and space complexity should be maintained carefully.

In programming contest and programming judging site, actually most ad hoc problems are easy and can be solved by previous knowledge.  But be careful about time, space and special criteria when solving them.

Some UVa Ad hoc problems  Solution are given below:

UVa: 278( Chess)

#include<stdio.h>
#define MAX(a,b) (a>b?a:b)
#define MIN(a,b) (a>b?b:a)

int M, N;
char P[5];

void Rock() {
printf("%d\n",MIN(M,N));
}
void Knight() {
int d, x;
d = M*N;
x = d/2;
if(d%2) x += 1;
printf("%d\n",x);
}
void Queen() {
printf("%d\n",MIN(M,N));
}
void King() {
int max, d, k, x;
d = MAX(M,N);
k = MIN(M,N);
x = (d / 2);
if( d % 2) x += 1;
k -= k / 2;
max = k * x;
printf("%d\n",max);
}

void main() {

int kase;
scanf("%d",&kase);
while(kase--) {
scanf("%s%d%d",P,&M,&N);
switch(P[0]) {
case 'r':Rock(); break;
case 'k':Knight(); break;
case 'K':King(); break;
case 'Q':Queen(); break;
}
}
}

UVa: 579(ClockHands)

#include<stdio.h>
#include<math.h>

float h,m;
main()
{
float th;
float dh,dm,p_angle,d_angle;
int k,i;
k=0;

while(1)
{
scanf("%f:%f",&h,&m);
if(h==0)
if(m==0) break;
th=fmod(h,12)*5;
dh=th*6;
dm=m*6;
d_angle=(m/12)*6;
dh=dh+d_angle;

if(dh>=dm)
{
p_angle=dh-dm;
if(p_angle>180)
printf("%.3lf\n",360-p_angle);
else
printf("%.3lf\n",p_angle);
}
else
{
p_angle=dm-dh;
if(p_angle>180) printf("%.3lf\n",360-p_angle);
else printf("%.3lf\n",p_angle);
}
}
return 0;
}

UVa: 10420(List of Conquests)

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
char name[2009][80];
int n;

sort_function(const void *a,const void *s)
{
return ( strcmp( (char *)a, (char *)s ) );
}

count() {

int i,c;
char inter[80];
qsort((void *)name,n,sizeof(name[0]),sort_function);
for(i = 0; i<n; ) {
c = 1;
strcpy(inter,name[i]);
for(i ++; !strcmp(inter,name[i]) && i<n; i ++) c ++;
printf("%s %d\n",inter,c);
}

return 0;
}

void main(void ) {

char mid[100];
int i;
scanf("%d",&n);
for(i = 0; i<n; i ++){
scanf("%s",name[i]);
gets(mid);
}
count();
}

UVa: 10812( Beat the Spread!)

#include<stdio.h>

typedef int ss;

void Cal(ss n, ss m, ss sum) {
if(n <= m) {
printf("impossible\n");
return;
}
if(sum % 2) {
printf("impossible\n");
return;
}
printf("%d %d\n",sum/2, n - sum/2);
}

void main() {
ss n, m, k;
scanf("%d",&k);
while(k--) {
scanf("%d%d",&n,&m);
if(!n && !m) {
printf("0 0\n");
continue;
}
Cal(n,m,n+m);
}
}

Essential Ad hoc problem link

1. UVa online judge

2. Light OJ

Related Post or You may felt Interest:

  1. Introduction of acm ICPC & UVa Online Judge
  2. Programming Sites & Resources
  3. Data Structures & Libraries problem Solution
  4. UVa Mathematics Problem Solution
  5. String Processing Problem Solution
  6. Computational Geometry Problem Solution
  7. Graphs Problem Solution
  8. Other Problem Solution
knowledgediarybd.com © 2017
shares