Posted in GCJ

GCJ Post #6

Continuing with my said goal ( solving 5 problems per day) This is what I did for the 2 days…

((งง •̀•̀__•́•́))งง

I had planned to put 5 problems of the GCJ types and discuss post and lot picked one for the next 2 weeks until July 10th.But I suddenly felt that I was going too easy on myself , so I started doing 20 sums a day since yesterday until I am not able to do 20 sums per day…
.
.
.

So doing that I ended up over working myself… So I ended up cutting down to 3 problems per day… I think I am gradually but definitely loosing my motive to seriously participate for the upcoming contest … *sigh 

So the list of problems that were chosen the last 2 days were:

  1. Chef under pressure 
  2. In a planet far far away 
  3. The Christmas Cookies 
  4. Problem with Strings 
  5. Stringology is magic 
  6. Terrible Vectors 

So the lot picked problem for today is

In a planet far far away…

The problem statement :

CodeChef has sent Jalebi Bai to a new planet to learn a special recipe from them. On her journey from the space station to the head chef’s house, she observed that the multiplication rule on this new planet is slightly different from our Earth.

For example: on this planet, 2*4 may be 9 instead of 8. Weird, she thought.

Curious, Jalebi Bai asked a co-passenger the results of all the 100 multiplications between all pairs of digits.

She figured out that the Standard algorithm for multiplication on this planet follows the same rules as on Earth except that digit multiplication should follow the rule of that planet.

She also found out that any digit multiplied with 0 is 0, the multiplication of x with y is the same as the multiplication of y with x.

Addition is defined to be same as that on the Earth.

For example, if the result of 2 multiplied with 4 is 9, 5 multiplied with 3 is 19, 2 multiplied with 3 is 17 and 4 multiplied with 5 is 24, then multiplication of 25 with 43 will give:

  25
  43
—————
  19
 170
 240
 900
—————
1329
—————

The final answer will be 1329 (following the addition algorithm of the earth for managing carry).

Finally Jalebi Bai meets the head chef of the planet, but the problem is he is ready to give her the recipe only if she can solve a puzzle. He asks her to find the sum of the results of multiplication (according to the planet) between all possible ordered pairs of numbers from the set of positive integer less than or equal to a given number A. Note: If i and j are distinct, then the pair (i,j) is considered different from (j,i).

Jalebi Bai then asks him for a formal multiplication algorithm of the planet, to which the head chef agrees and gives following description.

The multiplication of two numbers X and Y represented as arrays, with M as the digit multiplication matrix, is defined as follows:

Multiply(X[1..p], Y[1..q])
{
    m = [1..p+q]  //Allocate space for result
    for b = 1 to q
    {
        carry = 0
        for a = 1 to p
        {
            m[a + b – 1] += carry + M[X[a]] [Y[b]]
            carry = m[a + b – 1] /10
            m[a + b – 1] = m[a + b – 1] mod 10
        }
        m[b + p] += carry
    }
    answer = 0
    for r = p+q to 1
        answer = answer*10 + m[r]
    return answer
}

Aliens cannot hear any large number, so they want to hear the output modulo Mod, where Mod is some integer.

If Jalebi Bai gives a wrong output, she would be eaten up! (Surprise surprise!)

Jalebi Bai can contact someone on earth for help. She reaches you for a code which can evaluate the output for any given input. Can you help her solve this puzzle?

Input

The digit multiplication rule appears in 9 lines. Line i contains the multiplication rule for the digit i. Each line contains 9 positive integers, each of which is less than 100. It is guaranteed that the given matrix is symmetric.

The next line contains T, the number of test cases to evaluate.

The first line of each test case contains a positive integer A.

The second line of each test case contains Mod.

Output

For each test case, output the solution modulo Mod in a single line.

Example 1

Input:

01 02 03 04 05 06 07 08 09
02 04 06 08 10 12 14 16 18
03 06 09 12 15 18 21 24 27
04 08 12 16 20 24 28 32 36
05 10 15 20 25 30 35 40 45
06 12 18 24 30 36 42 48 54
07 14 21 28 35 42 49 56 63
08 16 24 32 40 48 56 64 72
09 18 27 36 45 54 63 72 81
3
9
10000
73
100
83
100

Output:

2025
1
96

Example 2

Input:

01 01 01 01 01 01 01 01 01
01 04 06 08 10 12 14 16 18
01 06 09 12 15 18 21 24 27
01 08 12 16 20 24 28 32 36
01 10 15 20 25 30 35 40 45
01 12 18 24 30 36 42 48 54
01 14 21 28 35 42 49 56 63
01 16 24 32 40 48 56 64 72
01 18 27 36 45 54 63 72 81
1
9
10000

Output:
1953

Explanation

In an alien world using the base 10 number system, the long multiplication algorithm is the same as Earth’s, except that digit-by-digit multiplication may be different. The results of all 100 digit multiplications are given, and it’s also guaranteed that any digit multiplied by 0 is 0, and multiplication of digits is commutative since it is given that the matrix is symmetrical.

Given A < 10 100000, compute the "alien product" of ii and jj for all pairs (i,j)(i,j) of integers between 11 and A, inclusive. Output this value modulo M (given as input).

So the code I came up with is this…well it works so I have no issue I guess…? 

def mul( num1 , num2 ):
product = 0

dig1 = list(int(d) for d in str(num1))
dig2 = list(int(d) for d in str(num2))
tempPow = 1
for i in range (len(str(num1))) :
for j in range (len(str(num2))) :
tempPow = len(str(num1)) + len(str(num2)) – 2
product += MulTab[int(dig1[i])][int(dig2[j])] * pow(10,tempPow)

return product

for i in range (9):
for j in range (9):
MulTab[i][j] = int ( input() )

for t in range ( int ( input() ) ):
n = int ( input () )
mod = int ( input() )
sum = 0
for i in range ( 1 , n+1 );
for j in range ( i , n+1 ):
sum += mul ( i , j )
print ( sum % mod )


o(╥﹏╥)o
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s