OJ Board

Posted: **Tue Mar 04, 2014 3:11 pm**

So, those who're completely stuck, here are some hints that I'd like to share as I solved the problem. Note that as the numbering of the hints increases, the problem should get easier to solve. So, bear this in mind and read as much - or as little as you need to.

Hint #1
First, notice the the expansion for one the sample inputs provided

Input:

Code: Select all

3 3

Expansion:

Code: Select all

1 x 3^1 + 2 x 3^2 + 3 x 3^3 = 3 + 18 + 81 = 102

Note that the "x" stands for "times" - the multiplication symbol. Not the letter "x".

Hint #2
More generally, using lower-case "a" instead of upper-case "A" (which is plain weird to use) this can be written out as

Code: Select all

a + 2 x a^2 + 3 x a^3 + ... + n x a^n

See if it's possible to reduce this formula.

Hint #3
Let

Code: Select all

y = a + 2 x a^2 + 3 x a^3 + ... + n x a^n

Multiplying by a on both sides, we have

Code: Select all

ay = a x (a + 2 x a^2 + 3 x a^3 + ... + n x a^n)
ay = a^2 + 2 x a^3 + 3 x a^4 + ... + (n - 1) x a^n + n x a^(n + 1)

Now, subtracting ay from y we have

Code: Select all

y - ay = (a + 2 x a^2 + 3 x a^3 + ... + n x a^n ) - (a^2 + 2 x a^3 + 3 x a^4 + ... + (n - 1) x a^n + n x a^(n + 1))
y - ay = a + (2 x a^2 - a^2) + (3 x a^3 - 2 x a^3) + ... + (n x a^n - (n - 1) x a^n) - n x a^(n + 1)
y (1 - a) = (a + a^2 + a^3 + ... + a^n) - n x a^(n + 1)

Note that dividing both sides by (1 - a), gives us y - which is what we're after. Try to see if it's possible to find a formula for

Code: Select all

a + a^2 + a^3 + ... + a^n

Hint #4
Let

Code: Select all

z = a + a^2 + a^3 + ... + a^n

Dividing by a on both sides we have

Code: Select all

z / a = 1 + a + a^2 + ... + a^(n - 1)

Subtracting this amount from z, we have

Code: Select all

z - (z / a) = a + a^2 + a^3 + ... + a^n - (1 + a + a^2 + ... + a^(n - 1)) = a^n - 1

Now,

Code: Select all

z(1 - 1/a) = a^n -1

Find out z in terms of a and n and replace this in what was given at the end of Hint #3.

Posted: **Wed Feb 25, 2015 9:12 am**

http://ideone.com/r1mE8t
why tle-!!!!!!!!!!!!!!!!!

Posted: **Thu Feb 26, 2015 2:14 am**

Try precalculating the output for every possible input.

Posted: **Sat Aug 22, 2015 8:17 pm**

I am getting Runtime error
but I can't find out the problem

Could any one help please

here is my code

Code: Select all

import java.math.BigInteger;
import java.util.Scanner;

public class Main {

	private static Scanner helal;

	public static void main(String[] args) {
		
		helal = new Scanner(System.in);
		BigInteger  n,m,x,i;
		long  j=0;
		
		BigInteger zero = new BigInteger("0");
		BigInteger one= new BigInteger("1");

		for(;;)
		{
			n=helal.nextBigInteger();
			m=helal.nextBigInteger();
			i=zero;
			x=zero;
			j=0;
				for(;;)
				{
					
					i=i.add(one);
					j++;
					x=x.add(i.multiply(m.pow((int) j)));
					
					if(n.equals(i))
						break;
				}
				System.out.println(x);
		}
	}
}

OJ Board

10523 - Very Easy !!!

Re: 10523 - Very Easy

Re: 10523 - Very Easy !!!

Re: 10523 - Very Easy !!!

Re: 10523 - Very Easy !!!