498 - Polly the Polynomial

[Miranda]

[cpp]
#include <iostream.h>
#include <string>
#include <math.h>

int main() {
string s1,s2;
int i,j1,j2,sign,result;
int c[10000],x[10000];
while(getline(cin,s1)) {
getline(cin,s2);
if(s2==""||(s1==""))
break;
i=0;j1=0;j2=0;
for(int k=0;k<10000;k++) {
c[k]=0;
x[k]=0;
}
sign=1;
s1=s1+' ';
while(i<s1.size()) {
if(s1==' '&&s1[i-1]!=' ') {
c[j1]=sign*c[j1];
j1++;
}
else if(s1!='-'&&s1!=' ')
c[j1]=c[j1]*10+(int)(s1-'0');

else if(s1!=' ') {
i++;
sign=-1;
c[j1]=c[j1]*10+(int)(s1-'0');
}
i++;
}
sign=1;
i=0;
s2=s2+' ';
while(i<s2.size()) {
if(s2==' '&&s2[i-1]!=' ') {
x[j2]=sign*x[j2];
j2++;
}
else if(s2!='-'&&s2!=' ') {
x[j2]=x[j2]*10+(int)(s2-'0');
}
else if(s2[i]!=' ') {
i++;
sign=-1;
x[j2]=x[j2]*10+(int)(s2[i]-'0');
}
i++;
}

for(int n=0;n<j2;n++) {
result=0;
for(int k=0;k<j1;k++) {
result=result+(int)pow(x[n],j1-1-k)*c[k];
}
if(n==0)
cout<<result;
else
cout<<" "<<result;
}
cout<<endl;

}
return 0;
}

[/cpp]

[Miranda]

I don't know why my code got WA,can anyone kindly point out what is wrong here?[/b][/b]

[Kimi]

Hi!

I have solved this problem using integer, not double.

Your output is wrong:
input:
10002 1001 102
3 0 1 0 -1

Output:
93123 102 11105 102 9103

Good Luck!

Are all the test data within the range of int64?

[shamim]

If you are concerned with the range of the numbers, i can assure you the double data type can handle it.

[Carlos]

There was an extra space at the end of the line, sorry. I've removed it so that input is fair now. Anyway I won't rejudge the problem until I make a bigger data set (2-3 days). If your veredicts change, then you'll recieve an email.
By the way...if you ever notice some problem like this one (wrong input or output) tell us at problemset@acm.uva.es and we'll check it.
Carlos.

[dpitts]

Here's my code. It works for all test cases I've thrown at it, but not for judges data.

I'm wondering if its a presentation error that shows up as WA. I've had that happen.
Does it matter if in the output there is a space after the last number?

[c]
/* @JUDGE_ID: xxxxxx 498 C */
char line[1024];
char out[1024];
long long co[1024];
int main(int argc, char *argv[])
{
while (gets(line))
{
char *n = line;
char *o;
long long numCo = 0;
long long neg = 0;
long long c = 0;
while (isspace(*n))
n++;
while (*n)
{
neg = 0;
if (*n == '-')
{
neg = 1;
n++;
}
c = 0;
while (isdigit(*n))
c = c * 10 + *n++ - '0';
while (isspace(*n))
n++;
if (neg)
co[numCo++] = -c;
else
co[numCo++] = c;
}
gets(line);
n = line;
o = out;
neg = 0;
while (isspace(*n))
n++;
while (*n)
{
long long x;
long long i;
long long acc;
char *a, *b;
neg = 0;
if (*n == '-')
{
neg = 1;
n++;
}
c = 0;
while (isdigit(*n))
c = c * 10 + *n++ - '0';
while (isspace(*n))
n++;
if (neg)
c = -c;
acc = 0;
for (x = 1, i = numCo-1; i >= 0; i--, x*=c)
acc += x*co;
if (acc < 0)
{
*o++ = '-';
acc = -acc;
}
a = o;
while (acc)
{
*o++ = (acc % 10) + '0';
acc /= 10;
}
b = o;
while (a < b--)
{
char tmp = *a;
*a = *b;
*b = tmp;
a++;
}
*o++ = ' ';
}
*o = 0;
puts(out);
}
return 0;
}
[/c]
p.s. I know this is ugly code. I'm going for speed, not ease. If I wanted ease, I'd be using C++.

Any cases this doesn't work with?

[dpitts]

Hmm, my C++ version works. its a lot slower though.

Still, the algo is the same, why am I getting WA for the C version?

[_.B._]

input:
10002 1001 102
3 0 1 0 -1

Output:
93123 102 11105 102 9103

Good Luck!

Thanks!
Had a mistake, now ACed
Keep posting!

[wolf]

Hi !
I've a little problem with that code (fragment of my ACM-498 code):

[cpp]
#include <stdio.h>

char cline[1000],xline[1000];
int i,j,a,c[100],x[100];

int main()
{
for (;;)
{
if (gets(cline)==NULL) break;
gets(xline);
for (i=0;;i++)
{
if (sscanf(cline,"%d",&c)==EOF) break;
}
for (j=0;;j++)
{
if (sscanf(xline,"%d",&x[j])==EOF) break;
}
for (a=0;a<i;a++) printf("%d ",c);
for (a=0;a<j;a++) printf("%d ",x[j]);
}
return 0;
}
[/cpp]

If I compile & run this, my program never ends... I thing it casused by sscanf() function, but how sjould I use it correctly ?

[Dominik Michniewski]

Yes, you have right. This piece of code should always work in infinite loop in first loop
Why?
sscanf() don't know, that it should read not from beginning of the buffer, but a few characters after beggining You must give to sscanf() function buffer in right place for reading. You could use i.e. strtok() function

Bets regards
DM

PS. sscanf() is a bit different from scanf(). scanf() reads from stdin, and readed characters are "forgotten". sscanf() always gets the same buffer (in your case) so infinity loop is only one possibility

[wolf]

Thanx Dominik !
I never used sscanf() before, so it was easy for me to make this stupid mistake...
Now I know how can I solve this problem in different way, but You mentioned about the strtok() function. Could you explain me how can I use it in above sample code, I don't know anything about this function too

[Dominik Michniewski]

strtok() function gives in first run buffer to tokenization and list of separators of tokens (like spaces, tabs, line feeds and so on, but it could be any character in fact). Next runs of function you do using NULL as buffer - strtok() remembers this first buffer and in each run gives you pointer to next token in buffer. For example

Code: Select all

char buffer[] = "abc 1 120-nuib 123_",*token;
token = strtok(buffer," \n\r\t");
while(token)
{
    // do something with token
    token = strtok(NULL," \n\r\t");
}

In while loop you take strings "abc", "1", "120-nuib" and "123_".
I write code by hand, so it could be uncompilable, but idea is clear I think

Best regards
DM

[wolf]

Thanx a lot ! Now it's clear for me

[nukeu666]

my code is working fine for all inputs given on the thread...using long and long long just to be sure also
yet og gives me a wrong answer
help!

Code: Select all

yay

[mamun]

What is the following line in main() doing

Code: Select all

if(sum!=0)

Remove it.