10523 - Very Easy !!!

All about problems in Volume 105. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

User avatar
uDebug
A great helper
Posts: 475
Joined: Tue Jul 24, 2012 4:23 pm

Re: 10523 - Very Easy

Post by uDebug » 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.
Check input and AC output for over 7,500 problems on uDebug!

Find us on Facebook. Follow us on Twitter.

uradura
New poster
Posts: 11
Joined: Thu Jan 01, 2015 10:31 am

Re: 10523 - Very Easy !!!

Post by uradura » Wed Feb 25, 2015 9:12 am

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

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10523 - Very Easy !!!

Post by brianfry713 » Thu Feb 26, 2015 2:14 am

Try precalculating the output for every possible input.
Check input and AC output for thousands of problems on uDebug!

Helaluddin_brur
New poster
Posts: 15
Joined: Tue Oct 21, 2014 4:08 pm
Location: Bangladesh
Contact:

Re: 10523 - Very Easy !!!

Post by Helaluddin_brur » 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);
		}
	}
}

Post Reply

Return to “Volume 105 (10500-10599)”