10268 - 498-bis

All about problems in Volume 102. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

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

10268 - 498-bis

Post by 10153EN » Tue Apr 23, 2002 8:36 pm

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

Post by wyvmak » Mon Apr 29, 2002 1:56 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.

Post by Alam » Wed May 15, 2002 5:43 pm

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
Experienced poster
Posts: 148
Joined: Sun Jan 06, 2002 2:00 am
Location: Hong Kong
Contact:

HI~~

Post by 10153EN » Wed May 15, 2002 6:17 pm

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

Post by Alam » Fri May 17, 2002 4:28 pm

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
Experienced poster
Posts: 148
Joined: Sun Jan 06, 2002 2:00 am
Location: Hong Kong
Contact:

Post by 10153EN » Fri May 17, 2002 4:45 pm

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:

Post by Stefan Pochmann » Sat May 18, 2002 7:12 am

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

Post by hongping » Mon Sep 23, 2002 1:30 am

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
New poster
Posts: 5
Joined: Mon Nov 05, 2001 2:00 am
Location: Taiwan
Contact:

10268

Post by ras46 » Tue Dec 17, 2002 12:41 pm

[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
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong

Post by Observer » Mon Jul 21, 2003 12:46 pm

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

Post by Observer » Mon Jul 21, 2003 1:02 pm

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

[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

Post by Revenger » Fri Aug 08, 2003 11:40 am

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]

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey » Fri Aug 08, 2003 12:13 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
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
Experienced poster
Posts: 132
Joined: Sun Apr 14, 2002 12:27 pm
Location: Russia

I get AC!!!

Post by Revenger » Fri Aug 08, 2003 2:34 pm

Thanks!

I get AC :)

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

10268 - 498'

Post by jai166 » Fri Aug 15, 2003 10:30 am

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]

Post Reply

Return to “Volume 102 (10200-10299)”