Scribd Logo
Upload

Welcome to Scribd!

  • 70 views

    Lab2 Problem A

    Uploaded by

    Teja Ananthasetty
    The document describes 4 problems: 1. Finding the number of possible binary sequences of length N with no consecutive 0s and without leading 0s. 2. Determining if an integer N can be represented as the sum of squares of other integers. 3. Computing the sum of elements in a subarray of an input array between indices i and j, for multiple queries. 4. Finding the product of two input matrices containing real and complex values.

    Copyright:

    Attribution Non-Commercial (BY-NC)
    Download as PDF, TXT or read online from Scribd

    Lab2 Problem A

    Uploaded by

    Teja Ananthasetty
    70 views3 pages
    The document describes 4 problems: 1. Finding the number of possible binary sequences of length N with no consecutive 0s and without leading 0s. 2. Determining if an integer N can be represented as the sum of squares of other integers. 3. Computing the sum of elements in a subarray of an input array between indices i and j, for multiple queries. 4. Finding the product of two input matrices containing real and complex values.

    Original Title

    Lab2 Final

    Copyright

    © Attribution Non-Commercial (BY-NC)

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    The document describes 4 problems: 1. Finding the number of possible binary sequences of length N with no consecutive 0s and without leading 0s. 2. Determining if an integer N can be represented as the sum of squares of other integers. 3. Computing the sum of elements in a subarray of an input array between indices i and j, for multiple queries. 4. Finding the product of two input matrices containing real and complex values.

    Copyright:

    Attribution Non-Commercial (BY-NC)
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    70 views3 pages

    Lab2 Problem A

    Uploaded by

    Teja Ananthasetty
    The document describes 4 problems: 1. Finding the number of possible binary sequences of length N with no consecutive 0s and without leading 0s. 2. Determining if an integer N can be represented as the sum of squares of other integers. 3. Computing the sum of elements in a subarray of an input array between indices i and j, for multiple queries. 4. Finding the product of two input matrices containing real and complex values.

    Copyright:

    Attribution Non-Commercial (BY-NC)
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    You are on page 1of 3

    LAB2 PROBLEM A: Find the number of binary sequences of length N possible with no consecutive zeroes and without leading

    zeroes. Constraints: N<=1000000, T<=10 INPUT: First line contains T, no of test cases Following T line contain an integer N (length of binary sequence) OUTPUT: Output the number of possible binary sequences for each test case. Output can be large , so print (output mod 1000000007) INPUT: 2 2 3 OUTPUT: 2 3 Explanation: For input 1 , {1} is only possible . So output is 1. For input 2, {10,11} are possible so output is 2. For input 3, {101,110,111} are possible so output is 3. PROBLEM B: Given an integer N, decide if it is possible to represent it as a sum of squares of integers. If so, print the "YES" otherwise print "NO". Constraints: a^2 + b^2 = N , 0<=N<=10000000000000 INPUT: First line contains T, number of test cases (T<=10). Following T lines contain an integer N. OUTPUT: Output the result for each test case. Input: 3 1 2 7 Output: YES YES NO Explanation: 1 can be written as 0^2 + 1^2 2 can be written as 1^2 + 1^2 7 cannot be written as a^2 + b^2

    PROBLEM C: You are given an array A[0,..,n-1] of n integers. Can you answer the following query ? Find the sum of all elements between indices i and j i.e., A[i] + A[i+1] + ... + A[j-1] +A[j]. Wait, we are not going to leave you with just one query, we will ask you many such queries, Q of them. Read Input section for more details. INPUT: First line has an integer N, number of elements in the array A. Second line has N integers of the array A, separated by spaces. Third line has integer Q, number of queries to follow. Each of the next Q lines contains two indices i and j, separated by space. OUTPUT: For each of the Q queries, find the value of A[i] + A[i+1] + ... + A[j]. You don't have to output this for each query, just sum the answers for all the queries and output total sum in one line. Also, print the answer followed by a '\n' ( just print '\n', no need to display on screen ) Constraints : 1 <= N <= 1000000, 1 <= Q <= 10000, -1000 <= A[i] <= 1000 and 0 <= i<=j < N Input: 4 1234 3 01 13 33 Output: 16\n Explanation: Sum(0..1) = 1 + 2 = 3 Sum(1..3) = 2 + 3 + 4 = 9 Sum(3..3) = 4 Sum of answers to all queries 3 + 9 + 4 = 16 PROBLEM D: Find out the product of two matrices A[P x Q ] and B[R x S] containing numeric values (possibly complex values as well). Constratins: INPUT: First line contains P<space>Q Following PxQ lines contain the elements of the matrix A( row major order) in the format x<space>y , where x is the real part and y is the imaginary part. This line contains R<space>S Following RxS lines contain the elements of the matrix B( row major order) in the format a<space>b , where a is the real part and b is the imaginary part. Constraints: 1<= P , Q , R , S <= 100 , -1000<=x , y , a ,b <=1000 OUTPUT: Print the output matrix in row major order as mentioned in the example below. Print each element of the matrix in the format a+ib , where a is the real part and b is the imaginary part.

    INPUT: 22 01 01 01 01 22 01 01 01 01 OUTPUT: -2+i0 -2+i0 -2+i0 -2+i0

    You might also like