Updates from September, 2016 Toggle Comment Threads | Keyboard Shortcuts

  • loctv 3:02 pm on September 7, 2016 Permalink | Reply
    Tags:   

    Problem: GCD and Fibonacci Numbers 

    You will be given two positive numbers M and N. Your task is to print the greatest common divisor of Fib(M) and Fib(N) where Fib(x) means the xth Fibonacci numbers defined as:

    Fib(0) = 0

    Fib(1) = 1

    for n > 1, Fib(n) = Fib(n-1) + Fib(n-2)

    Input:
    The first line of input contains a single integer T denoting the number of test cases. Then T test cases follow. Each test case consists of exactly one line. This line consists of two space separated positive integers N and M.

    Output:

    Corresponding to each test case, in a new line, print the value of gcd( Fib(M), Fib(N) ) modulo 100.

    Constraints:

    1 ≤ T ≤ 1000

    1 ≤ M, N ≤ 1000

    Example:

    Input

    2
    3 6
    7 8

    Output

    2
    1

    Explanation:

    Fib(3) = 2 and Fib(6) = 8

    GCD(2,8)%100 = 2

    Fib(7) = 13 and Fib(8) = 21

    GCD(13,21)%100 = 1

    def nth_fibo(n):
        """return the nth fibonacci number"""
        if n == 0 or n == 1:
            return n
        n1, n2 = 0, 1
        for _ in range(n):
            n1, n2 = n2, n1+n2
        return n1
    
    def gcd(a, b):
        if b == 0:
            return a
        else:
            return gcd(b, a % b)
    
    if __name__ == '__main__':
        t = input()
        for _ in range(t):
            a, b = map(int, raw_input().split())
            print gcd(nth_fibo(a), nth_fibo(b))%100
    
    Advertisements
     
  • loctv 2:25 pm on September 7, 2016 Permalink | Reply
    Tags:   

    Problem: Collection of pens 

    Everyone have some habits to collect one thing or the other. Harshit also has the craze to collect pens but in 3 piles. In first pile, he collected A pens and in the second pile, he collected B pens but in the third and the last pile , he think of something different. He decided to collect only the minimum number of pens in third pile so that the sum of pens in the three piles will give him a prime number. Note: there should be atleast one pen in the third pile.

    Input:

    First line contains the test cases,t. Then T test cases follow. Each line of the test case two space separated values A,B ie. number of pens in first and
    second pile respectively.

    Output:
    Print the minimum number of pens that should be there in the third pile so that sum of all three piles produces a prime number.

    Constraints:
    1<=T<=30
    1<=A<=1000
    1<=B<=1000

    Example:

    Input:
    2
    1 3
    4 3

    Output
    1
    4

    Explanation:

    In first case,Harshit put one pen in first pile and 3 pens in second pile which give 4 as a sum.So if he adds one pen in the third pile, the sum will yield a prime number ie.5
    Therefore the answer is 1.
    Similarly for other test case

    Python 2.7

     

    from math import *
    def make_primes():
        sieve_eratosthenes = [True]*3001
        for i in range(2, int(sqrt(len(sieve_eratosthenes)))):
            if sieve_eratosthenes[i]:
                temp = i+i
                for j in range(temp,len(sieve_eratosthenes),i):
                    sieve_eratosthenes[j] = False
        result = []
        for i in range(2, len(sieve_eratosthenes)):
            if sieve_eratosthenes[i]:
                result.append(i)
        return result
    
    if __name__ == '__main__':
        t = input()
        primes = make_primes()
        for _ in range(t):
            a, b = map(int, raw_input().split())
            ab = a+b
            for prime in primes:
                if prime > ab:
                    print prime-ab
                    break
    
     
  • loctv 1:24 pm on September 7, 2016 Permalink | Reply
    Tags:   

    Problem: Largest number with given sum 

    A boy lost the password of his super locker. He remembers the number of digits N as well as the sum S of all the digits of his password. He know that his password is the largest number of N digits that can be possible with given sum S. As he is busy doing his homework, help him retrieving his password.

    Input:

    The first line of input contains an integer T denoting the number of test cases. Then T test cases follow. The first line of each test case contains two space separated integers N and S, where N is the number of digits in password and S is the sum of all the digits of the password.

    Output:
    Corresponding to each test case, in a new line, print the largest integer if possible , else print -1.

    Constraints:
    1<= T <= 100
    1<= N <= 10000
    0<= S <= 100000000

    Example:

    Input:

    3
    5 12
    3 29
    3 26

    Output:
    93000
    -1
    998

    Explanation :

    In first test case, sum of elements is 12. Largest possible 5 digit number is 93000.
    In second test case, there is no such three digit number whose sum is 29.

    Python 2.7

    t = input()
    for _ in range(t):
        n, m = [int(x) for x in raw_input().split()]
        #n digits number will have max sum of its digit = n*9
        if 9*n &lt; m: 
            print -1
        else:
            s = ''
            if m &lt; 9:
                s += str(m)
            else:
                s += str(9)
                m -= 9
                while m &gt; 0:
                    if m &gt;= 9:
                        s += str(9)
                    else:
                        s += str(m)
                    m -= 9
            s += ('0'*(n-len(s)))
            print s
    
     
  • loctv 1:03 pm on September 7, 2016 Permalink | Reply
    Tags:   

    Problem: Mega SALE 

    LALU wanted to purchase a laptop so he went to a nearby sale.There were n Laptops at a sale. Laptop with index i costs ai rupees. Some Laptops have a negative price — their owners are ready to pay LALU if he buys their useless Laptop. LALU can buy any Laptop he wants. Though he’s very strong, he can carry at most m Laptops, and he has no desire to go to the sale for the second time. Please, help LALU find out the maximum sum of money that he can earn.

    Input:

    First line of the input contains T denoting the number of test cases.Each test case has 2 lines :

    • first line has two spaced integers n m.
    • second line has n integers [a0…ai…an-1].

    Output:

    The maximum sum of money that LALU can earn, given that he can carry at most m Laptops.
    Constraints:

    1≤T≤10

    1≤n,m≤100

    -1000≤ai≤1000
    Sample Input:

    1

    5 3

    -6 0 35 -2 4

    Sample Output:

    8

    Explanation:

    LALU takes the laptops with -6 and -2 and thus earns 8 rupees.

     

    Python 2.7

     

    t = input()
    for _ in range(t):
        n, m = [int(x) for x in raw_input().strip().split()]
        laptops = [int(x) for x in raw_input().strip().split()]
        laptops.sort()
        earn, amount = 0, 0
        for _ in laptops:
            if _ &lt;= 0:
                earn += _
                amount += 1
                if amount == m:
                    break
            else:
                break
        print earn*-1
    
     
  • loctv 12:52 pm on September 7, 2016 Permalink | Reply
    Tags:   

    Problem: Sachin’s love for runs 

    Sachin always wanted to score more and more runs for his team. Sometimes he succeed in doing that and sometimes he fails.He also has a habit of noting down the runs he scored after every match in his diary. After matches he always look for his scores. In i-th match he score A[i] runs. Now he wanted to know the length of the maximum non-decreasing sub segment in sequence A. As he want to go for another match, help him in doing this task.

    Input:
    The first line contains T denoting the number of test cases . Then T test cases follow . The first line of each test case is an integer N . Then in the next line are N space separated values of the array A [ ] .

    Output:
    Print a single integer which denotes  the length of the maximum non-decreasing sub-segment.

    Constraints:
    1<=T<=30
    1<=N<=105
    1 ≤ A[ ] ≤ 109
    Example:

    Input    
    2
    6
    2 2 1 3 4 1
    3
    2 2 9

    Output
    3
    3

    Explanation

    In the first test the maximum non-decreasing sub-segment is  the segment with numbers from the third to the fifth one.

    In the second test the maximum non-decreasing sub-segment is the numbers from the first to the third one.

    Python: 2.7

    t = input()
    for _ in range(t):
        n = input()
        l = [int(x) for x in raw_input().strip().split()]
        start, lndss, temp = l[0], 1, 1
        #lnds = longest non-decreasing sub-segment
        for i in range(1, len(l)):
            if l[i] >= l[i-1]:
                temp += 1
            else:
                if temp > lndss:
                    lndss = temp
                temp = 1
            if i == len(l)-1:
                if temp > lndss:
                    lndss = temp
    
        print lndss
    
     
c
Compose new post
j
Next post/Next comment
k
Previous post/Previous comment
r
Reply
e
Edit
o
Show/Hide comments
t
Go to top
l
Go to login
h
Show/Hide help
shift + esc
Cancel