10719 - Quotient Polynomial

Moussa · Post by **Moussa** » Tue Nov 29, 2005 12:34 am

i got a wrong answer 4 that code and i tried all the cases in the forum and all worked

and still get WA
im feeling that the error is not in the algo i use but in the output format and i tried every thing and nothing worked
can any one help
i appreciate ur kindly effort

Code: Select all

#include<iostream>
#include<string>
#include<strstream>
using namespace std;
char* str;
string temp;
int arr[10005];
void main()
{
	int k,n,num,m,count;
	string s;
	while(!cin.eof())
	{
		cin>>k;
		num = count = 0;
		getline(cin,temp);
		getline(cin,s);
		str = new char[s.length()+1];
		strcpy(str,s.c_str());
		strstream sstr(str,s.length()+1);
		string news = "";
		while(sstr>>n)
		{
			m = n-num;
			arr[count] = m;
			num = m*-k;
			count++;
		}
		cout<<"q(x): ";
		for(int i=0;i<count-1;i++)
		{
			cout<<arr[i];
			if(i != count-2)
				cout<<" ";
		}
		cout<<endl<<"r = "<<arr[count-1]<<endl<<endl;
	}
}

Rocky · Post by **Rocky** » Tue Nov 29, 2005 8:01 am

i not debug your code but if you need some test data then i can post you..

GOOD LUCK
Rocky

mamun · Post by **mamun** » Tue Nov 29, 2005 9:11 pm

I also haven't debugged your code but your input processing is faulty. Change the following portion

Code: Select all

while(!cin.eof()) 
{ 
   cin>>k;
   num = count = 0;
   ...

to

Code: Select all

while(cin>>k) 
{ 
  num = count = 0;
   ...

And also using cin>> and getline() at the same time is risky.

Martin Macko · Post by **Martin Macko** » Sat Dec 10, 2005 10:58 pm

Moussa wrote:i got a wrong answer 4 that code and i tried all the cases in the forum and all worked and still get WA
im feeling that the error is not in the algo i use but in the output format and i tried every thing and nothing worked
can any one help
i appreciate ur kindly effort

Your solution doesn't work even for the example from the problem statement. It returns:

Code: Select all

q(x): 
r = 0

q(x): 
r = 0

Karthekeyan · Post by **Karthekeyan** » Thu Jan 12, 2006 10:00 am

How can I get a compile error from the OJ for this code??!!
It's working fine in my comp!! Could someone lend me a hand?

Code: Select all

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
long int valdec(vector<char> no)
{
	long int res;
	int n=no.size();
	if(no[0]=='-')
	{
		res=0;
		long int power=1;
		for(int i=n-1;i>=1;i--)
		{
			res+=(no[i]-'0')*power;
			power*=10;
		}
		res*=-1;
	}
	else if(isdigit(no[0]))
	{
		res=0;
		long int power=1;
		for(int i=n-1;i>=0;i--)
		{
			res+=(no[i]-'0')*power;
			power*=10;
		}
	}
	return res;
}
main()
{
	long int k;
	while(cin>>k)
	{
		char ch;
		cin.get(ch);
		vector<char> no;
		vector<long int> a;
		while(cin.get(ch))
		{
			if(ch==' ')
			{
				a.push_back(valdec(no));
				no.clear();
				continue;
			}
			else if(ch=='\n')
			{
				a.push_back(valdec(no));
				no.clear();
				break;
			}
			else 
				no.push_back(ch);
		}

		vector<long int> q(a.size()-1);
		long int r;
		int n=a.size()-1;
		cout<<"q(x): ";
		q[0]=a[0];
		cout<<q[0]<<" ";
		for(int i=1;i<n;i++)
		{
			q[i]=q[i-1]*k+a[i];
			cout<<q[i]<<" ";
		}
		cout<<endl;
		r=a[n]+k*q[n-1];
		cout<<"r = "<<r<<endl;
		cout<<endl;
	}
}

Karthekeyan · Post by **Karthekeyan** » Thu Jan 12, 2006 10:13 am

I found the reason!!
isdigit was the problem....i removed it and i got PE now!! So, how to remove the PE??

Martin Macko · Post by **Martin Macko** » Sun May 21, 2006 2:59 am

Karthekeyan wrote:I found the reason!!
isdigit was the problem....i removed it and i got PE now!! So, how to remove the PE??

You write trailing spaces. Check this:

Karthekeyan wrote:
code wrote:......cout<<q[0]<<" ";
......for(int i=1;i<n;i++)
......{
.........q[i]=q[i-1]*k+a[i];
.........cout<<q[i]<<" ";
......}

Moussa · Post by **Moussa** » Wed Nov 22, 2006 10:33 pm

i don't know what to say

today by accident i saw my post on that problem, and i tried to solve it

and its still wrong answer i changed the cin.eof() to cin>> and it worked in all the cases and still WA

Martin said:
Your solution doesn't work even for the example from the problem statement. It returns:Code:
q(x):
r = 0

q(x):
r = 0

i think you copied and pasted the test case in the problem statement, when you do that the clipboard don't recognize it as a 45(-) but recognizes it as -106(-)

hope you kindly help me get AC

Moussa · Post by **Moussa** » Wed Nov 22, 2006 10:37 pm

Rocky wrote: i not debug your code but if you need some test data then i can post you..

GOOD LUCK

that would be very good

legnaleurc · Post by **legnaleurc** » Sat May 05, 2007 11:30 am

I got it.
Use "while(cin >> k)" instead of "while(!cin.eof())", and I got AC.
Thanks.

Jan · Post by **Jan** » Sat May 05, 2007 8:21 pm

Check mamun's post.

rongtuli · Post by **rongtuli** » Thu Oct 04, 2007 2:56 am

hi,
i m getting WA and can't figure out my error . can anyone give me some test case.
-tulip

nayimsust · Post by **nayimsust** » Mon Mar 08, 2010 7:43 am

i got ac now i used pow function for interger variable

amishera · Post by **amishera** » Mon May 10, 2010 11:02 pm

This is the code:

Code: Select all

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

#define MAX_DEGREE 20000
#define MAX_LEN 200000

char input[MAX_LEN];

int main()
{
	int i;
	long a[MAX_DEGREE];
	int k;
	int degree;
	long r;
	int j;
	long q[MAX_DEGREE];
	long t;
	char* p;
	int n;
	char word[100];
	int first = 1;

//	freopen("in5.txt", "r", stdin);

	while (scanf("%d", &k) != EOF)
	{
		scanf(" %[^\n]", input);
		
		i = 0;

		p = strtok(input, " ");

		while (p != NULL)
		{
			a[i] = atoi(p);			
			p = strtok(NULL, " ");
			i++;
		}
		
		degree = i;

		if (first)
		{
			first = 0;
		}
		else
		{
			printf("\n");
		}

/*		if (degree < 2)
		{
			printf("q(x): 0\nr = %ld\n", a[0]);
			continue;			
		}*/

		r = 0;

		j = 0;

		for (i = 0;i < degree-1;i++)
		{
			t = a[i]-r;

			q[j] = t;

			r = -t*k;

			j++;
		}

		r = a[i]-r;

		printf("q(x): ");
		for (i = 0;i < degree-1;i++)
		{
			printf("%ld ", q[i]);
		}

		printf("\n");
		printf("r = %ld\n", r);
	}

	return 0;
}

This is the test input:

3
1 -7 15 -8
3
1 -7 15 -9
1
1 0 0 -3
1
1 -1
1
5 -5
3
1 -3
3
3 -9
4
1 -3
4
1 -1
1
5
1
1 -2 1
1
1 -3 3 -1
3
1 -7 12
1
1 -4 6 -4 1
4
1 0 -16
1
1 -4 5 -2
2
1 -4 5 -2
1
1 0 0 0 -1 1
1
1 0 0 0 -1 0
3
-7 2 2
3
1
3
1 -7 15 -8
3
1 -7 15 -9
3
1
3
0 0 0 0 5
-2
1 1 -2

This is the test output:
[quoteq(x): 1 -4 3
r = 1

q(x): 1 -4 3
r = 0

q(x): 1 1 1
r = -2

q(x): 1
r = 0

q(x): 5
r = 0

q(x): 1
r = 0

q(x): 3
r = 0

q(x): 1
r = 1

q(x): 1
r = 3

q(x):
r = 5

q(x): 1 -1
r = 0

q(x): 1 -2 1
r = 0

q(x): 1 -4
r = 0

q(x): 1 -3 3 -1
r = 0

q(x): 1 4
r = 0

q(x): 1 -3 2
r = 0

q(x): 1 -2 1
r = 0

q(x): 1 1 1 1 0
r = 1

q(x): 1 1 1 1 0
r = 0

q(x): -7 -19
r = -55

q(x):
r = 1

q(x): 1 -4 3
r = 1

q(x): 1 -4 3
r = 0

q(x):
r = 1

q(x): 0 0 0 0
r = 5

q(x): 1 -1
r = 0
][/quote]

cases considered:
1) x-k
2) q (x-k)
3) 1/0
4) x-a, a < k
5) (x-k)^2
6) (x-k)^3
7) (x-k)^4

(x-k)(x-a)
9) x^2-k^2
10) x^2-a, a<k
11) x^5-x+1
12) (x-k)^2 ( x-a)
13) (x-k)(x-a)^2
14) k can be negative number
15) also included the test cases in previous posts.
16) k = 0

Moreover, made everything long so that no overflow. Size of the holding array is 2x ~ 10x. Kept the array in the heap. Included blank lines between cases.

Still the judge seems to be unfairly giving WA.

Got any ideas?

amishera · Post by **amishera** » Tue May 11, 2010 12:07 am

It seems like there are only 2 ways left to solve this:

1. beseech
2. bribe

if it were a girl instead then there would be a 3rd approach.

OJ Board

10719 - Quotient Polynomial

10719 - WA

abt 10719 wa

Re: 10719 - WA

10719 Compiler Error!

10719- Quotient Polynomial

please help me why i got wa

Re: 10719 - Quotient Polynomial

Re: 10719 - Quotient Polynomial