11170 - Cos(NA)

[stubbscroll]

During competition I got WA, although my algorithm seemed correct. Can anybody confirm if this is the correct answer for 49? Linebreaks are added to avoid a too long line.

Code: Select all

281474976710656Cos^49(A)
-3448068464705536Cos^47(A)
+19826393672056832Cos^45(A)
-71116412084551680Cos^43(A)
+178383666978750464Cos^41(A)
-332442288460398592Cos^39(A)
+477402588661153792Cos^37(A)
-540731503483551744Cos^35(A)
+490450067946209280Cos^33(A)
-359663383160553472Cos^31(A)
+214414709191868416Cos^29(A)
-104129631497486336Cos^27(A)
+41159347585155072Cos^25(A)
-13192098584985600Cos^23(A)
+3405715246940160Cos^21(A)
-701176668487680Cos^19(A)
+113542812794880Cos^17(A)
-14192851599360Cos^15(A)
+1335348940800Cos^13(A)
-91365980160Cos^11(A)
+4332007680Cos^9(A)
-132612480Cos^7(A)
+2344160Cos^5(A)
-19600Cos^3(A)
+49Cos(A)

[aboya__]

Code: Select all

47
70368744177664Cos^47(A)-826832744087552Cos^45(A)+4547580092481536Cos^43(A)-15554
790998147072Cos^41(A)+37078280867676160Cos^39(A)-65416681245114368Cos^37(A)+8855
1849002532864Cos^35(A)-94086339565191168Cos^33(A)+79611518093623296Cos^31(A)-541
21865370664960Cos^29(A)+29693888297959424Cos^27(A)-13159791404777472Cos^25(A)+46
99925501706240Cos^23(A)-1345114425262080Cos^21(A)+305707823923200Cos^19(A)-54454
206136320Cos^17(A)+7465496002560Cos^15(A)-768506941440Cos^13(A)+57417185280Cos^1
1(A)-2967993600Cos^9(A)+98933120Cos^7(A)-1902560Cos^5(A)+17296Cos^3(A)-47Cos(A)

[little joey]

During competition I got WA, although my algorithm seemed correct. Can anybody confirm if this is the correct answer for 49? Linebreaks are added to avoid a too long line.

Code: Select all

281474976710656Cos^49(A)
-3448068464705536Cos^47(A)
+19826393672056832Cos^45(A)
-71116412084551680Cos^43(A)
+178383666978750464Cos^41(A)
-332442288460398592Cos^39(A)
+477402588661153792Cos^37(A)
-540731503483551744Cos^35(A)
+490450067946209280Cos^33(A)
-359663383160553472Cos^31(A)
+214414709191868416Cos^29(A)
-104129631497486336Cos^27(A)
+41159347585155072Cos^25(A)
-13192098584985600Cos^23(A)
+3405715246940160Cos^21(A)
-701176668487680Cos^19(A)
+113542812794880Cos^17(A)
-14192851599360Cos^15(A)
+1335348940800Cos^13(A)
-91365980160Cos^11(A)
+4332007680Cos^9(A)
-132612480Cos^7(A)
+2344160Cos^5(A)
-19600Cos^3(A)
+49Cos(A)

Same as mine. What is your output for 1?

[stubbscroll]

My output for 1 is:

Code: Select all

Cos(A)

[little joey]

Hmm. That's correct. Strange.

[stubbscroll]

Hmm, I don't get it either. I'm sure it is an obvious bug that I can't see because I've stared me blind. I'm temporarily posting my code so that others can try it and compare the output. I hope I can figure it out with your help, thanks in advance.

Code: Select all

Accepted

[little joey]

I replaced llabs() with a handmade function and got your code accepted, so I think it doesn't work as you expect (it's not in C&R, so it's not officially C).

BTW: you can use printf("%lld",x) to print long longs.

[stubbscroll]

Ah, thanks. I'll try to avoid llabs in the future, then.

The reason why I use my own routine to print long long variables, is that "%lld" somehow does not work on my computer.

[FAQ]

if you use DevC++, you can try printf("%I64d", x)

[stubbscroll]

Thanks for the tip! I am actually using Dev-C++, and it works fine. (Now comes the potential headache of remembering to change it to %lld when I submit to UVa.)

[mf]

Here are correct outputs for first few cases, for those who are getting WAs:

Code: Select all

Cos(A)
2Cos^2(A)-1
4Cos^3(A)-3Cos(A)
8Cos^4(A)-8Cos^2(A)+1
16Cos^5(A)-20Cos^3(A)+5Cos(A)
32Cos^6(A)-48Cos^4(A)+18Cos^2(A)-1
64Cos^7(A)-112Cos^5(A)+56Cos^3(A)-7Cos(A)

[snar]

Here are correct outputs for first few cases, for those who are getting WAs:

Code: Select all

Cos(A)
2Cos^2(A)-1
4Cos^3(A)-3Cos(A)
8Cos^4(A)-8Cos^2(A)+1
16Cos^5(A)-20Cos^3(A)+5Cos(A)
32Cos^6(A)-48Cos^4(A)+18Cos^2(A)-1
64Cos^7(A)-112Cos^5(A)+56Cos^3(A)-7Cos(A)

Thanks, I think I found my mistake.

[snar]

Finally I got AC, but my solution run in more than 0,4 sec. I suppose, you're using another algorithm, right?

[sclo]

There is a way to express cos(NA) in terms some previous terms.

[sohel]

During the real time contest, I tried this approach:
1] cos(mx) = cos(m/2x + m/2x) =cos^2(m/2x)-sin^2(m/2x)->for even m
sin^2(nx) = 1 - cos^2(nx).

So for even m, I could eliminate sin(). But for odd values of m, I couldn't get rid of sin(). After opening my A'Level Pure Maths book and a bit of googling, I found that cos(nx) can be expressed in terms of cos(n-1) and cos(n-2).

How did you guys do it?