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

magic_guy
New poster
Posts: 10
Joined: Sat Aug 28, 2004 8:18 am

Post by magic_guy » Tue Aug 31, 2004 12:12 pm

#include <stdio.h>
#include <stdlib.h>
#define MAXDIGITS 1000 /* maximum length bignum */

#define PLUS 1 /* positive sign bit */
#define MINUS -1 /* negative sign bit */

typedef struct {
char digits[MAXDIGITS]; /* represent the number */
int signbit; /* 1 if positive, -1 if negative */
int lastdigit; /* index of high-order digit */
} bignum;

void print_bignum(bignum *n);
void int_to_bignum(int s, bignum *n);
void initialize_bignum(bignum *n);
int max(int a, int b);
void add_bignum(bignum *a, bignum *b, bignum *c);
void subtract_bignum(bignum *a, bignum *b, bignum *c);
int compare_bignum(bignum *a, bignum *b);
void zero_justify(bignum *n);
void digit_shift(bignum *n, int d); /* multiply n by 10^d */
void multiply_bignum(bignum *a, bignum *b, bignum *c);
void divide_bignum(bignum *a, bignum *b, bignum *c);



void print_bignum(bignum *n)
{
int i;

if (n->signbit == MINUS) printf("- ");
for (i=n->lastdigit; i>=0; i--)
printf("%c",'0'+ n->digits);

printf("\n");
}


void int_to_bignum(int s, bignum *n)
{
int i; /* counter */
int t; /* int to work with */

if (s >= 0) n->signbit = PLUS;
else n->signbit = MINUS;

for (i=0; i<MAXDIGITS; i++) n->digits = (char) 0;

n->lastdigit = -1;

t = abs(s);

while (t > 0) {
n->lastdigit ++;
n->digits[ n->lastdigit ] = (t % 10);
t = t / 10;
}

if (s == 0) n->lastdigit = 0;
}

void initialize_bignum(bignum *n)
{
int_to_bignum(0,n);
}


int max(int a, int b)
{
if (a > b)
return(a);
else
return(b);
}



void add_bignum(bignum *a, bignum *b, bignum *c)
{
int carry; /* carry digit */
int i; /* counter */

initialize_bignum(c);

if (a->signbit == b->signbit) c->signbit = a->signbit;
else {
if (a->signbit == MINUS) {
a->signbit = PLUS;
subtract_bignum(b,a,c);
a->signbit = MINUS;
} else {
b->signbit = PLUS;
subtract_bignum(a,b,c);
b->signbit = MINUS;
}
return;
}

c->lastdigit = max(a->lastdigit,b->lastdigit)+1;
carry = 0;

for (i=0; i<=(c->lastdigit); i++) {
c->digits = (char) (carry+a->digits+b->digits) % 10;
carry = (carry + a->digits + b->digits) / 10;
}

zero_justify(c);
}


void subtract_bignum(bignum *a, bignum *b, bignum *c)
{
int borrow; /* has anything been borrowed? */
int v; /* placeholder digit */
int i; /* counter */

if ((a->signbit == MINUS) || (b->signbit == MINUS)) {
b->signbit = -1 * b->signbit;
add_bignum(a,b,c);
b->signbit = -1 * b->signbit;
return;
}

if (compare_bignum(a,b) == PLUS) {
subtract_bignum(b,a,c);
c->signbit = MINUS;
return;
}

c->lastdigit = max(a->lastdigit,b->lastdigit);
borrow = 0;

for (i=0; i<=(c->lastdigit); i++) {
v = (a->digits - borrow - b->digits);
if (a->digits > 0)
borrow = 0;
if (v < 0) {
v = v + 10;
borrow = 1;
}

c->digits[i] = (char) v % 10;
}

zero_justify(c);
}

int compare_bignum(bignum *a, bignum *b)
{
int i; /* counter */

if ((a->signbit == MINUS) && (b->signbit == PLUS)) return(PLUS);
if ((a->signbit == PLUS) && (b->signbit == MINUS)) return(MINUS);

if (b->lastdigit > a->lastdigit) return (PLUS * a->signbit);
if (a->lastdigit > b->lastdigit) return (MINUS * a->signbit);

for (i = a->lastdigit; i>=0; i--) {
if (a->digits[i] > b->digits[i]) return(MINUS * a->signbit);
if (b->digits[i] > a->digits[i]) return(PLUS * a->signbit);
}

return(0);
}

void zero_justify(bignum *n)
{
while ((n->lastdigit > 0) && (n->digits[ n->lastdigit ] == 0))
n->lastdigit --;

if ((n->lastdigit == 0) && (n->digits[0] == 0))
n->signbit = PLUS; /* hack to avoid -0 */
}


void digit_shift(bignum *n, int d) /* multiply n by 10^d */
{
int i; /* counter */

if ((n->lastdigit == 0) && (n->digits[0] == 0)) return;

for (i=n->lastdigit; i>=0; i--)
n->digits[i+d] = n->digits[i];

for (i=0; i<d; i++) n->digits[i] = 0;

n->lastdigit = n->lastdigit + d;
}



void multiply_bignum(bignum *a, bignum *b, bignum *c)
{
bignum row; /* represent shifted row */
bignum tmp; /* placeholder bignum */
int i,j; /* counters */

initialize_bignum(c);

row = *a;

for (i=0; i<=b->lastdigit; i++) {
for (j=1; j<=b->digits[i]; j++) {
add_bignum(c,&row,&tmp);
*c = tmp;
}
digit_shift(&row,1);
}

c->signbit = a->signbit * b->signbit;

zero_justify(c);
}


void divide_bignum(bignum *a, bignum *b, bignum *c)
{
bignum row; /* represent shifted row */
bignum tmp; /* placeholder bignum */
int asign, bsign; /* temporary signs */
int i; /* counters */

initialize_bignum(c);

c->signbit = a->signbit * b->signbit;

asign = a->signbit;
bsign = b->signbit;

a->signbit = PLUS;
b->signbit = PLUS;

initialize_bignum(&row);
initialize_bignum(&tmp);

c->lastdigit = a->lastdigit;

for (i=a->lastdigit; i>=0; i--) {
digit_shift(&row,1);
row.digits[0] = a->digits[i];
c->digits[i] = 0;
while (compare_bignum(&row,b) != PLUS) {
c->digits[i] ++;
subtract_bignum(&row,b,&tmp);
row = tmp;
}
}

zero_justify(c);

a->signbit = asign;
b->signbit = bsign;
}



int main()
{
int a,b,n,i,j;
bignum c[150],n1,n2,n3,n4,n5,n6,n7,n8,zero,tem;

while (scanf("%d%d",&n,&a) != EOF)
{

int_to_bignum(a,&n1);
int_to_bignum(0,&n2);
int_to_bignum(0,&n4);
int_to_bignum(1,&n8);
for(j=0;j<n;j++)
{
if(j==0)
{
multiply_bignum(&n1,&n8,&n7);
add_bignum(&n7,&n2,&c[j]);
continue;
}
multiply_bignum(&n1,&n7,&n3);

add_bignum(&n3,&n2,&n7);
add_bignum(&n3,&n2,&c[j]);
}
for(i=1;i<=n;i++)
{
int_to_bignum(i,&tem);


multiply_bignum(&c[i-1],&tem,&n3);

add_bignum(&n3,&n4,&n5);

add_bignum(&n5,&n2,&n4);


}
print_bignum(&n5);

/* add_bignum(&n1,&n2,&n3);
printf("addition -- ");
print_bignum(&n3);

printf("compare_bignum a ? b = %d\n",compare_bignum(&n1, &n2));

subtract_bignum(&n1,&n2,&n3);
printf("subtraction -- ");
print_bignum(&n3);

multiply_bignum(&n1,&n2,&n3);
printf("multiplication -- ");
print_bignum(&n3);

int_to_bignum(0,&zero);
if (compare_bignum(&zero, &n2) == 0)
printf("division -- NaN \n");
else {
divide_bignum(&n1,&n2,&n3);
printf("division -- ");
print_bignum(&n3);
}
printf("--------------------------\n"); */
}
return 0;
}


yes ,i alted it,but still tle :cry:

roticv
Learning poster
Posts: 63
Joined: Sat Dec 11, 2004 9:28 am

Post by roticv » Sun Jul 24, 2005 2:54 pm

It is weird. I have tried your sample code and the one in the other thread and they all work out fine. I am quite puzzled over what's wrong with my code

Code: Select all

#include <stdio.h>

typedef struct{
char data[2000];
int size;
}bigint;

int A,n,i;
bigint tmp,tmp2,tmp3,tmp4,x,total;

int inttobigint(bigint *a, int b){
	int ii = 0;
	while (b!=0){
		a->data[ii] = b % 10;
		ii++;
		a->size = ii;
		b /= 10;
	}
	return 0;
}

int add(bigint *a, bigint *b, bigint *c){
	int max,ij,carry;
	if (b->size > c->size){
		max = b->size;
	}else
		max = c->size;
	a->size = max;
	carry = 0;
	for (ij=0;ij<max;ij++){
		a->data[ij] = b->data[ij] + c->data[ij] + carry;
		carry = a->data[ij] / 10;
		a->data[ij] %= 10;
	}
	if (carry!=0){
		a->data[ij] = carry;
		a->size++;
	}
	return 0;
}

int mul(bigint *a, bigint *b, bigint *c){
	int ij, ik, carry;
	a->size = b->size + c->size;
	for (ij=0;ij< a->size;ij++)
		a->data[ij] = 0;
	for (ij=0; ij<b->size; ij++){
		carry = 0;
		for (ik=0;ik<c->size; ik++){
			a->data[ij+ik] += b->data[ij] * c->data[ik] + carry;
			carry = a->data[ij+ik] / 10;
			a->data[ij+ik] %= 10;
		}
		if (carry!=0){
			a->data[ij+ik] +=carry;
		}
	}
	if (carry==0)
		a->size--;
	return 0;
}

int cpy(bigint *a, bigint *b){
/*a = b*/
	int ii;
	a->size = b->size;
	for (ii = 0; ii < a->size; ii++)
		a->data[ii] = b->data[ii];
	a->data[ii] = 0;
	return 0;
}

int printbigint(bigint *a){
	int ii;
	for (ii=a->size-1;ii>=0;ii--)
		printf("%c",a->data[ii]+'0');
	printf("\n");
	return 0;
}


int main(){
	while (scanf("%d %d ",&n,&A)!=EOF){
		if (n == 0)
			continue;
		if (A == 0)
			printf("0\n");
		else{
			inttobigint(&tmp,A);
			cpy(&tmp2,&tmp);
			cpy(&total,&tmp);
			for (i=2;i<=n;i++){
				mul(&tmp3,&tmp2,&tmp);
				cpy(&tmp,&tmp3);
				inttobigint(&x,i);
				mul(&tmp3,&tmp,&x);
				add(&tmp4,&total,&tmp3);
				cpy(&total,&tmp4);
			}
			printbigint(&total);
		}
	}
	return 0;
}

chulin nagasaki
New poster
Posts: 3
Joined: Wed Apr 26, 2006 7:06 pm

10523-WA PLEASE Which the correct answer for this test case?

Post by chulin nagasaki » Mon Jun 26, 2006 6:42 pm

It is strange because I used DP to calculate the results, and the answers are the same to the of previous topics. Could then anybody give the answer of that test case?

Code: Select all

100 10
150 15
150 1
130 0
150 14
141 9
13 13
Here it is my output

Code: Select all

1109876543209876543209876543209876543209876543209876543209876543209876543209876543209876543209876543210
51787403232223345349635010389299002259960232581476262727150318907931905663430528663635948915107719470616040777133044802997786319050144083896950248813058952729726526447769207424614
11325
0
593151987840605119165842702766440153673753119083430901020617296547411275424436093048645085587090382275252449167914137344833288398590286484212772267239171682713616442934740431
55999001388452553296039825273368938808880393936449338855913589147969692271625585648996366187167541803212453149361952594430344666172039539
4238148192940207
Thnaks for advantage!
Sorry for my poor english.

daveon
Experienced poster
Posts: 229
Joined: Tue Aug 31, 2004 2:41 am
Location: TORONTO, CANADA

Post by daveon » Tue Jun 27, 2006 3:38 am

Hi,

Here are my outputs:

Code: Select all

1109876543209876543209876543209876543209876543209876543209876543209876543209876543209876543209876543210
41642470296774462562792725985031884205969838044105091368779920844033177704061607491770151984953636682503436650913970981305172726267418523206995220099298301053694354332223230478715
11325
0
1340474392446163172861719327622772124846820958938823384437314197619442525722830907855805468403906344245721147456927160201090343809113573763510446672072485619115060487891513950
55999001388452553296039825273368938808880393936449338855913589147969692271625585648996366187167541803212453149361952594430344666172039539
4238148192940207

Saul Hidalgo
New poster
Posts: 18
Joined: Wed Jan 03, 2007 2:36 am
Location: Los Teques, Venezuela

Post by Saul Hidalgo » Wed Mar 05, 2008 5:55 am

Hi. I'm got RE, but i can't find the error. :-? :-? . Please, Here is my code.

Code: Select all

import java.util.Scanner;
import java.math.BigInteger;
import java.io.*;
class pp {

	public static void main (String[] args) {
		Scanner sc = new Scanner(System.in);
		//while(sc.hasNext()){
		while(sc.hasNext()){
			BigInteger n=sc.nextBigInteger();
			BigInteger b=sc.nextBigInteger();
			BigInteger temp=new BigInteger("0");
			BigInteger re= new BigInteger("0");
			BigInteger i=new BigInteger("0");
			for (i=new BigInteger("1") ; i.compareTo(n)<=0 ; i=i.add(BigInteger.ONE)){
				temp=b.pow(i.intValue());
				re=re.add(temp.multiply(i));
			}
			System.out.println(re);
		}
	}
}
Very thanks.

pok
New poster
Posts: 25
Joined: Sun Nov 09, 2008 11:04 pm

Re: 10523 - Very Easy

Post by pok » Sat Nov 29, 2008 1:57 am

why wrong ans ??

#include<stdio.h>
#include<math.h>

int main()
{
long long double n,a;

while(scanf("%lLf %lLf",&n,&a)==2)
{
long long double i,sum=0;

for(i=1;i<=n;i++)
sum=sum+(i*pow(a,i));

printf("%.0lLf\n",sum);
}

return 0;
}

pls help me..

Jehad Uddin
Learning poster
Posts: 74
Joined: Fri May 08, 2009 5:16 pm

Re: 10523 - Very Easy

Post by Jehad Uddin » Wed Jun 17, 2009 2:12 pm

Its a big integer problem and u have to use DP..

pollob_28
New poster
Posts: 3
Joined: Thu Apr 19, 2012 6:45 pm

Error in 10523

Post by pollob_28 » Thu Apr 19, 2012 6:52 pm

can any one help me ?
why the following compilation error is shown ?

Main.java:5: class MAINN is public, should be declared in a file named MAINN.java
public class MAINN {
^
1 error

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

Re: Error in 10523

Post by brianfry713 » Thu Apr 19, 2012 10:51 pm

Check input and AC output for thousands of problems on uDebug!

pollob_28
New poster
Posts: 3
Joined: Thu Apr 19, 2012 6:45 pm

Re: Error in 10523

Post by pollob_28 » Wed Apr 25, 2012 5:04 pm

thank you

renatov
New poster
Posts: 20
Joined: Fri Sep 21, 2012 6:33 am

Re: 10523 - Very Easy

Post by renatov » Fri Oct 05, 2012 8:13 pm

Does it work if I use "double" as variable types? I don't know how to use this BigNum thing yet, I'm still learning C and I just want to practice.

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

Re: 10523 - Very Easy

Post by brianfry713 » Sun Oct 07, 2012 7:26 pm

It probably won't be precise enough using double.
Check input and AC output for thousands of problems on uDebug!

renatov
New poster
Posts: 20
Joined: Fri Sep 21, 2012 6:33 am

Re: 10523 - Very Easy

Post by renatov » Mon Oct 08, 2012 2:28 am

brianfry713 wrote:It probably won't be precise enough using double.
Yeah, that's exaclty the case. I tested with the values on "Algorithmist" wiki and using 'double' as variable type it will not be precisely enough.

raj
Learning poster
Posts: 78
Joined: Fri Feb 15, 2013 5:39 pm

Re: 10523 - Very Easy

Post by raj » Sat Sep 14, 2013 10:50 pm

Message to those who are trouble in this problem
You dont have to use DP here!!!
There is straightforward summation formula for this problem(book coreman summation chapter) for A != 1
and if A = 1 then the formula will be (N(N+1)/2) ...
I suggest to use java BigInteger.....

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 2:26 pm

Here's some input / output that I found useful during testing / debugging.

Input:

Code: Select all

1 1
125 1
1 15
150 15
45 10
   100 9
        143         14
Output:

Code: Select all

1
7875
15
41642470296774462562792725985031884205969838044105091368779920844033177704061607491770151984953636682503436650913970981305172726267418523206995220099298301053694354332223230478715
49876543209876543209876543209876543209876543210
29844221781350241661174632605613926508265902469227497196143258591653345344863499967384693294147050
12122610255039445891626303831727930473622879834944721844446420379461937478470399702465425566505701636325424310331973096676008648962210093398454071995503086406962573918
Check input and AC output for over 7,500 problems on uDebug!

Find us on Facebook. Follow us on Twitter.

Post Reply

Return to “Volume 105 (10500-10599)”