HACKING THE RANDOM NUMBER GENERATOR

SPOJ Problem Set (classical)

9734. Hacking the random number generator

Problem code: HACKRNDM



You recently wrote a random number generator code for a web application and now you notice that some cracker has cracked it. It now gives numbers at a difference of some given value k more predominantly. You being a hacker decide to write a code that will take in n numbers as input and a value k and find the total number of pairs of numbers whose absolute difference is equal to k, in order to assist you in your random number generator testing.

NOTE: All values fit in the range of a signed integer, n,k>=1

Input

1st line contains n & k.
2nd line contains n numbers of the set. All the n numbers are assured to be distinct.

Output

One integer saying the no of pairs of numbers that have a diff k.

Example

Input:
5 2
1 5 3 4 2

Output:
3

SOLUTION-----

#include
#include
using namespace std;
int main()
{
    signed int n,k,count=0,i;
    scanf("%u %u",&n,&k);
    signed int arr[n];
    for(i=0;i<n;i++)
        scanf("%u",&arr[i]);
    sort(arr,arr+n);
    for(i=0;i<n;i++)
    {
        int flag=0,mid;
        //binary search//
        int lb=0,ub=n-1;
        while(lb<=ub)
        {
            mid=(lb+ub)/2;
            if(arr[mid]==arr[i]+k)
            {
                flag=1;
                break;
            }
            else if(arr[mid]>arr[i]+k)
                ub=mid-1;
            else
                lb=mid+1;
        }
        if(flag==1)
            count+=1;
    }
    printf("%u\n",count);
    return 0;
}

PARTY SCHEDULE

SPOJ Problem Set (classical)

97. Party Schedule

Problem code: PARTY



You just received another bill which you cannot pay because you lack the money.
Unfortunately, this is not the first time to happen, and now you decide to investigate the cause of your constant monetary shortness. The reason is quite obvious: the lion's share of your money routinely disappears at the entrance of party localities. 

You make up your mind to solve the problem where it arises, namely at the parties themselves. You introduce a limit for your party budget and try to have the most possible fun with regard to this limit. 

You inquire beforehand about the entrance fee to each party and estimate how much fun you might have there. The list is readily compiled, but how do you actually pick the parties that give you the most fun and do not exceed your budget? 

Write a program which finds this optimal set of parties that offer the most fun. Keep in mind that your budget need not necessarily be reached exactly. Achieve the highest possible fun level, and do not spend more money than is absolutely necessary.

Input

The first line of the input specifies your party budget and the number n of parties. 

The following n lines contain two numbers each. The first number indicates the entrance fee of each party. Parties cost between 5 and 25 francs. The second number indicates the amount of fun of each party, given as an integer number ranging from 0 to 10. 

The budget will not exceed 500 and there will be at most 100 parties. All numbers are separated by a single space. 

There are many test cases. Input ends with 0 0.

Output

For each test case your program must output the sum of the entrance fees and the sum of all fun values of an optimal solution. Both numbers must be separated by a single space.

Example

Sample input:


50 10
12 3
15 8
16 9
16 6
10 2
21 9
18 4
12 4
17 8
18 9 

50 10
13 8
19 10
16 8
12 9
10 2
12 8
13 5
15 5
11 7
16 2

0 0

Sample output:


49 26
48 32

SOLUTION--


#include
int main()
{
    int i,j,budget,party;
    scanf("%d %d",&budget,&party);
    while(budget!=0||party!=0){
    int arr[budget+1][party+1];
    int cost[party+1],fun[party+1];
    for(i=1;i<=party;i++)
        scanf("%d %d",&cost[i],&fun[i]);
    for(i=1;i<=party;i++)
        arr[0][i]=0;
    for(i=1;i<=budget;i++)
        arr[i][0]=0;
    for(i=1;i<=budget;i++)
    {
            for(j=1;j<=party;j++)
            {
                if(i
                    arr[i][j]=arr[i][j-1];
                else
                {
                     int d=arr[i-cost[j]][j-1]+fun[j];
                                        if(d>=arr[i][j-1])
                                                arr[i][j]=d;
                                        else arr[i][j]=arr[i][j-1];
                }
            
                }
             }
            i=budget;
             while(i){
                        if(arr[i][party]==arr[budget][party])
                                i--;
                        else
                                break;
                }
                printf("%d %d\n",i+1,arr[budget][party]);
                scanf("%d %d",&budget,&party);
                
    }
    return 0;
}

RUN LENGTH ENCODING

SPOJ Problem Set (classical)

1787. Run Length Encoding

Problem code: ENCONDIN



Your task is to write a program that performs a simple form of run-length encoding, as described by the rules below.

Any sequence of between 2 to 9 identical characters is encoded by two characters. The first character is the length of the sequence, represented by one of the characters 2 through 9. The second character is the value of the repeated character. A sequence of more than 9 identical characters is dealt with by first encoding 9 characters, then the remaining ones.

Any sequence of characters that does not contain consecutive repetitions of any characters is represented by a 1 character followed by the sequence of characters, terminated with another 1. If a 1 appears as part of the sequence, it is escaped with a 1, thus two 1 characters are output.

Input Specification

The input consists of letters (both upper- and lower-case), digits, spaces, and punctuation. Every line is terminated with a newline character and no other characters appear in the input.

Output Specification

Each line in the input is encoded separately as described above. The newline at the end of each line is not encoded, but is passed directly to the output.

Sample Input

AAAAAABCCCC
12344
Sample Output

6A1B14C
11123124

SOLUTION---

#include
#include
int main()
{
    char str[10000];
    while(gets(str))
    {
        char encoding[20000];
        int k=0,prev_count=0,count=0,i,len;
        char ch;
        len=strlen(str);
        for(i=0;i<len;i++)
        {
            prev_count=count;
            count=1;
            if(str[i]==str[i+1]&&(i+1)<len)
            {
                count=2;
                ch=str[i];
                i=i+2;
                while(str[i]==ch)
                {
                    i=i+1;
                    count=count+1;
                    if(count==9)
                    break;
                }
                i=i-1;
            }
            if(count!=1)
            {
                encoding[k]=count+'0';
                k=k+1;
                encoding[k]=str[i];
                k=k+1;
            }
            else if(count==1)
            {
                if(count!=prev_count){
                    if(str[i]!='1')
                    {
                    encoding[k]='1';
                    k=k+1;
                    encoding[k]=str[i];
                    k=k+1;
                    encoding[k]='1';
                    k=k+1;
                    }
                    else if(str[i]=='1')
                    {
                    encoding[k]='1';
                    k=k+1;
                    encoding[k]='1';
                    k=k+1;
                    encoding[k]='1';
                    k=k+1;
                    encoding[k]='1';
                    k=k+1;
                    }
                }
                else
                {
                    if(str[i]!='1')
                    {
                        k=k-1;
                        encoding[k]=str[i];
                        k=k+1;
                        encoding[k]='1';
                        k=k+1;
                    }
                    else if(str[i]=='1')
                    {
                        encoding[k]='1';
                        k=k+1;
                        encoding[k]='1';
                        k=k+1;
 
                    }
                }
            }
        }
        for(i=0;i<k;i++)
            printf("%c",encoding[i]);
        printf("\n");
    }
    return 0;
}

COKE MADNESS

SPOJ Problem Set (classical)

11373. Coke madness

Problem code: RPLC



David likes coke, lets say he likes it a lot... One day he was walking by a narrow street when he sees a lot of bottles of cokes, from different brands, he wants to drink it all, but he noticed that one brand gives him power, the other brand weaken him, now, he can wait and regain more energy, but he don't want to do that, he will wait at the beginning and, when he has the sufficient energy he will drink all the cokes in the street.

Please, help him find when he will be in the perfect moment to drink all the cokes.



INPUT:

Will start with an integer T denoting the number of test cases, then, T lines will follow, for each test case, there will be an integer N, then, in the next line will be N integers, this will be the number of cokes, and the values of the cokes in the floor (the positive one gives energy, the negative ones will take his energy).



OUTPUT:

Each test case will output the string “Scenario #i: “ where i is the number of test case analyzed, followed by the minimum energy required by David to pass the street.



INPUT

OUTPUT

2

5

4 -10 4 4 4



5

1 2 3 4 5

Scenario #1: 7

Scenario #2: 1




“Blank line between test cases for clarification and separation”
“The life of David should never reach 0 or less”



CONSTRAINTS:
1<=N<=1000000
-10000000<=Ni<=10000000

SOLUTION----

#include
#include
int main()
{
    int t,i,count=1;
    scanf("%d",&t);
    while(t--)
    {
        long long int num,sum=0,coke=0;
        scanf("%lld",&num);
        long long int arr[num];
        for(i=0;i<num;i++)
        {
            scanf("%lld",&arr[i]);
            sum+=arr[i];
            if(sum<0)
            {
                coke+=fabs(sum);
                sum=0;
            }
        }
        
        printf("Scenario #%d: %lld\n",count,coke+1);
        count+=1;
        
    }
    return 0;
}

FAVORITE DICE

SPOJ Problem Set (classical)

1026. Favorite Dice
Problem code: FAVDICE



BuggyD loves to carry his favorite die around. Perhaps you wonder why it's his favorite? Well, his die is magical and can be transformed into an N-sided unbiased die with the push of a button. Now BuggyD wants to learn more about his die, so he raises a question:

What is the expected number of throws of his die while it has N sides so that each number is rolled at least once?

Input

The first line of the input contains an integer t, the number of test cases. t test cases follow.

Each test case consists of a single line containing a single integer N (1 <= N <= 1000) - the number of sides on BuggyD's die.

Output

For each test case, print one line containing the expected number of times BuggyD needs to throw his N-sided die so that each number appears at least once. The expected number must be accurate to 2 decimal digits.

Example

Input:
2
1
12

Output:
1.00
37.24

SOLUTION---



#include
int main()
{
    int t,num,i;
    scanf("%d",&t);
    double ans;
    while(t--)
    {
        ans=0.0;
        scanf("%d",&num);
        double k=num;
        for(i=num;i>=1;i--)
        {
            ans+=num/k;
            k=k-1;
        }
        printf("%.2lf\n",ans);
    }
    return 0;
    
}

Simple Arithmetics II

SPOJ Problem Set (classical)

4452. Simple Arithmetics II

Problem code: ARITH2



While browsing aimlessly, Peter stumbled upon an old riddle he used to solve on his calculator when he was still young. It was the kind of a riddle where you punch in a bunch of numbers and operators into a simple pocket calculator and then turn it upside down to get the answer:

These come in many different sizes but they are always exactly one foot long. Answer: 103 * 103 * 5.

What are made of ice to keep people warm? Answer: 50 * 40 * 250 + 791.

After a few minutes he found a large amount of such riddles and full of excitement he went to solve them. He turned his computer screen upside down...

... only to find out that he does not have a reasonable calculator program installed on his computer.

Problem specification

You are given multiple sequences of button presses of a simple pocket calculator that consist of digits and arithmetic operators. For each such sequence find the number it would produce on a pocket calculator's display.

Note that the pocket calculator evaluates the operators in the order in which they are given. (i.e., there is no operator precedence.) Assume that the display of the calculator is large enough to show the result, and that its memory is sufficient to store all intermediate results.

Input specification

The first line of the input file contains an integer T specifying the number of test cases. Each test case is preceded by a blank line.

Each test case represents one sequence of button presses for a pocket calculator. The sequence consists of non-negative integers and arithmetic operators and ends with an equal sign. It may also contain spaces to improve readability.

The operator / represents integer division, rounded down. You may assume that no test case contains division by zero and that in all test cases all intermediate results are non-negative.

Tip: long long int in C/C++, long in Java or int64 in Pascal is enough for this problem.

Output specification

For each sequence from the input file output the number that would be displayed on the calculator.

Example

Input:
4

1 + 1 * 2 =

29 / 5 =

103 * 103 * 5 =

50 * 40 * 250 + 791 =

Output:
4
5
53045
500791

SOLUTION----



#include
#include
int main()
{
    int t,len=0;
    char str[1000000];
    char oper[1000000];
    scanf("%d ",&t);

    while(t--)
    {

        gets(str);
        len=strlen(str);
        long long int i=0,a=0,b=0,temp=0,k=1,d,j;
  
        while(str[i]!='*'&&str[i]!='+'&&str[i]!='-'&&str[i]!='/')
        {

            if(str[i]!=' ')
            {
                d=str[i]-'0';
                a=a*10+d;
            }
            i=i+1;
        }
       
       oper[0]=str[i];
        for(j=i+1;j
        {
          
             while(str[j]!='*'&&str[j]!='+'&&str[j]!='-'&&str[j]!='/'&&j
             {
                if(str[j]!=' ')
                {
                d=str[j]-'0';
          
                b=b*10+d;
                }
                j=j+1;
             }
          
            if(str[j]!='=')
               oper[k]=str[j];
            char ch=oper[k-1];
            if(ch=='+')
                temp=a+b;
            if(ch=='-')
                temp=a-b;
            if(ch=='*')
                temp=a*b;
            if(ch=='/')
                temp=a/b;
            a=temp;
            
            b=0;
            k=k+1;
        }
        printf("%lld\n",a);

        gets(str);
}
    return 0;
}

Kth SMALLEST ELEMENT

Q.) FIND THE KTH SMALLEST ELEMENT IN A GIVEN ARRAY .
SOLUTION--







#include
#include
using namespace std;
int main()
{
    int n,k,i,min;
    printf("enter the size of array=");
    scanf("%d",&n);
    int arr[n];
    printf("the velue of k=");
    scanf("%d",&k);
    for(i=0;i
        scanf("%d",&arr[i]);
    sort(arr,arr+k);
    min=arr[k-1];
    for(i=k;i
    {
        if(arr[i]
        {
            arr[k-1]=arr[i];
            sort(arr,arr+k);
            min=arr[k-1];
        }
    }
    printf("%dth smallest element in array=%d",k,arr[k-1]);
    return 0;
}