CCHESS-COSTLY CHESS

COSTLY CHESS

Given below code is for cchess spoj or costly chess spoj.

In this question I apply Floyd Warshall's algorithm to find the minimum cost between all pair of blocks of chess, and then for given input I just print out that value from table.

#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define MP make_pair
LL dist[100][100];
map<int , pair<int , int > > mp;
map<pair<int , int > , int > m;
void fill_distance(int v){
    int path[8][2];
    int x = mp[v].first , y = mp[v].second;
    path[0][0] = x+2 , path[0][1] = y+1;
    path[1][0] = x+2 , path[1][1] = y-1;
    path[2][0] = x-2 , path[2][1] = y+1;
    path[3][0] = x-2 , path[3][1] = y-1;
    path[4][0] = x+1 , path[4][1] = y+2;
    path[5][0] = x+1 , path[5][1] = y-2;
    path[6][0] = x-1 , path[6][1] = y+2;
    path[7][0] = x-1 , path[7][1] = y-2;

    for(int i = 0 ; i < 8 ; i ++)
    {
        if(path[i][0] >= 0 && path[i][0] < 8 && path[i][1] >= 0 && path[i][1] < 8){
            dist[v][m[MP(path[i][0] , path[i][1])]] = x*path[i][0] + y*path[i][1];
        }
    }
}
void pre(){
    int k = 0;
    for(int i = 0 ; i < 64 ; i++)
        for(int j = 0 ; j < 64 ; j++){
            dist[i][j] = INT_MAX;
            dist[j][j] = 0;
        }
    for(int i = 0 ; i<64 ; i++){
        fill_distance( i);
    }
    for(int k = 0 ; k < 64 ; k++)
        for(int i = 0 ; i < 64 ; i++)
            for(int j = 0 ; j < 64 ; j++)
                    dist[i][j] = min(dist[i][j] , dist[i][k] + dist[k][j]);
}
int main()
{
    int k = 0;
    for(int i = 0 ; i < 8 ; i++)
        for(int j = 0 ; j < 8 ; j++){
            mp[k] = MP(i , j);
            m[MP(i , j)] = k;
            k++;
        }
    pre();
    int x, y , u ,v;
    while(scanf("%d%d%d%d",&x , &y , &u ,&v)!=EOF){
        int source = m[MP(x,y)], dest = m[MP(u,v)];
        dist[source][dest] == INT_MAX ? printf("-1\n") : printf("%lld\n",dist[source][dest]) ;
    }
    return 0;
}

ARRANGE-Arranging Amplifiers

Arranging Amplifiers

Given below code is for ARRANGE spoj or Arrange Amplifiers spoj.

This question is based on greedy approach.

Main idea is  a^b < b^a (if a>b and not valid for a=3 and b=3) , so place all the amplifiers with higher amplification first . If there is amplifier with amplification 1 the place all these amplifier first.

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n,t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        int array[n],count1=0,count=0,input,j=0;
        for (int i=0; i<n; i++)
        {
            scanf("%d",&input);
            if (input==1)
                count1++;
            else
            {
                array[j++]=input;
                count++;
            }
        }
        sort(array,array+count);
        for (int i=0; i<count1; i++)
            printf("1 ");
        if (count==2 && array[0]==2 && array[1]==3)
            cout<<2<<" "<<3;
        else
        {
            for (int i=count-1; i>=0; i--)
                printf("%d ",array[i]);
        }
        cout<<endl;
    }
    return 0;
}

INS14C-Digo plays with Numbers

Digo plays with Numbers

GIVEN BELOW CODE IS FOR INS14C SPOJ OR DIGO PLAY WITH NUMBER SPOJ.

#include <bits/stdc++.h>
using namespace std;
int main()
{
 int t;
 scanf("%d",&t);
 while(t--)
 {
  int n,k;
  char s[1009];
  scanf("%d%d",&n,&k);
  vector<int>one,zero;
  scanf("%s",s);
  for(int i=0;i<n;i++)
  {
   if(s[i] == 48)
    zero.push_back(i);
   else
    one.push_back(i);
  }
  int count=1,j;
  for(int i=0,j=0;count <= n-k;count++)
  {
   if(count&1){
    if(i<one.size())
     s[one[i++]] = 50;
    else
     s[zero[j++]]=50;
   }
   else{
    if(j<zero.size())
     s[zero[j++]] = 50;
    else
     s[one[i++]]=50;
   }
  }
  for(int i=0;i<n;i++)
   if(s[i]!=50)
    printf("%c",s[i]);
  printf("\n");
 }
 return 0;
}

SIRNUMS-SIR CHIRAG AND MAGIC NUMBERS

SIR CHIRAG AND MAGIC NUMBERS

given below code is for sirnums spoj or sir chirag and magic numbers spoj.

if you want logic mail me. email :- raj.nishant360@gmail.com

#include <bits/stdc++.h>
using namespace std;
int main()
{
 int t;
 scanf("%d",&t);
 while(t--){
 int k,x;
 scanf("%d%d",&k,&x);
 char a[1000009];
 int temp,carry,temp1;
 int flag=0;
 for(int i=x;i<=9;i++)
 {
  a[k-1]=i+48;
  carry=0;
  for(int j=k-2;j>=0;j--)
  {
   a[j]=((a[j+1]-48)*x + carry)%10 + 48;
   carry = ((a[j+1]-48)*x + carry)/10;
  }
  a[k]=0;
  temp=a[0]-48;
  temp1= (temp*x + carry)%10;
  carry=(temp*x + carry)/10;
  if(temp1 == i && carry==0){
   printf("%s\n",a);
   flag=1;
   break;
  }
 }
 if(!flag)
  printf("Impossible\n");
 }
 return 0;
}

JOKER1-Knifes Are Fun

Knifes Are Fun

below given code is for jocker1 spoj or knifes are fun spoj.

#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <map>
#include <string>
#include <cstring>
#include <sstream>
#include <fstream>
#include <climits>
#include <ctime>
#include <algorithm>
using namespace std;
#define MOD 1000000007
int main()
{
 int t;
 scanf("%d",&t);
 while(t--)
 {
  int n;
  scanf("%d",&n);
  int a[n+9];
  for(int i=0;i<n;i++)
   scanf("%d",&a[i]);
  sort(a,a+n);
  long long result=1,flag=1;
  for(int i=n-1;i>=0;i--)
  {
   if(a[i]-i<=0)
   {
    flag=0;
    break;
   }
   result=(result*(a[i]-i))%MOD;
  }
  if(!flag)
   printf("0\n");
  else
   printf("%lld\n",result);
 }
 printf("KILL BATMAN\n");
 return 0;
}

MSCHED-Milk Scheduling

Milk Scheduling

below given code is for msched spoj or milk scheduling spoj.

this is simple implementation of Job Sequencing
:happy coding..

#include <stdio.h>
#include <iostream>
#include <cstdlib>
#include <bitset>
using namespace std;
class job
{
public:
 int deadline;
 int profit;
};
void mergesort(job a[],int low,int mid,int high)
{
 job temp[10009];
 int i=low,k=low,j=mid+1;
 while(i<=mid && j<=high)
 {
  if(a[i].profit >=a[j].profit)
   temp[k++]=a[i++];
  else
   temp[k++]=a[j++];
 }
 while(i<=mid)
  temp[k++]=a[i++];
 while(j<=high)
  temp[k++]=a[j++];
 for(i=low;i<=high;i++)
  a[i]=temp[i];
}
void partition(job a[],int low,int high)
{
 int mid;
 if(low<high)
 {
  mid=(low+high)/2;
  partition(a,low,mid);
  partition(a,mid+1,high);
  mergesort(a,low,mid,high);
 }
}
int main()
{
 int n;
 scanf("%d",&n);
 int i,max=-1,k;
 bool p[10009]={0};
 job j[n+9];
 for(i=0;i<n;i++)
 {
  scanf("%d",&j[i].profit);
  scanf("%d",&j[i].deadline);
 }
 partition(j,0,n-1);
 int total=0,temp;
 for(i=0;i<n;i++)
 {
     temp=j[i].deadline;
     while(temp)
     {
         if(!p[temp]){
   p[temp]=1;
   total+=j[i].profit;
   break;
            }
            else
                temp--;
     }
 }
 printf("%d",total);
 return 0;
}