10523 - Very Easy !!!

Moderator: Board moderators

magic_guy
New poster
Posts: 10
Joined: Sat Aug 28, 2004 8:18 am
#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;
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++) {
*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);
continue;
}
multiply_bignum(&n1,&n7,&n3);

}
for(i=1;i<=n;i++)
{
int_to_bignum(i,&tem);

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

}
print_bignum(&n5);

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

roticv
Learning poster
Posts: 63
Joined: Sat Dec 11, 2004 9:28 am
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);
cpy(&total,&tmp4);
}
printbigint(&total);
}
}
return 0;
}
``````

chulin nagasaki
New poster
Posts: 3
Joined: Wed Apr 26, 2006 7:06 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
``````
Sorry for my poor english.

daveon
Experienced poster
Posts: 229
Joined: Tue Aug 31, 2004 2:41 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
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());
}
System.out.println(re);
}
}
}
``````
Very thanks.

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

Re: 10523 - Very Easy

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..

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

Re: 10523 - Very Easy

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

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

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

thank you

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

Re: 10523 - Very Easy

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

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

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

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.....

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

Re: 10523 - Very Easy

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!