Two arrays

You are given two integer arrays, A and B, each containing N integers. The size of the array is <= 1000. You are free to permute the order of the elements in the arrays.

Now for the real question - is there an arrangement of the arrays such that Ai+Bi>=K for all i where Ai denotes the ith element in the array A.

Input Format
The first line contains an integer T denoting the number of test-cases. T test cases follow. Each test case is given in the following format.

The first line contains two integers, N and K. The second line contains N integers separated by a single space, denoting A array. The third line describes B array in a same format.

Output Format
For each test case, if there is such arrangement exists output “YES”, otherwise “NO” (quotes for clarity).

Constraints
1 <= T <= 10
1 <= N <= 1000
1 <= K <= 109
0 <= Ai, Bi <= 109

Sample Input

2
3 10
2 1 3
7 8 9
4 5
1 2 2 1
3 3 3 4

Sample Output

YES
NO

Explanation

The first input has 3 elements in Array A and Array B, we see that the one of the arrangements, 3 2 1 and 7 8 9 has each pair of elements (3+7, 2 + 8 and 9 + 1) summing upto 10 and hence the answer is “YES”.

The second input has B array with three 3s. So, we need at least three numbers in A to be greater than 1. As its not the case, the answer is “NO”.

............................................................................................................
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
int partition(long int A[],long int f,long int l)
{
long int i=f,j,x,temp;
x=A[l];
 for(j=f;j<l;j++)
 {
   if(A[j]<x)
   {
     temp=A[j];
     A[j]=A[i];
     A[i]=temp;
     i++;
   }
 }
    A[l]=A[i];
    A[i]=x;
return i;
}

void Sort1(long int A[],long int f,long int l)
{
 if(f<l)
 {
 long int q=partition(A,f,l);
 Sort1(A,f,q-1);
 Sort1(A,q+1,l);
 }  
}
int main() {
   int T,i;
    scanf("%d",&T);
    for(i=0;i<T;i++)
    {
      int N,i,j,k;
    long int K;
        scanf("%d %ld",&N,&K);
        long int A[N],B[N];
        for(j=0;j<N;j++)
            scanf("%ld",&A[j]);
        for(j=0;j<N;j++)
            scanf("%ld",&B[j]);
        
      Sort1(A,0,N-1);
      Sort1(B,0,N-1);
        k=N;
      for(i=0;i<N;i++,k--)
      {
        if(A[i]+B[k-1]<K)
        {
          printf("NO\n");
          break;
         }
       }
        if(i==N)
       printf("YES\n");
    }    
    
    return 0;
}

Filling Jars

Animesh has N empty candy jars numbered from 1 to N with infinite capacity. He performs M operations. Each operation is described by 3 integers a, b and k where a and b are index of the jars and k is the number of candies to be added inside each jar with index between a and b (both inclusive). Can you tell the average number of candies after M operations?

Input Format
The first line contains two integers N and M separated by a single space.
M lines follow. Each of the M lines contain three integers a, b and k separated by single space.

Output Format
A single line containing the average number of candies across N jars, rounded down to the nearest integer.

Constraints
3 <= N <= 107
1 <= M <= 105
1 <= a <= b <= N
0 <= k <= 106

Sample Input #00

5 3
1 2 100
2 5 100
3 4 100

Sample Output #00

160

Explanation
Initially each of the jar contains 0 candies

0 0 0 0 0  

First operation

100 100 0 0 0  

Second operation

100 200 100 100 100  

Third operation

100 200 200 200 100  

Total = 800, Average = 800/5 = 160

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

int main() {
    int i,j;
    long int N,M,a,b,k,sum=0,c;
    scanf("%ld %ld",&N,&M);
    
    for(i=1;i<=M;i++)
    {
      scanf("%ld %ld %ld",&a,&b,&k);
     c=b-a+1;
     c=c*k;
     sum=sum+c;        
    }
    sum/=N;
    printf("%ld",sum);    
    return 0;
}

Harry Potter And The Floating Rocks

Famous wizard Harry Potter is stuck in a huge room and has to save Hermione Granger from a monster. Harry is at location P1 given by integral coordinates (x₁,y₁) and Hermione is at location P2 given by integral coordinates (x₂,y₂). Sadly P1 and P2 are the only points at which floating rocks are present. Rest of the room is without floor and underneath is hot lava.

Harry has to go from P1 to P2 but there are no floating rocks to walk on. Harry knows a spell that can make the rocks appear but only on the integral coordinates on the straight line joining P1 and P2.

How many rocks can appear at locations (x,y) on the line segment between P1 and P2 (excluding P1 and P2) which satisfy the condition that both x and y are integers?

Input Format
The first line contains a single integer T, the number of test cases. T lines follow.
Each of the following T lines contains one test case each. Each test case contains 4 integers x₁, y₁, x₂ and y₂ separated by a single space.

Output Format
A single line containing the number of rocks.

Constraints
1 <= T <= 10⁵
-10⁹ <= x₁, y₁, x₂, y₂ <= 10⁹

Sample input

3
0 2 4 0
2 2 5 5
1 9 8 16

Sample Output

1
2
6

Explanation

Case 1: As shown in the figure, between (0,2) and (4,0) there’s only 1 integral point (2,1) hence 1 rock.
Case 2: Between (2,2) and (5,5) lies (3,3) and (4,4), hence 2 rocks.
Case 3: Between (1,9) and (8,16) there lies 6 rocks at positions (2,10) (3,11) (4,12) (5,13) (6,14) (7,15).

..............................................................................................

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

long int gcd(long int a,long int b)
{
    if(b==0)
        return a;
    else
        return gcd(b,a%b);
}

int main()
{

    long int t,x1,y1,x2,y2,a,b,ans;
    scanf("%ld",&t);
    while(t--)
    {
        scanf("%ld %ld %ld %ld",&x1,&y1,&x2,&y2);
        a=abs(x2-x1);
        b=abs(y2-y1);
        printf("%ld\n",gcd(a,b)-1);
    }

    return 0;
}

Insertion Sort - Part 2

In Insertion Sort Part 1, you sorted one element into an array. Using the same approach repeatedly, can you sort an entire unsorted array?

Guideline: You already can place an element into a sorted array. How can you use that code to build up a sorted array, one element at a time? Note that in the first step, when you consider an element with just the first element - that is already “sorted” since there’s nothing to its left that is smaller than it.

In this challenge, don’t print every time you move an element. Instead, print the array every time an element is “inserted” into the array in (what is currently) its correct place. Since the array composed of just the first element is already “sorted”, begin printing from the second element and on.

Input Format
There will be two lines of input:

• s - the size of the array
• ar - the list of numbers that makes up the array

Output Format
On each line, output the entire array at every iteration

Constraints
1<=s<=1000
-10000<=x<= 10000 , x ∈ ar

Sample Input

6
1 4 3 5 6 2

Sample Output

1 4 3 5 6 2 
1 3 4 5 6 2 
1 3 4 5 6 2 
1 3 4 5 6 2 
1 2 3 4 5 6 

Explanation
Insertion Sort checks the ‘4’ first and doesn’t need to move it, so it just prints out the array. Next, the 3 is inserted next to the 4 and the array is printed out. This continues one element at a time until the entire array is sorted.

Task
The method insertion Sort takes in one parameter: ar, an unsorted array. Use an Insertion Sort Algorithm to sort the entire array.

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
#include <assert.h>

/* Head ends here */
void insertionSort(int ar_size, int *  ar) {
    int i,j,x;
    for(i=1;i<ar_size;i++)
    {
        x=ar[i];
        j=i;
       while(ar[j-1]>x && j>=1)
       {
        ar[j]=ar[j-1];
           j--;
       }
       ar[j]=x;
     for(j=0;j<ar_size;j++) 
       printf("%d ",ar[j]);
       printf("\n");
    }

    


}

/* Tail starts here */
int main(void) {
   
   int _ar_size;
scanf("%d", &_ar_size);
int _ar[_ar_size], _ar_i;
for(_ar_i = 0; _ar_i < _ar_size; _ar_i++) { 
   scanf("%d", &_ar[_ar_i]); 
}

insertionSort(_ar_size, _ar);
   
   return 0;
}

Mark and Toys

Mark and Jane are very happy after having their first kid. Their son is very fond of toys. Therefore, Mark wants to buy some toys for his son. But he has a limited amount of money. But he wants to buy as many toys as he can. So, he is in a dilemma and is wondering how he can maximize the number of toys he can buy. He has N items in front of him, tagged with their prices and he has only K rupees.

Now, you being Mark’s best friend have the task to help him buy as many toys for his son as possible.

Input Format
The first line will contain two inputs N and K, followed by a line containing N integers

Output Format
Maximum number of toys Mark can buy for his son.

Constraints
1<=N<=105
1<=K<=109
1<=price of any toy<=109

Sample Input

7 50
1 12 5 111 200 1000 10

Sample Output

4

Explanation

He can buy only 4 toys at most. These toys have the following prices: 1,12,5,10.

-------------------------------------------------------------------------------------------------------------

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
#define M 100
int partition(int A[],int f,int l)
{
int i=f,j,x,temp;
x=A[l];
 for(j=f;j<l;j++)
 {
   if(A[j]<x)
   {
     temp=A[j];
     A[j]=A[i];
     A[i]=temp;
     i++;
   }
 }
    A[l]=A[i];
    A[i]=x;
return i;
}

void Sort(int A[],int f,int l)
{
 if(f<l)
 {
 int q=partition(A,f,l);
 Sort(A,f,q-1);
 Sort(A,q+1,l);
 }  
}



void CountTotal(int A[],int N,int K)
{
    int total=0,count=-1,i;
    Sort(A,0,N-1);
    for(i=0;i<N;i++)
    {
        if(total<K)
        {
          total+=A[i];
          count++;
        }
        else 
        {
            printf("%d",count); break;
        }
    
    }
}
int main() 
{
   int A[M],K,i,N;
    scanf("%d %d",&N,&K);
    for(i=0;i<N;i++)
      scanf("%d",&A[i]);

    CountTotal(A,N,K);
    return 0;
}

FizzBuzz

Write a program that prints (to STDOUT) the numbers from 1 to 100. But for multiples of three print “Fizz” instead of the number and for the multiples of five print “Buzz”. For numbers which are multiples of both three and five print “FizzBuzz”.

The goal is to write the shortest code possible.

Scoring: Your score is (200 - number of characters in your source code)/10

#define f printf
main(){for(int i=1;i<=100;i++)(i%3!=0)&&(i%5!=0)?f("%d\n",i):((i%3==0&&i%5==0)?f("FizzBuzz\n"):((i%3==0)?f("Fizz\n"):f("Buzz\n")));}

Insertion Sort - Part 1

Sorting
One common task for computers is to sort data. For example, people might want to see all their files on a computer sorted by size. Since sorting is a simple problem with many different possible solutions, it is often used to introduce the study of algorithms.

Insertion Sort
These challenges will cover Insertion Sort, a simple and intuitive sorting algorithm. We will first start with an already sorted list.

Insert element into sorted list
Given a sorted list with an unsorted number V in the right-most cell, can you write some simple code to insert V into the array so it remains sorted?

Print the array every time a value is shifted in the array until the array is fully sorted. The goal of this challenge is to follow the correct order of insertion sort.

Guideline: You can copy the value of V to a variable, and consider its cell “empty”. Since this leaves an extra cell empty on the right, you can shift everything over until V can be inserted. This will create a duplicate of each value, but when you reach the right spot, you can replace a value with V.

Input Format
There will be two lines of input:

• s - the size of the array
• ar - the sorted array of integers

Output Format
On each line, output the entire array every time an item is shifted in it.

Constraints
1<=s<=1000
-10000<=x<= 10000, x ∈ ar

Sample Input

5
2 4 6 8 3

Sample Output

2 4 6 8 8 
2 4 6 6 8 
2 4 4 6 8 
2 3 4 6 8 

Explanation

3 is removed from the end of the array.
In the 1st line 8 > 3, 8 is shifted one cell right.
In the 2nd line 6 > 3, 6 is shifted one cell right.
In the 3rd line 4 > 3, 4 is shifted one cell right.
In the 4th line 2 < 3, 3 is placed at position 2.

Task

Complete the method insertionSort which takes in 1 parameter:

• ar - an array with the value V in the right-most cell.

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
#include <assert.h>

/* Head ends here */
void insertionSort(int ar_size, int *  ar) {
int i,j,x=ar[ar_size];
    for(i=1;i<=ar_size;i++)
    {
       if(ar[ar_size-i]>x)
       {
       ar[ar_size-i+1]=ar[ar_size-i];
       }
        else{
        ar[ar_size-i+1]=x;
        }
        for(j=0;j<=ar_size;j++)
            printf("%d ",ar[j]);
        printf("\n");
    }
}

/* Tail starts here */
int main(void) {
   
   int _ar_size;
scanf("%d", &_ar_size);
int _ar[_ar_size], _ar_i;
for(_ar_i = 0; _ar_i < _ar_size; _ar_i++) { 
   scanf("%d", &_ar[_ar_i]); 
}

insertionSort(_ar_size-1, _ar);
   
   return 0;
}

Chocolate Feast

Little Bob loves chocolates and goes to the store with a $N bill with $C being the price of each chocolate. In addition, the store offers a discount: for every M wrappers he gives the store, he’ll get one chocolate for free. How many chocolates does Bob get to eat?

Input Format:
The first line contains the number of test cases T (<=1000).
Each of the next T lines contains three integers N, C and M

Output Format:
Print the total number of chocolates Bob eats.

Constraints:
2 <= N <= 100000
1 <= C <= N
2 <= M <= N

Sample input

3
10 2 5
12 4 4
6 2 2

Sample Output

6
3
5

Explanation
In the first case, he can buy 5 chocolates with $10 and exchange the 5 wrappers to get one more chocolate thus making the total number of chocolates he can eat as 6

In the second case, he can buy 3 chocolates for $12. However, it takes 4 wrappers to get one more chocolate. He can’t avail the offer and hence the total number of chocolates remains 3.

In the third case, he can buy 3 chocolates for $6. Now he can give 2 of this 3 wrappers and get 1 chocolate. Again, he can use his 1 unused wrapper and 1 wrapper of new chocolate to get one more chocolate. Total is 5.

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


int CountCho(int N,int C,int M)
{
    int total,repr,temp;
    
    total=N/C;
    repr=total;
    while(repr>=M)
    {
    temp=repr/M;
    repr=temp+repr%M;
      total+=temp;  
    } 
   return total;
}

int main() {
  int Total,i,M,N,C;
  scanf("%d",&i);
    while(i-->0)
    {
    scanf("%d %d %d",&N,&C,&M);
        Total=CountCho(N,C,M);
        printf("%d\n",Total);
    }
    return 0;
}

Lonly Integer in a Array

There are N integers in an array A. All but one integer occurs in pairs. Your task is to find out that number that occurs only once.

Input Format  

The first line of the input contains an integer N indicating number of integers in the array A.

Next line contains N integers each separated by a single space.

Constraints

1 <= N < 100
N % 2 = 1 ( N is an odd number )
0 <= A[i] <= 100, ∀ i ∈ [1, N]

Output Format

Output (S) which is the number that occurs only once.

Sample Input:1

1
1

Sample Output:1

1

Sample Input:2

3
1 1 2

Sample Output:2

2

Sample Input:3

5
0 0 1 2 1

Sample Output:3

2

Explanation

In the first input, we see only 1 element and that element is the answer (1)
In the second input, we see 3 elements, 1 is repeated twice, the only other element 2 is the answer
In the third input, we see 5 elements, 1 and 0 are repeated twice, the other element 2 is the answer

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
#include <assert.h>

/* Head ends here */

int lonelyinteger(int a_size, int* a) 
{
    int count[100];
    for(int i=0;i<100;i++)
    count[i]=0;
    
    for(int i=0;i<a_size;i++)
    {
       count[a[i]]+=1;
    }
    
    for(int i=0;i<100;i++)
    {
      if(count[i]==1)
      return i;
    }
        
return -1;
}

/* Tail starts here */

int main() {
    int res;  
    int _a_size, _a_i;
    scanf("%d", &_a_size);
    int _a[_a_size];
    for(_a_i = 0; _a_i < _a_size; _a_i++) { 
        int _a_item;
        scanf("%d", &_a_item);
        
        _a[_a_i] = _a_item;
    }
    
    res = lonelyinteger(_a_size, _a);
    printf("%d", res);
    
    return 0;
}