10268 - 498-bis

[10153EN]

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]

try to allocate big arrays for both the input string and the coefficients

[Alam]

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[1000000];
char *p;
long a[1000000],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]

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]

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);

But got Wrong Answer.

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

NB: I'm a little bit frastreted about this problem since i correctly solved the problem 498.

[10153EN]

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]

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]

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[1000000];
int xp[100000],n;


void process(){
int i,c,sum,v;
xp[0]=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[1000000],s2[1000000];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]

[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[0] * 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]

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]

[Observer]

Finally got an ACC... Thx for your attention...

[pascal]-- cut --[/pascal]

[Revenger]

I try everything, but I get WA
Please, help me

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
Read(Ch);
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;
ReadInteger := Cnt > 0;
end;

begin
While Not Eof do begin
Readln(X);
N := 0;
While ReadInteger(A[N]) do N := N + 1;
if Eoln then Readln;
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]

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
x,nums,answer:integer;
num:array[..] of integer;
begin
while not eof do begin
if eoln then begin readln; continue; end;
readln(x);
nums:=0;
while not eoln do begin
inc(nums);
read(num[nums]);
end;
readln;

//calculate answer; spoiler removed

writeln(answer);
end;
end.[/pascal]
All with the standard S32 integer type.

[Revenger]

Thanks!

I get AC

[jai166]

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]