## 10268 - 498-bis

Moderator: Board moderators

10153EN
Experienced poster
Posts: 148
Joined: Sun Jan 06, 2002 2:00 am
Location: Hong Kong
Contact:

### 10268 - 498-bis

I would like to ask why there's runtime error in my program on the online judge?

Any traps or tricks on this problem?

wyvmak
Experienced poster
Posts: 110
Joined: Thu Dec 13, 2001 2:00 am
try to allocate big arrays for both the input string and the coefficients

Alam
New poster
Posts: 4
Joined: Fri Apr 26, 2002 8:42 am

### P: 10268 What's the wrong in my code.

What's the wrong in my code? I am getting wrong answer for the code given below. Can any one help me to find out the problem?

/* @begin_of_source_code */

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

void main()
{
char ch;
char *p;
long a,sumf,i,j,x,n;
double sum;

while(gets(ch)!=NULL)
{ x = atol(ch);
gets(ch);
p = strtok(ch," ");
i = 0;
do{
a[i++] = atol(p);
p = strtok(NULL," ");
if(p == NULL)break;
}while(1);
n = i-1;

i=0; sum=0;
do{
if (n== 0) break;
sum += a*n*pow(x,n-1);
n--;
i++;
}while(n!=0);
sumf= (long) sum;
printf("%ld\n",sumf);

}

}
/* @end_of_source_code */

10153EN
Experienced poster
Posts: 148
Joined: Sun Jan 06, 2002 2:00 am
Location: Hong Kong
Contact:

### HI~~

Glancing your program, the 1st thing attach my attention is the variable sum, which is of data type double.

Will there be precision error when casting the variable from

Code: Select all

``double``
to

Code: Select all

``long``
?[/code]

Alam
New poster
Posts: 4
Joined: Fri Apr 26, 2002 8:42 am
I think that's not the problem. Sum is less than 2^31.

I used double here to store intermediate vlaue of sum which may be more than 2^31.

To check, I also send my program by changing the last two lines in this way

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

Can any one help me by giving some critical sample input ouput?

10153EN
Experienced poster
Posts: 148
Joined: Sun Jan 06, 2002 2:00 am
Location: Hong Kong
Contact:
Oh, sorry~

However, to me, precision problem is one of the problem that has puzzled me for wrong answer~~

So I have solved this problem without using double data type =P

Stefan Pochmann
A great helper
Posts: 284
Joined: Thu Feb 28, 2002 2:00 am
Location: Germany
Contact:
I know what the bug is, I have learned so much with this problem. Your mistake is that you mix long-calculation and double-calculation. "a*n" might result in overflow and will be cut, but then you work with double values that don't cut.

The key here is to not think. That's right, don't think. Don't worry about overflow at all, just use normal "int" or "long" values. That works because the result is guaranteed to fit into an int. Now if you have heard about the Chinese Remainder Theorem, this might sound familiar: If you work modulo some number, then you can read the result in the end correctly, if the value is in a certain small range. (That's a very unprecise statement, but it includes the key message.)

Since you need only use +, - and * here, doing everything in modulo works fine. Even better, the standard int operations are already done modulo 2^32 for you for free!

So my advice: don't use double here, use int everywhere. Let us know what happens.

hongping
New poster
Posts: 11
Joined: Fri Jul 26, 2002 5:43 pm
Hi, I dont know what's wrong with my code. I keep getting time limit exceeded. I am using purely integers.

[cpp]

#include <iostream>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <ctype.h>

using namespace std;
int x,a;
int xp,n;

void process(){
int i,c,sum,v;
xp=1; //xp = x^i
for (i=1;i<=n;i++){
xp=xp[i-1]*x;
}
sum=0;
c=n-1;
for (i=0;i<n-1;i++,c--){
v = xp[c-1] * a * (c);
sum+=v;
}
cout << sum << endl;
}
void main(){
char s,s2;int p;
while (gets(s)){
x=atol(s);
gets(s);
strcat(s,"~");
n=0;p=0;
int i=0;
while((s!='-')&&!isdigit(s)&&i<strlen(s))
i++;
for (;i<strlen(s);i++){
if (s==' ' || s=='~'){
s2[p]=0;
a[n++]=atol(s2);
p=0;
while((s!='-')&&!isdigit(s)&&i<strlen(s))
i++;
i--;
}else
s2[p++]=s;
}
process();
}

}

[/cpp]

ras46
New poster
Posts: 5
Joined: Mon Nov 05, 2001 2:00 am
Location: Taiwan
Contact:

### 10268

[c]

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define SIZE 1000000

unsigned long split(char *a,unsigned long *b)
{
char *c;
unsigned long i = 0,value;

c = strtok(a," ");

while( c != NULL )
{
value = atoi(c);
b[i++] = value;
c = strtok(NULL," ");
}

return i;
}

int main()
{
unsigned long x,n,i,value;
unsigned long coef[SIZE];
char input[SIZE];

while( scanf("%lu",&x) == 1 )
{
gets(input);
n = split(input,coef) - 1;
value = coef * n;

for( i = 1 ; i < n ; i++ )
value = value*x + coef*(n-i) ;

printf("%lu\n",value);
}

return 0;
}
[/c]

I got many WAs.
Can somebody tell me what's wrong with my code?
Thanks!

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong
I've taken all the advices provided on the board, however, still WA...

Any help??!! Plz...

Or is that input problem? Does the input contain trailing spaces???!!

[pascal]-- cut --

No, there aren''t any trailing spaces in the input.[/pascal]
Last edited by Observer on Mon Jul 21, 2003 2:32 pm, edited 2 times in total.
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong
Finally got an ACC... Thx for your attention... [pascal]-- cut --[/pascal]
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

Revenger
Experienced poster
Posts: 132
Joined: Sun Apr 14, 2002 12:27 pm
Location: Russia

### Help me

I try everything, but I get WA

My code

[pascal]Program p10268; {\$n+}

Var X, Ans : Extended;
XPow : Extended;
A : Array[0..1000000]of Extended;
N, i : Integer;

Function ReadInteger(Var I : Extended) : Boolean;
Var Ch : Char;
Cnt : Integer;
begin
I := 0;
Cnt := 0;
While Not (Eoln or Eof) do begin
if Ch in ['0'..'9'] then begin
I := I * 10 + Ord(Ch) - Ord('0');
Cnt := Cnt + 1;
end else
if Cnt > 0 then Break;
end;
end;

begin
While Not Eof do begin
N := 0;
While ReadInteger(A[N]) do N := N + 1;
N := N - 1;
Ans := 0;
XPow := 1;
for i := N - 1 downto 0 do begin
Ans := Ans + A * (N - i) * XPow;
if Abs(X) < 1e-5 then Break;
XPow := XPow * X;
end;
Writeln(Ans:0:0);
end;
end.[/pascal]

little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm
There is no need to use floating-point types and you don't have to use your home brew input parser.

Here's my i/o framework:[pascal]
var
num:array[..] of integer;
begin
while not eof do begin
if eoln then begin readln; continue; end;
nums:=0;
while not eoln do begin
inc(nums);
end;

end;
end.[/pascal]
All with the standard S32 integer type.

Revenger
Experienced poster
Posts: 132
Joined: Sun Apr 14, 2002 12:27 pm
Location: Russia

### I get AC!!!

Thanks!

I get AC jai166
New poster
Posts: 10
Joined: Mon May 12, 2003 11:10 am

### 10268 - 498'

I've submited it many times, but it always says "Time Limit Exceeded"!
[c]/* 10268 */
#include<stdio.h>
#define MAX 1000000
#define MAX2 500000
unsigned int c2i(char c[],int in[]);
long double count(int x,int c[],unsigned int allc);
int pow(int x,unsigned int t);
void main(void)
{
char input[MAX];
unsigned int allc,i,j;
int c[MAX2],x;

while( scanf("%d\n",&x) ){
gets(input);
allc=c2i(input,c);

printf("%.0Lf\n",count(x,c,allc) );
}
}
unsigned int c2i(char input[],int in[])
{
unsigned int i=0,j=0;
int sum;

for(;input; )
if(input!='-'){ /*input>0*/
for(sum=0; input!=' '&&input!=0 ;i++){
sum*=10;
sum+=input-48;
}
in[j++]=sum;
if(input)i++;
}else{/* input<0 */
for(i++,sum=0; input!=' '&&input!=0 ;i++){
sum*=10;
sum+=input-48;
}
in[j++]=0-sum;
if(input)i++;
}
return j;
}
long double count(int x,int c[],unsigned int allc)
{
long double sum=0;
unsigned int i;

for(i=0;i<allc-1;i++)
sum+=(long double)(c[i]*(allc-i-1)*pow(x,allc-i-1-1));

return sum;
}
int pow(int x,unsigned int t)
{
int sum=1;
for(;t;t--)
sum*=x;
return sum;
}[/c]