Shooting Targets

PKJ

 Coding Problem Keys 

 Shooting Targets 

 Problem Statement 

N shooting targets are placed in a two dimensional grid and their x and y co-ordinates are provided. The x and y co-ordinates are integer value. When a bullet is fired along a straight line (either parallel to x-axis or y-axis) it eliminates all the targets along it's path.
Assuming a bullet can be fired from negative infinity to positive infinity along a straight line parallel to both x and y-axis, find the minimum number of bullets that need to be fired to eliminate all targets.

 Boundary Condition(s) 

1 <= N <= 100
-100 <= x, y <= 100

 Input Format 

The first line contains the value of N.
The next N lines contain the two integers (x and y) in each line separated by space(s).

 Output Format 

The first line contains the minimum number of bullets that need to be fired to eliminate all targets.

 Example Input/Output 1 

 Input 

9
4 0
4 1
3 0
2 1
1 1
-2 0
1 2
-1 -1
-2 -1

 Output 

4

 Explanation 

The first bullet is fired parallel to X-axis through the line Y = 0.
The second bullet is fired parallel to X-axis through the line Y = 1.
The third bullet is fired parallel to X-axis through the line Y = -1.
The fourth bullet is fired parallel to X-axis through the line Y = 2.

 Example Input/Output 2 

 Input 

8
2 3
-5 -1
0 4
1 2
7 2
4 0
3 5
1 1

 Output 

7

 Max Execution Time Limit: 5000 millisecs 

 Solution 

 Programming Language: C Language 

#include <stdio.h>
struct p{
    int xy,c;
};
int f(int a,struct p *k,int l){
    for(int i=0;i<l;i++){
        if(k[i].xy==a)
        return i;
    }return -1;
}
void r(struct p *a,int x,int p[][2],int k,int l,int n){
    for(int i=0;i<n;i++){
        if(p[i][k]==x){
            int h=f(p[i][k^1],a,l);
            a[h].c--;
        }
    }
}
struct p * m(struct p *k,int l){
    struct p *m=k;
    for(int i=1;i<l;i++){
        if(m->c<k[i].c)
        m=k+i;
    }return m;
}
int main(){
    int n;
    scanf("%d",&n);
    int p[n][2],xc=0,yc=0,k,t=0,c=0;
    struct p x1[n],y1[n],*tempx,*tempy;
    for(int i=0;i<n;i++){
        scanf("%d%d",&p[i][0],&p[i][1]);
        k=f(p[i][0],x1,xc);
        if(k==-1){
            x1[xc].xy=p[i][0];
            x1[xc++].c=1;
        }else
            x1[k].c++;
            k=f(p[i][1],y1,yc);
            if(k==-1){
                y1[yc].xy=p[i][1];
                y1[yc++].c=1;
            }else
                y1[k].c++;
    }
    tempy=m(y1,yc);
    tempx=m(x1,xc);
    while(t!=n){
        if(tempx->c>tempy->c){
            t+=tempx->c;
            tempx->c=0;
            r(y1,tempx->xy,p,0,yc,n);
            tempx=m(x1,xc);
            tempy=m(y1,yc);
        }else{
            t+=tempy->c;
            tempy->c=0;
            r(x1,tempy->xy,p,1,xc,n);
            tempy=m(y1,yc);
            tempx=m(x1,xc);
        }c++;
    }printf("%d",c);
}

// Published By PKJCODERS

 (Note: Incase If the code doesn't Pass the output kindly comment us with your feedback to help us improvise.) 

Comments

Post a Comment

Popular Posts

Same Unit Digit Adjacent Numbers

PKJ
 Coding  Problem  Keys   Same Unit Digit Adjacent Numbers    Problem Statement  A matrix of size R*C (R rows and C columns) containing numbers (positive integer values) is passed as input. The program must print the count C of numbers in a given cell which has at least one adjacent cell (in the same row) containing a number with the same unit digit.  Input Format  The first line contains R and C separated by a space. Next R lines contains C values separated by a space.  Output Format  The first line contains C.  Boundary Conditions  1 <= R, C <= 100.  Example Input/Output 1   Input  4 3 20 27 67 13 74 100 37 90 97 53 75 44  Output  2  Explanation  The numbers are 27 67 in the first row where both have 7 as their unit digit.  Note:  Max Execution Time Limit: 5000 millisecs   Solution   Programming Language: C Language  #include<stdio.h...
Click to Continue...

Print Grandson's Name

PKJ
 Coding Problem Keys   Print Grandson's Name   Problem Statement  The program must accept the first and last names of three persons who are in a family tree and print the grandson's name. Note: The last name of a person is nothing but the father's first name.  Boundary Condition(s)  Length of first and last names are from 3 to 100.  Input Format  The first line contains the first and last name of person 1 separated by a space. The second line contains the first and last name of person 2 separated by a space. The third line contains the first and last name of person 3 separated by a space.  Output Format  The first line contains the first and last name of the grandson separated by a space.  Example Input/Output 1   Input  Arun Kumar Swamy Nathan Kumar Swamy  Output  Arun Kumar  Note: Max Execution Time Limit: 5000 millisecs   Solution   Programming Language: Python 3 Languag...
Click to Continue...

String Pattern - Inverted U

PKJ
 Coding Problem Keys   String Pattern - Inverted U   Problem Statement  Three strings S1, S2 and S3 are passed as the input. The program must print the pattern as shown in the Example Input/Output section. Out of these three strings, the two strings that are print along the left most column and the right most column will be of the same length. The string printed along the first row may or may not be equal in length to the other two strings but it's first character will be same as the first character of the string in the left most column and it's last character will be as same as the first character of the string in the right most column. The string values appearing on the top, left, right can appear in any order in the input.  Boundary Condition(s)  2 <= Length of strings <= 1000  Input Format  The first line contains the string value S1. The second line contains the string value S2. The third line contains the string value S3. ...
Click to Continue...

Multi-Storey Car Parking Lot

PKJ
 Multi-Storey Car Parking Lot   Problem Statement:  The program must accept an integer matrix of size R*C representing a multi-storey car parking lot. The integer 0 represents an empty slot and the integer 1 represents a car. The entry point is always present at the bottom-right of the ground floor. The way to reach the 1st floor is on the left side of the ground floor. The way to reach the 2nd floor is on the right side of the 1st floor. Similarly, the ways to the remaining floor are present on the left side and right side alternatively. A person wants to park his car in the first occurring empty slot on or above the X th  floor. The value of x is also passed as the input. The program must print the instructions he needs to follow to park his car as the output. The instructions must be in the following formats.     ➝ L followed by an integer K - It indicates that he needs to move K slots towards left.      ➝ R followed by an integer K ...
Click to Continue...

File - N Words Concatenate

PKJ
 Coding Problem Keys   File - N Words Concatenate    Problem Statement  N words are passed as the input to the program. The program must concatenate the N words into a single string and write it into a file called output.txt (whose location is same as the program execution location). Fill in the missing lines of code so that the program executes successfully.  Input Format  The first line contains N. N lines contain the N words.  Output output.txt file is created into which these N words are concatenated and written into  Boundary Conditions  1 <= N <= 100  Example Input/Output 1   Input  3 good morning friend  Output File Content  goodmorningfriend  Note:  Max Execution Time Limit: 3000 millisecs   Solution   Programming Language: Java Language  import java.io....
Click to Continue...

Swap and Reverse the String

PKJ
 Coding Problem Keys   Swap and Reverse the String   Problem Statement  The program must accept a string S as the input. The program must swap the first two characters then swap the next two characters and so on. The program must print the modified string S in the reverse order as the output. Note: The last character is not swapped since it has no pair as the length is odd.  Input Format  The first line contains the value of string S.  Output Format  The first line contains the modified string value.  Boundary Condition(s)  1 <= Length of S <= 10000  Example Input/Output 1   Input  elephant   Output  nthaepel   Explanation  The 1st and 2nd characters are e and l , after swapping the characters are l and e . The 3rd and 4th characters are e and p , after swapping the characters are p and e . The 5th and 6th characters are h and a , after swapping the characters are a and h . T...
Click to Continue...