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
Moni
Experienced poster
Posts: 202
Joined: Fri Mar 22, 2002 2:00 am
Location: Chittagong. CSE - CUET
Contact:

Post by Moni » Wed Aug 27, 2003 7:29 pm

xbeanx wrote:What's the big deal about changing a problem??

So what if you need to change your program a little. I mean, if you were astute enough to solve it in the first place, then a little modification shouldn't be so bad... Am I right?
--->

Now you know why :-?
ImageWe are all in a circular way, no advances, only moving and moving!

xbeanx
Experienced poster
Posts: 114
Joined: Wed Jul 30, 2003 10:30 pm
Location: Newfoundland, Canada (St. John's)

Post by xbeanx » Wed Aug 27, 2003 8:59 pm

What the heck does --> mean?

And I still do not know why. :-?

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:

Post by Larry » Wed Aug 27, 2003 9:06 pm

So what about the rest of us that doesn't have a bigint class?

User avatar
Pier
New poster
Posts: 38
Joined: Thu Mar 27, 2003 9:12 pm
Location: Aguascalientes, Mexico
Contact:

Post by Pier » Thu Aug 28, 2003 7:24 am

So what if you need to change your program a little. I mean, if you were astute enough to solve it in the first place, then a little modification shouldn't be so bad... Am I right?
My old program got this:
Time: 0:00.000
Memory: 64
Language: PASCAL

I don't think a little modification will work in this case...

So please don't comment such a thread.
And A great programmer usually don't do that.
I'm not a great programmer not even a good one... And I don't think that this has anything to do with it.

But you may agree that we learn more when it is WA or TLE..........!
I agree, but my answer was correct. I think they should have changed the checking system insteed of the problem.





Sorry if anyone felt insulted. I didn't knew that correct answers were getting WA. But still, I don
There are 10 kind of people on this world: those who understand binary and those who don't!

anupam
A great helper
Posts: 405
Joined: Wed Aug 28, 2002 6:45 pm
Contact:

Post by anupam » Thu Aug 28, 2003 8:56 am


>>So what about the rest of us that doesn't have a bigint class?

So, according to you change at least 60 problems that uses BigInt class??

I have sent the changed problem and in out when they are first out in the list
of problemset and when there are total 20 submission for the problem.

But, As they were busy with their server they did it after 900 submission.
So is this the stupidity of the problem??

Why making a comment when you didn't know the total circomm. for a problem?
Don't you see them upgrading the server? goto the page acm.uva.es/p and see the heading

It is more important to upgrade the server than upgrading only
a program?
at least I think. I don't bother whatever you think>?


So, what to tell about a problem in vol 3 when there goes at least 5000 subm?

I got wa mle for at least 22 times and when aggressively i deleted my src(frustation),
I found that all of my submission got ac.
So, what to tell about the problem????
when i got ac after rejudge i wa happy but those who with wrong case got ac
was sad. So Is it better to think about those submission? or those who for
the problem in the problem got wa before though they were correct??


And, if your answer was correct, your method must be correct.
so It needs only a submission to get ac again.
No programmers in this site except you (I think) bother for
just a submission.

And about making a special judge for the problem?

I havn't ever seen there are multiple format of the answer and all getting ac.
Rather there are multiple answer..

I am sorry if i am aggresive, it's my first such post. But even now if you
continue, I advice you to solve other 1199 problems except mine..
--
Anupam
(good words sometimes are unsuccssful)
"Everything should be made simple, but not always simpler"

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:

Post by Larry » Thu Aug 28, 2003 9:07 am

But you may agree that we learn more when it is WA or TLE..........!
Err.. ya, I don't think I've learn anything. Except for the quality of some problems.

User avatar
Moni
Experienced poster
Posts: 202
Joined: Fri Mar 22, 2002 2:00 am
Location: Chittagong. CSE - CUET
Contact:

Post by Moni » Thu Aug 28, 2003 4:15 pm

xbeanx wrote:What the heck does --> mean?

And I still do not know why. :-?
Sorry! I just use the symbol what I always use in my mail.....

Left <---
Right --->

I said you were right!

And the reason of changing is their server config.......:)
ImageWe are all in a circular way, no advances, only moving and moving!

User avatar
Moni
Experienced poster
Posts: 202
Joined: Fri Mar 22, 2002 2:00 am
Location: Chittagong. CSE - CUET
Contact:

Post by Moni » Thu Aug 28, 2003 4:38 pm

Larry wrote:
But you may agree that we learn more when it is WA or TLE..........!
Err.. ya, I don't think I've learn anything. Except for the quality of some problems.


Hey! then don't you have to think again what special cases have been added!
Every WA or TLE forced me to think deeply about it and then I had learnt new algorithm (to tackle WA) or technique (to Defeat TLE)!

It's true that I hadn't got all the things READY-MADE.....I learnt (Still the same way!) by facing obstackles :)
ImageWe are all in a circular way, no advances, only moving and moving!

Per
A great helper
Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden

Post by Per » Thu Aug 28, 2003 7:37 pm

Moni wrote:For the matrix problem pivoting is that factor which made it really challenging............
Yes! So doesn't it seem like a bad idea to remove that part of the problem? :)
Moni wrote:But I have seen before one year, Dmitry solved 718... problems and after one year it was seen 684...(or someting.......) all this happen only for rejudges.......and if this still goes nothing to complain I think!
I think there's a big difference between rejudgements because new input has been added, and rejudgements because the problem has been changed, don't you? I've only been registered here for a year, so I have probably missed something, but the only other problem I'm aware of that has been changed is 197, where there's a Fix apologising for changing the problem.
Larry wrote:So what about the rest of us that doesn't have a bigint class?
Can't give you any other advice than to write one. :)
Seriously, there's a lot of problems requiring bigints, and writing one is good practice. For this problem, you only need addition, multiplication by scalar, and output, so it's a good start! (Even though there are quite a few which just require addition and output)
anupam wrote:But, As they were busy with their server they did it after 900 submission.
I'm sorry, I didn't know that. I was wrong in complaining about that part. As I said in my previous post, I understand why you've changed 10523, but please, can you explain the rationale behind disallowing pivoting on 10524?
anupam wrote:I havn't ever seen there are multiple format of the answer and all getting ac.
Rather there are multiple answer..
Just because it hasn't been done before doesn't mean it's a bad idea! :)
And actually, in problem 415 you are supposed to use default output format and there's a special judge, so it has been done!

User avatar
angga888
Experienced poster
Posts: 143
Joined: Sat Dec 21, 2002 11:41 am
Location: Indonesia

10523 Very Easy - Bignum?

Post by angga888 » Mon Dec 08, 2003 2:12 pm

Hello, I got WA & WA for this problem. :(

I use Bignum to calculate the sum for i*a^i
I also have checked my output on input 150 15, and got the same result as stated in previous post. But still WA...

Are there any tricky or invalid input, or the input n,a could be reversed?

I have some input, please give me the output...

Code: Select all

150 0
150 1
100 0
1 0
1 10
1 15
0 0 -> is this a valid input?
Please someone give me some hints to get rid of this WA.
Thanks before.


Best Regards,
Anggakusuma

User avatar
sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

Post by sohel » Mon Dec 08, 2003 2:56 pm

Hi,

my AC program gives

0
11325
0
0
10
15

as output.
Hope it helps. :wink:

User avatar
angga888
Experienced poster
Posts: 143
Joined: Sat Dec 21, 2002 11:41 am
Location: Indonesia

Post by angga888 » Mon Dec 08, 2003 4:41 pm

Hi Sohel, thanks for your output.
My output is exactly same as yours.
I still wonder why I get WA. :(

Please answer my question below. :)
- What's the maximum & minimum limit for n and a?
- Could n,a be reversed in input?
- Should we handle for something invalid in input?

Here's some more input, please give the output

Code: Select all

0 0
0 150
0 1
51 15
100 5
91 19
And please tell me which input above is invalid...

Thanks very much. :D


Best Regards,
Anggakusuma

User avatar
sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

Post by sohel » Tue Dec 09, 2003 8:33 am

Here are the answers to your questions:
- 1<=N<=150 and 0<=A<=15
- input is given as N and A respectively, ie order cannot be reversed.
- there will be no invalid input.

The first three and the last one is invalid and these will not be there in the judges input. So you do not have to take care of these types.

output for the fourth one is :
52188994475428012744377141543018279541999562548435464197275590

and the fifth one :
983610941197449094872749054836974080123779273776563059072941541671752930

Hope it helps. :wink:

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

10523

Post by magic_guy » Mon Aug 30, 2004 9:08 am

#include <stdio.h>
#include <stdlib.h>
#define MAXDIGITS 100 /* 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 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(i=1;i<=n;i++)
{
int_to_bignum(i,&tem);
add_bignum(&n1,&n2,&n7);
for(j=0;j<i;j++)
{
if(j==0)
{
multiply_bignum(&n1,&n8,&n7);
continue;
}
multiply_bignum(&n1,&n7,&n3);

add_bignum(&n3,&n2,&n7);
}

multiply_bignum(&n7,&tem,&n3);

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

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


}
print_bignum(&n5);


}
return 0;
}


this is my code and got tle.could anyone help :cry:

User avatar
shamim
A great helper
Posts: 498
Joined: Mon Dec 30, 2002 10:10 am
Location: Bozeman, Montana, USA

Post by shamim » Tue Aug 31, 2004 8:26 am

Hi I did not check your code, from what I remember, you have to store the powers in advance and not calculate it every time you take a new set of input. Many people got TLE on this problem because of this. :roll:

Post Reply

Return to “Volume 105 (10500-10599)”