11099 - Next Same-Factored

farzane · Post by **farzane** » Fri Sep 22, 2006 10:20 pm

Thank you very much Arsalan.I got AC now.

The compiler I use doesn't have type long long,so I couldn't check all of your inputs and inputs to find out my mistake.

arsalan_mousavian · Post by **arsalan_mousavian** » Sat Sep 23, 2006 7:16 pm

farzane wrote:Thank you very much Arsalan.I got AC now.
The compiler I use doesn't have type long long,so I couldn't check all of your inputs and inputs to find out my mistake.

you 're welcome , you can use VS.Net 2003 or 2005, both of them supports long long

erdos · Post by **erdos** » Sun Sep 24, 2006 9:59 pm

Hi,

I don't think this program requires the use of long long because we can test if an overflow is going to happen in advance.

What is the output for 1 ? Not Exist or 1 ?

I can't see why I'm having WA. Can you post some inputs, please?

Regards,

Jose Santos

arsalan_mousavian · Post by **arsalan_mousavian** » Sun Sep 24, 2006 11:55 pm

some randomly generated input
input:

Code: Select all

my AC program outputs:

Code: Select all

H_Hima · Post by **H_Hima** » Mon Sep 25, 2006 6:27 pm

Hi

may anybody help me in my code.
my code got true for all of testcases above.
but i got WA

and can't understand where is the mistake.

may you help me with testcases or ...

here is my code

Code: Select all

#include <stdio.h>
#include <iostream>
//#include <fstream>
using namespace std;

short int count[1000001];
int primes[1000001][7];

struct node{
	int data;
	node *next;
};
class list{
public:
	list()	{	start=0;	}
	void add(int);
	node *start;
	~list() {
		node *cur=start;
		while(cur) {
			start=start->next;
			delete cur;
			cur=start;
		}
	}
};
void list::add(int data) {
	node *cur=start,*prv=0;
	node *New=new node;
	New->data=data;
	while(cur&&(cur->data)<data) {
		prv=cur;
		cur=cur->next;
	}
	if(cur&&cur->data==data);
	else if(prv) {
		New->next=cur;
		prv->next=New;
	}
	else {
		New->next=start;
		start=New;
	}
}


void main() {
	list *List;
	//ofstream cout("out.txt");
  int num,i,j,k,max,Max,tp,pos,Count,mult;
  count[1]=count[0]=0;
  count[2]=0;
  for(i=0;i<=1000000;i++)
    count[i]=0;
  for(i=2;i<=1000000;i++) {
    if(!count[i]) {
      for(j=i;j<=1000000;j+=i)  {
        primes[j][count[j]]=i;
        count[j]++;
      }
    }
  }
  cin>>num;
  while(!cin.eof()) {
	 // for(num=0;num<1000000;num++)	{
		//  cout<<num<<"		";
		  List=new list;
		Max=2000001;
		  if(num==1)	cout<<"Not Exist!"<<endl;
		  else if(count[num]==1)	{
				pos=num*primes[num][0];
				if(pos>=2000000||pos<=0)	cout<<"Not Exist!"<<endl;
				else						cout<<pos<<endl;
		}
		else {
				mult=1;
				for(i=0;i<count[num];i++)	mult*=primes[num][i];
				List->add(mult);
				node *cur=List->start,*tem=0;
				Count=0;
				max=4*count[num];
				for(;max>=Count && cur;cur=List->start) {
					for(j=0;j<count[num];j++)	{
						tp=(cur->data)*primes[num][j];
						if(tp>num||tp<=0)	{
							if(tp<Max)	Max=tp;
							Count++;
							break;
						}
						else if(tp>=0)	List->add(tp);
					}
					List->start=cur->next;
					delete cur;
				}
				delete List;
				if(Max>=2000000 || Max<=0) 
					cout<<"Not Exist!"<<endl;
				else
					cout<<Max<<endl;
		  }
	 // }
	  cin>>num;
  }
//  cout.close();
}

thanks!

Ecou · Post by **Ecou** » Mon Sep 25, 2006 8:12 pm

Some Testcases you fail:

Code: Select all

7500
95000
157636

My AC outputs:

Code: Select all

7680
97280
315272

H_Hima · Post by **H_Hima** » Tue Sep 26, 2006 10:12 pm

thanks a lot.

I find my mistake and got AC.
without your testcases I can't get it.

thanks again.

Timo · Post by **Timo** » Thu Sep 28, 2006 7:32 am

Hey,I Got WA for this problem,and I can't figure why my program got WA

Code: Select all

Removed after AC

I found my bug,my calculation is overflow
Ok,this is some test case,try it,Good Luck

Code: Select all

My output :

Code: Select all

Hisoka · Post by **Hisoka** » Thu Sep 28, 2006 8:00 am

your output is correct.

but, maximum value for array of temp can be more than integer range (499958000882)

gutlak ...

hehehe

PG · Post by PG » Thu Apr 17, 2008 7:01 am

I solved this problem just now,
and want to share some information to those who is trobled with this question.

First,you may not need to stored those num you count before.
When I stored, I got AC by 1.1 sec.
When I didn't, I got AC by 1.3 sec.

You can just try using those factors to build the ans,
the methoud can be the same as Ugly Number.
It can pass the time-limit.

And last,use long long when you check, or you probably fail on some numbers like this "999987".

OJ Board

11099 - Next Same-Factored

Please help in mistakes

Re: 11099 - Next Same-Factored