Two Arrays and Minimum

3.9

16 votes
Easy
Problem

You are given two arrays each with N elements. Elements of each arrays follow a particular generator dependent on factors a,b and c . You have to choose on element from both the arrays such that if you chose ith element from one array and jth element from another array then i should not be equal to j and sum of the both elements should be minimum.
Remember that the generator code is language independent. Please make relevant changes as per the language you use

A[1] = a*c;
for(i=2 ; i<=n ; i++)
{
    A[i] = A[i-1]*a*b*c + A[i-1]*a*b + A[i-1]*a*c;
    A[i] = A[i]%1000000007;
}
B[1] = b*c;
for(i=2 ; i<=n ; i++)
{
    B[i] = B[i-1]*b*c*a + B[i-1]*b*a + B[i-1]*b*c;
    B[i] = B[i]%1000000007;
}    
Input
First line contains a ,b and c as input . Next line contains N as input which is the total elements in the arrays

Output
You have to output the minimum sum of the two elements that can be selected from the array with distinct indices

Scoring
2≤ a,b,c,N ≤ 10 20pts
2≤ N ≤ 10^6,2≤ a,b,c ≤ 10^9 40pts
2≤ N ≤ 10^7,2≤ a,b,c ≤ 10^9 40pts

Sample Input
1 1 1
3
Sample Output
4
Time Limit: 1
Memory Limit: 256
Source Limit:
Explanation

The arrays generated are 1 3 9 and 1 3 9, So answer will be 4

Editor Image

?