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:
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)
little joey
Guru
Posts: 1080 Joined: Thu Dec 19, 2002 7:37 pm
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
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.
Last edited by
stubbscroll on Sun Feb 18, 2007 2:01 pm, edited 1 time in total.
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.
sohel
Guru
Posts: 856 Joined: Thu Jan 30, 2003 5:50 am
Location: New York
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?