11099 - Next Same-Factored

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

Moderator: Board moderators

farzane
New poster
Posts: 26
Joined: Thu Jun 15, 2006 9:26 am

Post by farzane »

Thank you very much Arsalan.I got AC now. :P
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
Experienced poster
Posts: 111
Joined: Mon Jan 09, 2006 6:19 pm
Location: Tehran, Iran
Contact:

Post by arsalan_mousavian »

farzane wrote:Thank you very much Arsalan.I got AC now. :P
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
In being unlucky I have the record.

erdos
New poster
Posts: 32
Joined: Sat Jul 06, 2002 9:38 pm
Location: Lisbon
Contact:

Post by erdos »

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
Experienced poster
Posts: 111
Joined: Mon Jan 09, 2006 6:19 pm
Location: Tehran, Iran
Contact:

Post by arsalan_mousavian »

some randomly generated input
input:

Code: Select all

1
2
3
4
16
12
24
199238
999321
777234
212121
999999
888888
777777
666666
555555
444444
333333
222222
111111
my AC program outputs:

Code: Select all

Not Exist!
4
9
8
32
18
36
398476
Not Exist!
1554468
272727
1222221
1333332
999999
888888
1666665
666666
777777
444444
333333
In being unlucky I have the record.

H_Hima
New poster
Posts: 18
Joined: Mon Sep 25, 2006 10:56 am
Location: Solar System
Contact:

Please help in mistakes

Post by H_Hima »

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
New poster
Posts: 10
Joined: Wed Aug 09, 2006 11:47 pm

Post by Ecou »

Some Testcases you fail:

Code: Select all

7500
95000
157636
My AC outputs:

Code: Select all

7680
97280
315272

H_Hima
New poster
Posts: 18
Joined: Mon Sep 25, 2006 10:56 am
Location: Solar System
Contact:

Post by H_Hima »

thanks a lot.

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

thanks again.

Timo
Learning poster
Posts: 70
Joined: Tue Oct 11, 2005 2:44 am
Location: Indonesia

Post by Timo »

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

100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
My output :

Code: Select all

160
10201
204
10609
208
315
212
11449
144
11881
220
333
196
12769
228
575
232
351
236
833
150
1331
244
369
248
625
168
16129
256
387
260
17161
198
931
268
225
272
18769
276
19321
280
423
284
1573
162
725
292
189
296
22201
180
22801
304
459
308
775
234
24649
316
477
200
1127
192
26569
328
495
332
27889
252
2197
340
513
344
29929
348
245
242
531
356
32041
240
32761
364
549
368
925
372
2057
376
441
380
36481
216
37249
388
585
224
38809
264
39601
Last edited by Timo on Thu Sep 28, 2006 10:50 am, edited 1 time in total.
"Life is more beautiful with algorithm"

Hisoka
Experienced poster
Posts: 120
Joined: Wed Mar 05, 2003 10:40 am
Location: Indonesia

Post by Hisoka »

your output is correct.

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

gutlak ...

hehehe

PG
New poster
Posts: 4
Joined: Mon Nov 14, 2005 7:16 am

Re: 11099 - Next Same-Factored

Post by PG »

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".

Post Reply

Return to “Volume 110 (11000-11099)”