SPOJ Solutions

Friday, 5 June 2020

AGGRCOW - Aggressive cows

Farmer John has built a new long barn, with N (2 <= N <= 100,000) stalls. The stalls are located along a straight line at positions x1,...,xN (0 <= xi <= 1,000,000,000).

His C (2 <= C <= N) cows don't like this barn layout and become aggressive towards each other once put into a stall. To prevent the cows from hurting each other, FJ wants to assign the cows to the stalls, such that the minimum distance between any two of them is as large as possible. What is the largest minimum distance?

Input

t – the number of test cases, then t test cases follows.

* Line 1: Two space-separated integers: N and C

* Lines 2..N+1: Line i+1 contains an integer stall location, xi

Output
For each test case output one integer: the largest minimum distance.

Example
Input:
1
5 3
1
2
8
4
9
Output:
3

Output details:

FJ can put his 3 cows in the stalls at positions 1, 4 and 8,

resulting in a minimum distance of 3.

Solution: Binary Search

Well, the hint is already given in the SPOJ problem page. But it is confusing at the same time. Because you won't get the solution using Binary Search. Binary search will get you the optimal solution, but you need to still find a way to get all possible solutions.

Let Lim =1,000,000,000

To start thinking of a solution you need first choose the minimum difference between any 2 stable and then verify whether that minimum distance would work or not. Let suppose you have devised a function Fn(x), which tells you whether minimum distance x would is possible or not. Now what, now you will check this for all the numbers 0....Xi.....Lim.

0 is always possible since you can fill all the cows in one stable.

0, 1, 2 ...... Xi, Xi+1,......Lim

you will see that it is always possible to have a small number as a difference between stable, and as you increase the x you might reach a point where it is unstable. In other ways, you need to find Xi where Fn(Xi) is possible but Fn (Xi+1) is not. And X will be your answer. So to find X you can apply binary search on 0 to Lim and find X.

Now our job is to write Fn(X) and binary search which uses this Fn.
Let me give you time to try this before I post my solution.

Saturday, 4 April 2020

Find a pair of natural numbers who have the least energy among all pairs having sum of n

There is a natural number n. You have to find a pair of natural numbers x, y whose sum is n and also have the least energy among other pairs having the sum n. Then output the sum of digits of the pair.

Energy(x) = sum of all digits of x
Total Energy = Energy(x) + Energy(y)

1 <= n <= 10^9

For eg, 
n = 10000
A few pairs: 
5000 + 5000 -> Energy = 10
1000 + 9000 -> Energy = 10
9999 + 1 -> Energy = 37
2999 + 7001 -> Energy = 37

So possible answers are:
(5000, 5000), (1000, 9000) etc 
And Final answer is 10.

IT is not a SPOJ problem. I just came across this problem and wanted to share the tricky solution behind it.

Solution :

If n is of type 10^x then the answer is 10. Otherwise answer is the sum of digits of n.

The idea here is to break down the number into a pair containing digits less than that are present in n. if you break down into smaller digits then sum remains the same as the original number. example for 7= 1-6,2-5,3-4.

for a number like 100, 1000.... digit 1 can’t be broken down into further pairs, so we try to make 10 as the sum of digit so that the sum becomes n. like for 10=5-5,2-8,3-7 100=20-80,40-60

for other numbers, like 123 it can be broken into 100-23, 120-3, 111-12... all will give you sum 6. which is the sum of digits of the original number.

if you try to break down into further pairs like 80-43, 52-71, you will see that the digit sum increases as you have broken down to a number containing digits which are higher than those are present in n. like 8 4,5,7 are greater than 3.

Friday, 2 October 2015

FCTRL - Factorial

See on SPOJ

The most important part of a GSM network is so called Base Transceiver Station (BTS). These transceivers form the areas called cells (this term gave the name to the cellular phone) and every phone connects to the BTS with the strongest signal (in a little simplified view). Of course, BTSes need some attention and technicians need to check their function periodically.

ACM technicians faced a very interesting problem recently. Given a set of BTSes to visit, they needed to find the shortest path to visit all of the given points and return back to the central company building. Programmers have spent several months studying this problem but with no results. They were unable to find the solution fast enough. After a long time, one of the programmers found this problem in a conference article. Unfortunately, he found that the problem is so called "Travelling Salesman Problem" and it is very hard to solve. If we have N BTSes to be visited, we can visit them in any order, giving us N! possibilities to examine. The function expressing that number is called factorial and can be computed as a product 1.2.3.4....N. The number is very high even for a relatively small N.

The programmers understood they had no chance to solve the problem. But because they have already received the research grant from the government, they needed to continue with their studies and produce at least some results. So they started to study behaviour of the factorial function.
For example, they defined the function Z. For any positive integer N, Z(N) is the number of zeros at the end of the decimal form of number N!. They noticed that this function never decreases. If we have two numbers N₁<N₂, then Z(N₁) <= Z(N₂). It is because we can never "lose" any trailing zero by multiplying by any positive number. We can only get new and new zeros. The function Z is very interesting, so we need a computer program that can determine its value efficiently.

Simply you have to find the number of zero's at the end of N! (factorial(N))

Input

There is a single positive integer T on the first line of input (equal to about 100000). It stands for the number of numbers to follow. Then there are T lines, each containing exactly one positive integer number N, 1 <= N <= 1000000000.

Output

For every number N, output a single line containing the single non-negative integer Z(N).

Example

Sample Input:

Sample Output:

Solution- count Number of 5's.

Yeah, that's it. You just to calculate the number the of 5's in the prime factorization of N!.

This is because it is obvious for any factorial to have more number of 2's than 5's in its prime factorization. Thus every 5 which appears in factorization will get a 2 so that it can be multiplied with it to become 10. And it is pretty clear that the number of occurrences of 10 in factorization is the same as the number of 0's at the end.

Logic-

Suppose we have number 100. we need to calculate the number of 5 in the prime factorization of 100!.

We know 100!=1*2*3*4*5....*100

Let zeros= number of zeros initially zero.

Thus every number divisible by 5 (like 5,10,15..95,100) will give one 5 as a factor.

zeros+=(100/5)=20

Similarly numbers divisible by 5*5=25 (like 25,50, 75,100) will give two 5's as factors.

(Since one five is already taken into account)

zeros+=100/25... =24

Now 5^3=125>N(100) thus we stop here.

And the answer is 24.

Simple C++ Implementation is here . Time Taken =0.01 sec.

//zero in factorial


#include <bits/stdc++.h>
 
   int main()
 {int a,zeros,num,i,t,j;
 scanf("%d",&t);
 
while(t--)
 {   
 	scanf("%d",&num);

	  a=5;
	  zeros=0 ;
 		 while(num/a!=0)

			{					

				zeros+=num/a;

				a=a*5;		//increasing a to powers of 5

			}

printf("\n%d",zeros);

}
 
 return 0;
 }

PALIN - The Next Palindrome

See on SPOJ

A positive integer is called a palindrome if its representation in the decimal system is the same when read from left to right and from right to left. For a given positive integer K of not more than 1000000 digits, write the value of the smallest palindrome larger than K to output. Numbers are always displayed without leading zeros.

Input

The first line contains integer t, the number of test cases. Integers K are given in the next t lines.

Output

For each K, output the smallest palindrome larger than K.

Example

Input:
2
808
2133
Output:
818
2222

Solution- Trace from Middle. O(n)

This solution is an approach to avoid recursion.

Take the input as an array of characters (or String). Then there will be 2 big cases.

The input number is a palindrome and has all 9s. For example “9 9 9″. The output should be “1 0 0 1″. for this, we will just output the string of length 1 greater than the previous with 1 at ends and 0 in middle.
Other cases. say 2133

Split it into the left half and right half ("21", "33");
Compare the last digit in the left half and the first digit in the right half.
a. If the right is greater than the left, increment the left and stop. ("22")
b. If the right is less than the left, stop.
c. If the right is equal to the left, repeat step 3 with the second-last digit in the left and the second digit in the right (and so on).
Take the left half and append the left half reversed. That's your next largest palindrome. ("2222")

Applied to a more complicated Even length number:

1.    1234567887654322
2.    12345678   87654322
3.    12345678   87654322
             ^   ^         equal
3.    12345678   87654322
            ^     ^        equal
3.    12345678   87654322
           ^       ^       equal
3.    12345678   87654322
          ^         ^      equal
3.    12345678   87654322
         ^           ^     equal
3.    12345678   87654322
        ^             ^    equal
3.    12345678   87654322
       ^               ^   equal
3.    12345678   87654322
      ^                 ^  greater than, so increment the left

3.    12345679

4.    1234567997654321  answer

Applied to a more complicated ODD length number:

1.    12345678987654322
2.    12345678 9 87654322
3.    12345678 9 87654322
             ^   ^         equal
3.    12345678 9 87654322
            ^     ^        equal
3.    12345678 9 87654322
           ^       ^       equal
3.    12345678 9 87654322
          ^         ^      equal
3.    12345678 9 87654322
         ^           ^     equal
3.    12345678 9 87654322
        ^             ^    equal
3.    12345678 9 87654322
       ^               ^   equal
3.    12345678 9 87654322
      ^                 ^  greater than, so increment the middle,

                           but middle is max (9) here so make it zero

                           and increment the next closer digits on both sides(8)

 3.    12345679 0 97654321 and make second half same.

4.    12345679097654321  answer

Implementation in C++. Time taken is 0.08 sec.

//next palindrome



#include <bits/stdc++.h>
 
    #define max1(x,y) (x)>(y)?(x):(y)
     
    #define s(n) scanint(n)
    #define sc(n) scanf(" %c",&n)
     #define sl(n) scanf("%ld",&n)
    #define sll(n) scanf("%lld",&n)
    #define sf(n) scanf("%lf",&n)
    #define ss(n) scanf("%s",n)
    #define INF (int)1e9
    #define EPS 1e-9
    #define bitcount __builtin_popcount
    #define gcd __gcd
    #define forall(i,a,b) for(int i=a;i<b;i++)
    #define all(a) a.begin(), a.end()
    #define pb push_back
    #define sz(a) ((int)(a.size()))
    #define mp make_pair
    #define checkbit(n,b) ( (n >> b) & 1)
    #define gc getchar_unlocked
    #define l long
  
    using namespace std ;

    inline void scanint(int &x)
    {
    register int c = gc();
    x = 0;
    int neg = 0;
    for(;((c<48 || c>57) && c != '-');c = gc());
    if(c=='-') {neg=1;c=gc();}
    for(;c>47 && c<58;c = gc()) {x = (x<<1) + (x<<3) + c - 48;}
    if(neg) x=-x;
    }
    

    int all_nine(string str)  //check if all digits are '9' 
    {
        for(int i=0;i<str.length();i++)
        {
            if(str[i]!='9')
                return 0;
        }
        return 1;
    }
     
    int main()
    {
        string str;
        int t;
        s(t);
        
        while(t--){
        cin>>str;
        int i,j,num;
        char ans[str.length()+3];
        int n=str.length();
        
        if(all_nine(str))
        {                       //if all 9
            ans[0]='1';
            for(i=0;i<n;i++)   
            {
                ans[i+1]='0';
            }
            ans[n]='1';
            ans[n+1]='\0';
            cout<<ans<<endl;
        }
        
        else
        {
            i=n/2;
            j=i;
     
            if(n%2==0)  
            i=i-1;
     
            while(i>=0 && str[i]==str[j])
            {                   //checking for equal from middle
                                // <---i    j--->           
                i--;
                j++;
            }
     
            if(i<0 || str[i]<str[j])
            {                   //not equal or string is palindroic(i<0)
                i=n/2;
                j=i;
                if(n%2==0)
                    i=i-1;
            int carry=1;
            while(i>=0)
            {
                num=((str[i]-'0')+carry);
                carry=num/10;
                str[i]=(num%10)+'0';
                str[j]=str[i];
                i--;
                j++;
            }
            }
            else
            {
                while(i>=0)     //making second half same.
                    {
                        str[j]=str[i];
                        i--;
                        j++;
                    }
            }
            cout<<str<<endl;
        }
        
        }
        return 0;
    }

ONP - Transform the Expression

See on SPOJ

Transform the algebraic expression with brackets into RPN form (Reverse Polish Notation). Two-argument operators: +, -, *, /, ^ (priority from the lowest to the highest), brackets ( ). Operands: only letters: a,b,...,z. Assume that there is only one RPN form (no expressions like a*b*c).

In simple words, convert an infix expression to postfix.

Input

t [the number of expressions <= 100]
expression [length <= 400]
[other expressions]

Text grouped in [ ] does not appear in the input file.

Output

The expressions in RPN form, one per line.

Example

Input:
3
(a+(b*c))
((a+b)*(z+x))
((a+t)*((b+(a+c))^(c+d)))

Output:
abc*+
ab+zx+*
at+bac++cd+^*

Solution- Using Stack.

It uses a stack which is used to hold operators rather than numbers. The purpose of the stack is to reverse the order of the operators in the expression. It also serves as a storage structure, since no operator can be printed until both of its operands have appeared.

In this algorithm, all operands are printed (or sent to output) when they are read. There are more complicated rules to handle operators and parentheses.

Example
A * (B + C) becomes A B C + *
A subexpression in parentheses must be done before the rest of the expression.

	current symbol	operator stack	postfix string

1	A		A
2	*	*	A
3	(	* (	A B
4	B	* (	A B
5	+	* ( +	A B
6	C	* ( +	A B C
7	)	*	A B C +
8			A B C + *

Since expressions in parentheses must be done first, everything on the stack is saved and the left parenthesis is pushed to provide a marker. When the next operator is read, the stack is treated as though it were empty and the new operator (here the '+' sign) is pushed on. Then when the right parenthesis is read, the stack is popped until the corresponding left parenthesis is found. Since postfix expressions have no parentheses, the parentheses are not printed.

Here is the code to implement this. Time taken 0.00 sec.

//infix to postfix
//stack

#include <bits/stdc++.h>
 
    #define max1(x,y) (x)>(y)?(x):(y)
     
    #define s(n) scanint(n)
    #define sc(n) scanf(" %c",&n)
     #define sl(n) scanf("%ld",&n)
    #define sll(n) scanf("%lld",&n)
    #define sf(n) scanf("%lf",&n)
    #define ss(n) scanf("%s",n)
    #define INF (int)1e9
    #define EPS 1e-9
    #define bitcount __builtin_popcount
    #define gcd __gcd
    #define forall(i,a,b) for(int i=a;i<b;i++)
    #define all(a) a.begin(), a.end()
    #define pb push_back
    #define sz(a) ((int)(a.size()))
    #define mp make_pair
    #define checkbit(n,b) ( (n >> b) & 1)
    #define gc getchar_unlocked
    #define l long
  
    using namespace std ;

    inline void scanint(int &x)
    {
    register int c = gc();
    x = 0;
    int neg = 0;
    for(;((c<48 || c>57) && c != '-');c = gc());
    if(c=='-') {neg=1;c=gc();}
    for(;c>47 && c<58;c = gc()) {x = (x<<1) + (x<<3) + c - 48;}
    if(neg) x=-x;
    }
  // Function to convert Infix expression to postfix 
string InfixToPostfix(string expression);

// Function to verify whether an operator has higher precedence over other
int HasHigherPrecedence(char operator1, char operator2);

// Function to verify whether a character is operator symbol or not. 
bool IsOperator(char C);

// Function to verify whether a character is alphanumeric chanaracter (letter or numeric digit) or not. 
bool IsOperand(char C);

int main() 
{
 string expression; 
 
 int t;
 s(t);
 while(t--){
 getline(cin,expression);
 string postfix = InfixToPostfix(expression);
 cout<<postfix<<"\n";
 }
}

// Function to evaluate Postfix expression and return output
string InfixToPostfix(string expression)
{
 // Declaring a Stack from Standard template library in C++. 
 stack<char> S;
 string postfix = ""; // Initialize postfix as empty string.
 for(int i = 0;i< expression.length();i++) {

  // Scanning each character from left. 
  // If character is a delimitter, move on. 
  if(expression[i] == ' ' || expression[i] == ',') continue; 

  // If character is operator, pop two elements from stack, perform operation and push the result back. 
  else if(IsOperator(expression[i])) 
  {
   while(!S.empty() && S.top() != '(' && HasHigherPrecedence(S.top(),expression[i]))
   {
    postfix+= S.top();
    S.pop();
   }
   S.push(expression[i]);
  }
  // Else if character is an operand
  else if(IsOperand(expression[i]))
  {
   postfix +=expression[i];
  }

  else if (expression[i] == '(') 
  {
   S.push(expression[i]);
  }

  else if(expression[i] == ')') 
  {
   while(!S.empty() && S.top() !=  '(') {
    postfix += S.top();
    S.pop();
   }
   S.pop();
  }
 }

 while(!S.empty()) {
  postfix += S.top();
  S.pop();
 }

 return postfix;
}

// Function to verify whether a character is english letter or numeric digit. 
// We are assuming in this solution that operand will be a single character
bool IsOperand(char C) 
{
 if(C >= '0' && C <= '9') return true;
 if(C >= 'a' && C <= 'z') return true;
 if(C >= 'A' && C <= 'Z') return true;
 return false;
}

// Function to verify whether a character is operator symbol or not. 
bool IsOperator(char C)
{
 if(C == '+' || C == '-' || C == '*' || C == '/' || C== '^')
  return true;

 return false;
}

// Function to verify whether an operator is right associative or not. 
int IsRightAssociative(char op)
{
 if(op == '^') return true;
 return false;
}

// Function to get weight of an operator. An operator with higher weight will have higher precedence. 
int GetOperatorWeight(char op)
{
 int weight = -1; 
 switch(op)
 {
 case '+':
 case '-':
  weight = 1;
 case '*':
 case '/':
  weight = 2;
 case '^':
  weight = 3;
 }
 return weight;
}

// Function to perform an operation and return output. 
int HasHigherPrecedence(char op1, char op2)
{
 int op1Weight = GetOperatorWeight(op1);
 int op2Weight = GetOperatorWeight(op2);

 // If operators have equal precedence, return true if they are left associative. 
 // return false, if right associative. 
 // if operator is left-associative, left one should be given priority. 
 if(op1Weight == op2Weight)
 {
  if(IsRightAssociative(op1)) return false;
  else return true;
 }
 return op1Weight > op2Weight ?  true: false;
}

If there is another solution (without stack) please let us know. You will be given credit.