10655 - Contemplation - Algebra

[misof]

If you look carefully at the descriptions of the volume forums, you will notice the following sentences:
All about problems in Volume CVI. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

There is already a thread concerning this problem and everything necessary is explained in the thread. And btw, the implementation is correct, you just assume something the test data doesn't assume. Read the original thread for more info.

[cytmike]

Though my code can solve all inputs correctly here, it is still WA.

Is there any other tricks?

[cytmike]

push~
can anybody help me?

[shuniu]

You should check if you are really get WA and not Runtime Error. I used to get WA for this prob when there was a stack overflow exception.

Input:

Code: Select all

83 104 2
83 104 3
83 104 4
164 26 2
164 26 3
164 26 4
33 7 2
33 7 3
33 7 4
155 32 2
155 32 3
155 32 4
11 190 2
11 190 3
11 190 4
523 75 2
523 75 3
523 75 4
0 108 2
0 108 3
0 108 4
220 103 2
220 103 3
220 103 4
155 7 2
155 7 3
155 7 4
35 34 2
35 34 3
35 34 4
346 0 2
346 0 3
346 0 4
119 159 2
119 159 3
119 159 4
428 29 2
428 29 3
428 29 4
49 8 2
49 8 3
49 8 4
154 4 2
154 4 3
154 4 4
10 15 2
10 15 3
10 15 4
271 3 2
271 3 3
271 3 4
86 145 2
86 145 3
86 145 4
20 1 2
20 1 3
20 1 4
288 159 2
288 159 3
288 159 4
0 0

Output:

Code: Select all

6681
545891
44614129
26844
4398152
720598984
1075
35244
1155527
23961
3708995
574127473
-259
-4939
-5119
273379
142937992
74736066391
-216
0
23328
48194
10580020
2322640418
24011
3720620
576528023
1157
39305
1336337
119716
41421736
14331920656
13843
1628396
191578087
183126
78365516
33535130194
2385
116473
5688097
23708
3650416
562069232
70
550
4450
73435
19900072
5392699207
7106
598646
50453186
398
7940
158402
82626
23750496
6827005314

[cytmike]

hey...
i still got the above correct, but still judge gives WA...

i use DeMovire's Theorem to do the power part.

here is my code.


hope sb can help me... [cpp]
#include <iostream>
#include <cmath>

using namespace std;

int main()
{
long double p,h;
int y;
while (cin>>p>>h>>y)
{
double l=p*p-4.0*h;
double i,s,u,n;
if ((p==0)&&(h==1))
{
if (y%4==0)
cout<<2<<endl;
else if (y%4==2)
cout<<-2<<endl;
else
cout<<0<<endl;
}
else if (l>=0)
{
l=sqrt(l);
i=(l+p)/2.0;
s=(p-l)/2.0;
u=pow(i,y);
n=pow(s,y);
long long sky=(long long)(u+n+1e-5);
cout<<sky<<endl;
}
else
{
i=p/2.0;
l=sqrt(-l);
s=l/2.0;
u=sqrt(i*i+s*s);
n=atan2(s,i);
u=pow(u,y);
n=cos(y*n);
u*=2*n;
long long sky;
if (u>0)
sky=(long long)(u+1e-5);
else
sky=(long long)(u-1e-5);
cout<<sky<<endl;
}
}
return 0;
} [/cpp]

[shuniu]

The fact you use "double" and "long double" to store intermediate results are quite dangerous for this prob, cause the result requires very high precision.
Here are some test cases I think your program generates close but not precise results:

Code: Select all

504 8562 7
732 3058 6
165 4604 8
854 7611 6
673 1586 6
210 1840 8
759 8381 6
541 8465 6
64 5660 10
684 3641 6
779 9292 6
385 5191 7
465 1938 7
534 2041 6
182 7798 9
266 9362 8
850 9576 6
365 1767 7
879 5598 6
77 3769 10
281 5696 7
361 7213 7
117 8395 9
924 8210 6
509 6248 7
153 5004 9
915 3922 6
686 6912 6
201 5468 8
973 365 6
463 1736 7
353 2204 7
36 3844 10
903 6571 6
103 2901 10
716 4176 6
826 3815 6
135 9144 10
375 160 7
88 9162 10
787 2754 6
344 7939 7
620 8006 6
193 5064 8
957 3377 6
800 7298 6
442 6365 7
215 7051 8
844 8315 6
477 4986 7
979 7731 6
207 2541 8
852 8562 6
668 9520 6
552 8396 6
763 4009 6
80 7131 10
481 2767 7
732 446 6
588 7003 6
4 5340 10
762 7070 6
209 8585 8
827 5656 6
42 5949 9
161 6325 9
387 9908 7
306 9221 7
335 8585 7
119 5454 9
509 7379 7
136 2899 9
353 2743 7
865 3355 6
338 2284 7
902 8739 6
3 5259 10
34 5161 10
459 4596 7
876 4662 6
947 5416 6
492 9457 7
300 3201 7
373 1650 7
901 81 6
509 9357 7
35 876 12
691 987 6
296 1433 7
650 3004 6
92 593 9
112 2939 10
106 3668 10
343 8638 7
31 9719 10
0 0

Code: Select all

6440755780408195008
148616206667897776
78748760341807937
364014028742456062
90974063250924777
2647122996252320000
174858232354870682
20908446022289826
3642933146508773376
97682512741870142
203411784592600049
967578532265365405
4411122789955498515
22202062364809042
3034163152740268640
6395836908480648224
347751646084330048
785058808859808785
441413074128562785
-1338340077206904649
78198317591141161
522762131196660457
-45962959948179768
586955455288535216
7428591194027892733
1637606314594690749
570470393709083329
95235743675796544
651703541441078177
846587473162687674
4306687924532939303
601404923825472637
1646474510124648448
516261064992111322
-405021271908455873
128229482717028352
307033798121500086
-2202088696166237823
1034556090175734375
-8255534614148014400
231304404738867553
337055187129282056
49922995163457168
466897122746367169
751293841387072610
244514440036344816
2592305046949223138
864526845147734927
336582159819952266
4794095746084624407
838336704632717482
1997709261668715807
355913285075141040
77839024413384704
23805094291213952
189240832490630258
-8129239486594089302
5469999353276752957
153071673301604432
36458992993494346
-8361018491534157824
181721355781823264
297636972628924991
304236545956421177
118436148573272586
549649160623827866
775064983603520871
110471336088092586
257252136937339375
109509483051540089
7185993768454017361
2269396191992798536
582341951190644669
407692901342632250
436245514525438592
504415480045034638
-7873849495791621549
5345459725938287474
3665120001892160319
435559723071638544
695374327443202697
5216169770892990156
168055252245837900
923101398558351847
534673559887419682
6772566257374098053
234423417965875777
107514027377612794
177032993078714152
72235753579551872
232246322830171580
2856114902338834026
441601219842432000
312086112164239609
1387789154256151323

[cytmike]

yea...
i got many of these wrong

but then...
what data type should i use to avoid this problem?

[cytmike]

i used the matrix multiplication method to get AC
thank you anybody who helped me, especially shuniu!!

[Noim]

I am really ashamed that I didn't find this. I already solved similar problems, so this should have been easy for me

I'm ashamed I didn't think about it in contest time when I knew that Xn = pXn-1 + qXn-2.

i am ashamed too, but just the opposite reason you are. i could NEVER solve this problem if you two did not give the formula in the board. i solve this problem after see your formula ( it's just like cheating). my formula was nothing but stupid one...... to solve this problem.

i wonder how you people are so genius. and i am so stupid.

[Solaris]

I have just solved 10655... I have used an O(n) recursion technique with some checks for special cases... In one part of my solution I had to compute (a+b)^n

God Bless Manzoor Bhai... He has not given the following test case [He is not that cruel.. ] :

4 4 50

The ultimate a^n + b^n is within limit of 64-bit integet but the intermediate (a+b)^n will cross the 64 bit limit.

[abishek]

may be he will read this post add the case to the input set and rejudge the problem . I for one would be happy as I am sure my solution will not fail

[Repon kumar Roy]

I am getting Runtime Error For this problem ..
I used matrix exponentiation to solve...

Code: Select all

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<vector>
#include<map>
#include<queue>
#include<stack>
#include<cstdlib>
#include<algorithm>
#include<set>
#include<iterator>
#include<cassert>

using namespace std;

/*------- Constants---- */
#define MX 1030
#define ll long long
#define ull unsigned long long
#define mod 1000000007


struct matrix{
    ll row,col,value[6][6];
};

matrix multiply(matrix &a, matrix &b)
{
    matrix ret;
    ret.row=a.row;
    ret.col=b.col;
    int sum;
    for (int i=0; i<ret.row; i++) {
        for (int j=0; j<ret.col; j++) {
            sum=0;
            for (int k=0; k<a.col; k++) {
                sum+= a.value[i][k]* b.value[k][j];
                sum %=mod;
            }
            ret.value[i][j]=sum;
        }
        
    }
    return ret;
}

matrix matrixExpo(matrix &a, ll p) {
    matrix tmp;
    if (p == 1) return a;
    if (p % 2 == 1){
        tmp=matrixExpo(a, p-1);
        return multiply(a,tmp);
    }
    tmp = matrixExpo(a, p / 2);
    return multiply(tmp, tmp);
}

int main()
{
    ll n,plus,multiple,discri;
    
    matrix mul,res;
    mul.row=2;
    mul.col=2;
    while (scanf("%lld %lld %lld",&plus,&multiple,&n)==3) {
        mul.value[0][0]=plus;
        mul.value[0][1]=(-1)*multiple;
        mul.value[1][0]=1;
        mul.value[1][1]=0;
        
        if(n==1){
            printf("%lld\n",plus);
            
        }
        else {
            res= matrixExpo(mul, n-1);
            discri = res.value[0][0]*plus + 2*res.value[0][1];
            printf("%lld\n",discri);
        }
    }
    return 0;
}

[lbv]

I am getting Runtime Error For this problem ..

You may try:

Input

Code: Select all

2 1 0
0 0

Output

Code: Select all

2