10719 - Quotient Polynomial

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

Moderator: Board moderators

Moussa
New poster
Posts: 6
Joined: Fri Jun 24, 2005 1:29 am

10719 - WA

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

User avatar
Rocky
Experienced poster
Posts: 124
Joined: Thu Oct 14, 2004 9:05 am
Contact:

abt 10719 wa

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
A great helper
Posts: 286
Joined: Mon Oct 03, 2005 1:54 pm
Location: Bangladesh
Contact:

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.

User avatar
Martin Macko
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)

Re: 10719 - WA

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
New poster
Posts: 33
Joined: Tue Jun 29, 2004 1:38 pm
Location: IITM,chennai,Tamil Nadu,India
Contact:

10719 Compiler Error!

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;
	}
}
Karthe

Karthekeyan
New poster
Posts: 33
Joined: Tue Jun 29, 2004 1:38 pm
Location: IITM,chennai,Tamil Nadu,India
Contact:

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??
Karthe

User avatar
Martin Macko
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)

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
New poster
Posts: 6
Joined: Fri Jun 24, 2005 1:29 am

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

i don't know what to say :oops: 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 :roll:

Moussa
New poster
Posts: 6
Joined: Fri Jun 24, 2005 1:29 am

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
New poster
Posts: 4
Joined: Mon Apr 23, 2007 6:05 am

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.
Last edited by legnaleurc on Sun May 06, 2007 10:50 am, edited 1 time in total.

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

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

Check mamun's post.
Ami ekhono shopno dekhi...
HomePage

rongtuli
New poster
Posts: 5
Joined: Fri Aug 17, 2007 4:38 am

10719- Quotient Polynomial

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
by tulip

nayimsust
New poster
Posts: 9
Joined: Wed Aug 27, 2008 6:50 pm

please help me why i got wa

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

i got ac now i used pow function for interger variable :)

amishera
New poster
Posts: 38
Joined: Sat Dec 27, 2008 10:42 pm

Re: 10719 - Quotient Polynomial

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
8) (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
New poster
Posts: 38
Joined: Sat Dec 27, 2008 10:42 pm

Re: 10719 - Quotient Polynomial

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.

Post Reply

Return to “Volume 107 (10700-10799)”