11170 - Cos(NA)

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

Moderator: Board moderators

stubbscroll
Experienced poster
Posts: 151
Joined: Tue Nov 16, 2004 7:23 pm
Location: Norway
Contact:

11170 - Cos(NA)

Post by stubbscroll » Sun Feb 18, 2007 12:00 pm

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__
New poster
Posts: 1
Joined: Sun Feb 18, 2007 12:15 pm
Contact:

Post by aboya__ » Sun Feb 18, 2007 12:21 pm

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)


User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Re: 11170 Cos(NA)

Post by little joey » Sun Feb 18, 2007 12:23 pm

stubbscroll wrote: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
Experienced poster
Posts: 151
Joined: Tue Nov 16, 2004 7:23 pm
Location: Norway
Contact:

Post by stubbscroll » Sun Feb 18, 2007 12:33 pm

My output for 1 is:

Code: Select all

Cos(A)

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey » Sun Feb 18, 2007 12:47 pm

Hmm. That's correct. Strange.

stubbscroll
Experienced poster
Posts: 151
Joined: Tue Nov 16, 2004 7:23 pm
Location: Norway
Contact:

Post by stubbscroll » Sun Feb 18, 2007 1:09 pm

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
Last edited by stubbscroll on Sun Feb 18, 2007 2:01 pm, edited 1 time in total.

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey » Sun Feb 18, 2007 1:52 pm

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
Experienced poster
Posts: 151
Joined: Tue Nov 16, 2004 7:23 pm
Location: Norway
Contact:

Post by stubbscroll » Sun Feb 18, 2007 2:03 pm

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
Learning poster
Posts: 84
Joined: Wed Jan 28, 2004 6:23 pm

Post by FAQ » Mon Feb 19, 2007 6:01 am

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

stubbscroll
Experienced poster
Posts: 151
Joined: Tue Nov 16, 2004 7:23 pm
Location: Norway
Contact:

Post by stubbscroll » Mon Feb 19, 2007 10:30 am

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
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Post by mf » Mon Feb 19, 2007 9:50 pm

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
New poster
Posts: 44
Joined: Thu Sep 01, 2005 12:14 pm
Location: Yerevan, Armenia

Post by snar » Mon Feb 19, 2007 9:54 pm

mf wrote: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.
Narek Saribekyan

snar
New poster
Posts: 44
Joined: Thu Sep 01, 2005 12:14 pm
Location: Yerevan, Armenia

Post by snar » Tue Feb 20, 2007 6:25 am

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

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada
Contact:

Post by sclo » Tue Feb 20, 2007 7:11 am

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

User avatar
sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

what was ur approach??

Post by sohel » Tue Feb 20, 2007 9:21 am

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?

Post Reply

Return to “Volume 111 (11100-11199)”