Thread: see if u can help me with this

  1. #1
    Registered User
    Join Date
    Jul 2014
    Posts
    41

    see if u can help me with this

    this is a programming practice called rupsa and the game:

    Princess Rupsa saw one of her friends playing a special game. The game goes as follows:
    • N+1 numbers occur sequentially (one at a time) from A0 to AN.
    • You must write the numbers on a sheet of paper, such that A0 is written first. The other numbers are written according to an inductive rule — after Ai-1 numbers have been written in a row, then Ai can be written at either end of the row. That is, you first write A0, and then A1 can be written on its left or right to make A0A1 or A1A0, and so on.
    • Ai must be written before writing Aj, for every i < j.
    • For a move in which you write a number Ai (i>0), your points increase by the product of Ai and its neighbour. (Note that for any move it will have only one neighbour as you write the number at an end).
    • Total score of a game is the score you attain after placing all the N + 1 numbers.

    Princess Rupsa wants to find out the sum of scores obtained by all possible different gameplays. Two gameplays are different, if after writing down all N + 1 numbers, when we read from left to right, there exists some position i, at which the gameplays have aj and ak written at the ith position such that j ≠ k. But since she has recently found her true love, a frog Prince, and is in a hurry to meet him, you must help her solve the problem as fast as possible. Since the answer can be very large, print the answer modulo 109 + 7.

    Input:

    • The first line of the input contains an integer T denoting the number of test cases.
    • The first line of each test case contains a single integer N.
    • The second line contains N + 1 space-separated integers denoting A0 to AN.

    Output:

    • For each test case, output a single line containing an integer denoting the answer.

    Constraints:

    • 1 ≤ T ≤ 10
    • 1 ≤ N ≤ 105
    • 1 ≤ Ai109


    Example
    Input:
    2
    1
    1 2
    2
    1 2 1

    Output:
    4
    14
    Explanation


    • There are 2 possible gameplays. A0A1 which gives score of 2 and A1A0 which also gives score of2. So the answer is 2 + 2 = 4

    **********************************************
    done.
    my code gives the correct answer everytime but when i submit, it always says wrong answer.
    i don't know what is wrong. please help.
    here is my code:
    Code:
    #include<iostream>
    #include<vector>
    #include<cmath>
    #include<string>
    using namespace std;
    
    
    int length = 0;
    unsigned long long sum = 0;
    
    
    void solve(const unsigned long long & l, const unsigned long long & r, const vector<unsigned long long> & v, const int & left, const unsigned long long & prevSum)
    {
        if (left == 0)
        {
            sum += prevSum;
            return;
        }
        sum += prevSum *((unsigned long long)pow(2,left));
        int next = length - left;
        unsigned long long subSum1 = r*v[next];
        solve(l, v[next], v, left - 1, subSum1);
        unsigned long long subSum2 = l*v[next];
        solve(v[next], r, v, left - 1, subSum2);
    }
    
    
    unsigned long long findSum(const vector<unsigned long long> & v)
    {
        unsigned long long l = v[0];
        unsigned long long r = v[1];
        solve(l, r, v, length - 2, l*r);
        l = v[1];
        r = v[0];
        solve(l, r, v, length - 2, l*r);
        return sum % 1000000007;
    }
    
    
    int main()
    {
        int T;
        cin >> T;
        while (T--)
        {
            cin >> length;
            ++length;
            unsigned long long num;
            vector<unsigned long long> v = vector<unsigned long long>();
            for (int i = 0; i < length; i++)
            {
                cin >> num;
                v.push_back(num);
            }
            printf("%llu\n",findSum(v));
            sum = 0;
        }
    }
    Last edited by V8cTor; 05-15-2016 at 12:13 AM.

  2. #2
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,651
    > Since the answer can be very large, print the answer modulo 109 + 7.
    I think this means
    return sum % 100000000 + 7;
    not
    return sum % 1000000007;
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

Popular pages Recent additions subscribe to a feed

Tags for this Thread