12573 - Sohel Sir's Assignment

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

Moderator: Board moderators

Post Reply
ioi
New poster
Posts: 8
Joined: Sat May 05, 2012 10:44 pm

12573 WA :'(

Post by ioi »

Code: Select all

#include<stdio.h>
#include<math.h>
#define prime(i) ((Prime[i>>5])&(1<<(i&(31))))
#define set(j) (Prime[j>>5]|=(1<<(j&(31))))
#define LIM 86100000
#define SLIM 9278


typedef unsigned long long i64;

i64 Prime[1100000];
i64 pos[5010001],l;


void sieve()
{
	i64 i, j, m, n, t,x,k,h;
	set(1);
	pos[1]=2;
	pos[2]=3;
	for(k=2,l=3,i=5; i<=SLIM; k++,i=3*k-(k&1)-1)
	{
		if(prime(k)==0)
		{
			pos[l++]=i;
			for(j=i*i,h=((j+2)/3); j<=LIM; h+=(k&1)?(h&1?((k<<2)-3):((k<<1)-1)):(h&1?((k<<1)-1):((k<<2)-1)),j=3*h-(h&1)-1)
			set(h);
		}
	    i=3*k-(k&1)-1;
    }
	for(; i<=LIM; k++,i=3*k-(k&1)-1)
	{
	   if(prime(k)==0)
	   pos[l++] = i;
    }
}

i64 solve(i64 modv,i64 n)
{
    i64 i,j,len,k,val,maxm;
    i64 minm=10000000000002;
    i=1;
    while(i<l && pos[i]*pos[i]<=n)
    {
        if(n%pos[i]==0)
        {
            while(n%pos[i]==0)
            {
                n/=pos[i];
                if(n>modv)
                {
                    minm=(minm>n? n:minm);
                }
            }
        }
        i++;
    }
    if(n>1)
    {
        if(n>modv)
        {
            minm=(minm>n? n:minm);
        }
    }
    if(1>modv)
    {
        minm=(minm>1? 1:minm);
    }
    return minm;
}

int main()
{
    sieve();
    int test,t;
    i64 x,y,m,rem,res,mod_val;
    scanf("%d",&test);
    for(t=0;t<test;t++)
    {
        scanf("%llu%llu",&x,&y);
        if(x<=y)
        {
            printf("Impossible\n");
            continue;
        }
        mod_val=y-2;
        rem=x-mod_val;
        res=solve(mod_val,rem);
        printf("%llu\n",res);
    }
    return 0;
}
Getting WA...Please Help...Give me Some i/o...
Thanks in Advance....
Top
brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 12573 WA :'(

Post by brianfry713 »

Input

Code: Select all

125
897 148
765 303
1 3
220 135
729 573
184 19
104 6
909 198
724 578
387 2
241 186
159 111
653 448
418 138
36 13
516 86
703 500
304 124
491 234
464 174
183 111
796 288
979 439
356 151
667 516
976 70
728 541
106 55
193 42
71 51
114 42
543 73
248 133
901 829
752 7
649 147
702 502
913 543
529 346
72 64
392 176
103 4
872 770
189 73
113 57
985 664
537 522
735 382
445 2
214 71
690 614
822 751
687 555
763 12
73 2
412 136
263 130
965 435
105 101
580 206
103 75
136 30
472 434
115 17
197 87
494 18
572 344
659 547
120 93
165 110
637 579
39 31
472 226
724 270
157 17
486 458
249 225
592 10
874 203
18 14
417 74
338 100
517 250
938 147
418 45
522 192
59 58
644 128
255 207
108 63
51 13
364 225
597 245
712 127
42 3
231 191
932 315
829 470
565 485
466 432
559 246
417 191
930 333
840 417
809 330
287 2
923 35
851 158
987 33
370 122
672 36
178 33
860 407
431 301
463 364
788 751
956 292
19 9
336 111
760 349
498 242
384 35
78 45
320 123
176 147
AC output:

Code: Select all

751
464
2
Impossible
Impossible
167
5
713
Impossible
1
Impossible
Impossible
Impossible
141
25
108
Impossible
182
259
292
Impossible
510
542
207
Impossible
227
Impossible
Impossible
51
Impossible
74
118
Impossible
Impossible
9
168
Impossible
Impossible
Impossible
Impossible
218
101
Impossible
118
58
Impossible
Impossible
Impossible
1
145
Impossible
Impossible
Impossible
251
1
139
135
532
Impossible
376
Impossible
36
Impossible
20
112
239
Impossible
Impossible
Impossible
Impossible
Impossible
Impossible
248
456
71
Impossible
Impossible
73
673
Impossible
115
120
269
793
75
332
Impossible
259
Impossible
Impossible
20
Impossible
354
587
41
Impossible
619
Impossible
Impossible
Impossible
315
228
599
425
481
1
89
695
239
125
58
49
455
Impossible
Impossible
Impossible
333
12
227
413
258
39
Impossible
199
Impossible
Check input and AC output for thousands of problems on uDebug!
Top
ioi
New poster
Posts: 8
Joined: Sat May 05, 2012 10:44 pm

Re: 12573 WA :'(

Post by ioi »

Thanks Brainfry Got AC :D
Top
shahedcsedu1906
New poster
Posts: 3
Joined: Fri Jul 25, 2014 4:17 pm

12573 - Sohel Sir's Assignment

Post by shahedcsedu1906 »

Code: Select all

Accepted

I tried the test case in other post . that was okay for my code . but still WA . give me some more i/o
Last edited by shahedcsedu1906 on Sat Jul 26, 2014 11:51 pm, edited 2 times in total.
Top
brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 12573 WA

Post by brianfry713 »

Input:

Code: Select all

286
0 2
1 2
1 3
2 2
2 3
2 4
3 2
3 3
3 4
3 5
4 2
4 3
4 4
4 5
4 6
5 2
5 3
5 4
5 5
5 6
5 7
6 2
6 3
6 4
6 5
6 6
6 7
6 8
7 2
7 3
7 4
7 5
7 6
7 7
7 8
7 9
8 2
8 3
8 4
8 5
8 6
8 7
8 8
8 9
8 10
9 2
9 3
9 4
9 5
9 6
9 7
9 8
9 9
9 10
9 11
10 2
10 3
10 4
10 5
10 6
10 7
10 8
10 9
10 10
10 11
10 12
1000000000000 2
1000000000000 3
1000000000000 4
1000000000000 5
1000000000000 6
1000000000000 7
1000000000000 8
1000000000000 9
1000000000000 10
999999999999 2
999999999999 3
999999999999 4
999999999999 5
999999999999 6
999999999999 7
999999999999 8
999999999999 9
999999999999 10
999999999998 2
999999999998 3
999999999998 4
999999999998 5
999999999998 6
999999999998 7
999999999998 8
999999999998 9
999999999998 10
999999999997 2
999999999997 3
999999999997 4
999999999997 5
999999999997 6
999999999997 7
999999999997 8
999999999997 9
999999999997 10
999999999996 2
999999999996 3
999999999996 4
999999999996 5
999999999996 6
999999999996 7
999999999996 8
999999999996 9
999999999996 10
999999999995 2
999999999995 3
999999999995 4
999999999995 5
999999999995 6
999999999995 7
999999999995 8
999999999995 9
999999999995 10
999999999994 2
999999999994 3
999999999994 4
999999999994 5
999999999994 6
999999999994 7
999999999994 8
999999999994 9
999999999994 10
999999999993 2
999999999993 3
999999999993 4
999999999993 5
999999999993 6
999999999993 7
999999999993 8
999999999993 9
999999999993 10
999999999992 2
999999999992 3
999999999992 4
999999999992 5
999999999992 6
999999999992 7
999999999992 8
999999999992 9
999999999992 10
999999999991 2
999999999991 3
999999999991 4
999999999991 5
999999999991 6
999999999991 7
999999999991 8
999999999991 9
999999999991 10
999999999990 2
999999999990 3
999999999990 4
999999999990 5
999999999990 6
999999999990 7
999999999990 8
999999999990 9
999999999990 10
1000000000000 1000000000002
1000000000000 1000000000001
1000000000000 1000000000000
1000000000000 999999999999
1000000000000 999999999998
1000000000000 999999999997
1000000000000 999999999996
1000000000000 999999999995
1000000000000 999999999994
1000000000000 999999999993
1000000000000 999999999992
999999999999 1000000000001
999999999999 1000000000000
999999999999 999999999999
999999999999 999999999998
999999999999 999999999997
999999999999 999999999996
999999999999 999999999995
999999999999 999999999994
999999999999 999999999993
999999999999 999999999992
999999999999 999999999991
999999999998 1000000000000
999999999998 999999999999
999999999998 999999999998
999999999998 999999999997
999999999998 999999999996
999999999998 999999999995
999999999998 999999999994
999999999998 999999999993
999999999998 999999999992
999999999998 999999999991
999999999998 999999999990
999999999997 999999999999
999999999997 999999999998
999999999997 999999999997
999999999997 999999999996
999999999997 999999999995
999999999997 999999999994
999999999997 999999999993
999999999997 999999999992
999999999997 999999999991
999999999997 999999999990
999999999997 999999999989
999999999996 999999999998
999999999996 999999999997
999999999996 999999999996
999999999996 999999999995
999999999996 999999999994
999999999996 999999999993
999999999996 999999999992
999999999996 999999999991
999999999996 999999999990
999999999996 999999999989
999999999996 999999999988
999999999995 999999999997
999999999995 999999999996
999999999995 999999999995
999999999995 999999999994
999999999995 999999999993
999999999995 999999999992
999999999995 999999999991
999999999995 999999999990
999999999995 999999999989
999999999995 999999999988
999999999995 999999999987
999999999994 999999999996
999999999994 999999999995
999999999994 999999999994
999999999994 999999999993
999999999994 999999999992
999999999994 999999999991
999999999994 999999999990
999999999994 999999999989
999999999994 999999999988
999999999994 999999999987
999999999994 999999999986
999999999993 999999999995
999999999993 999999999994
999999999993 999999999993
999999999993 999999999992
999999999993 999999999991
999999999993 999999999990
999999999993 999999999989
999999999993 999999999988
999999999993 999999999987
999999999993 999999999986
999999999993 999999999985
999999999992 999999999994
999999999992 999999999993
999999999992 999999999992
999999999992 999999999991
999999999992 999999999990
999999999992 999999999989
999999999992 999999999988
999999999992 999999999987
999999999992 999999999986
999999999992 999999999985
999999999992 999999999984
999999999991 999999999993
999999999991 999999999992
999999999991 999999999991
999999999991 999999999990
999999999991 999999999989
999999999991 999999999988
999999999991 999999999987
999999999991 999999999986
999999999991 999999999985
999999999991 999999999984
999999999991 999999999983
999999999990 999999999992
999999999990 999999999991
999999999990 999999999990
999999999990 999999999989
999999999990 999999999988
999999999990 999999999987
999999999990 999999999986
999999999990 999999999985
999999999990 999999999984
999999999990 999999999983
999999999990 999999999982
AC output:

Code: Select all

1
1
2
1
Impossible
3
1
2
Impossible
4
1
3
Impossible
Impossible
5
1
2
3
Impossible
Impossible
6
1
5
4
Impossible
Impossible
Impossible
7
1
2
5
4
Impossible
Impossible
Impossible
8
1
7
3
5
Impossible
Impossible
Impossible
Impossible
9
1
2
7
6
5
Impossible
Impossible
Impossible
Impossible
10
1
3
4
7
6
Impossible
Impossible
Impossible
Impossible
Impossible
11
1
3
2969
5507
6
251
49369
19
14
1
2
5507
4
5
49369
19
8
757
1
5507
3
5
49369
19
7
757
9
1
2
5
49369
19
7
757
9
999999999989
1
5
49369
19
7
757
9
999999999989
11
1
2
3
4
757
6
999999999989
11
17
1
3
4
757
5
999999999989
11
17
13
1
2
757
5
999999999989
11
17
13
35
1
757
3
999999999989
11
17
13
35
12
1
2
999999999989
4
17
13
7
8
229
1
999999999989
4
17
13
7
8
229
41
1000000000001
Impossible
Impossible
Impossible
Impossible
Impossible
Impossible
Impossible
Impossible
Impossible
Impossible
1000000000000
Impossible
Impossible
Impossible
Impossible
Impossible
Impossible
Impossible
Impossible
Impossible
Impossible
999999999999
Impossible
Impossible
Impossible
Impossible
Impossible
Impossible
Impossible
Impossible
Impossible
Impossible
999999999998
Impossible
Impossible
Impossible
Impossible
Impossible
Impossible
Impossible
Impossible
Impossible
Impossible
999999999997
Impossible
Impossible
Impossible
Impossible
Impossible
Impossible
Impossible
Impossible
Impossible
Impossible
999999999996
Impossible
Impossible
Impossible
Impossible
Impossible
Impossible
Impossible
Impossible
Impossible
Impossible
999999999995
Impossible
Impossible
Impossible
Impossible
Impossible
Impossible
Impossible
Impossible
Impossible
Impossible
999999999994
Impossible
Impossible
Impossible
Impossible
Impossible
Impossible
Impossible
Impossible
Impossible
Impossible
999999999993
Impossible
Impossible
Impossible
Impossible
Impossible
Impossible
Impossible
Impossible
Impossible
Impossible
999999999992
Impossible
Impossible
Impossible
Impossible
Impossible
Impossible
Impossible
Impossible
Impossible
Impossible
999999999991
Impossible
Impossible
Impossible
Impossible
Impossible
Impossible
Impossible
Impossible
Impossible
Impossible
Check input and AC output for thousands of problems on uDebug!
Top
shahedcsedu1906
New poster
Posts: 3
Joined: Fri Jul 25, 2014 4:17 pm

Re: 12573 WA

Post by shahedcsedu1906 »

Here the given output data set is 285 lines for T=286 :-?
Top
lighted
Guru
Posts: 587
Joined: Wed Jun 11, 2014 9:56 pm
Location: Kyrgyzstan, Bishkek

Re: 12573 WA

Post by lighted »

I counted 286 lines. :)
Check it again
A person who sees the good in things has good thoughts. And he who has good thoughts receives pleasure from life... Bediuzzaman
Top
shahedcsedu1906
New poster
Posts: 3
Joined: Fri Jul 25, 2014 4:17 pm

Re: 12573 WA

Post by shahedcsedu1906 »

oh sorry ! I counted wrong :-? AC now . Bad mistake :-?
Top
Post Reply

Return to “Volume 125 (12500-12599)”