| ENG RUS | Timus Online Judge |
Discussion of Problem 1594. Aztec TreasureShen Yang AC with long double [6] // Problem 1594. Aztec Treasure 20 Oct 2017 21:14 rt Shen Yang Re: AC with long double [5] // Problem 1594. Aztec Treasure 20 Oct 2017 21:25 deleted Edited by author 21.10.2017 21:07 Mahilewets Nikita Re: AC with long double [4] // Problem 1594. Aztec Treasure 20 Oct 2017 21:52 Why not std:: complex? I have not read the code very carefully, maybe miss something important Mahilewets Nikita Re: AC with long double [3] // Problem 1594. Aztec Treasure 20 Oct 2017 21:53 Maybe not possible to made it long double? Shen Yang Re: AC with long double [2] // Problem 1594. Aztec Treasure 21 Oct 2017 09:46 it involves with Chebyshev polynomial U(x) is Chebyshev polynomial Um(i*An/2)= i*An*Um-1(i*An/2)-Um-2(i*An/2) i is unit imaginary number An is a n*n matrix Aij==1 if and only if abs(i-j)==1. sqrt(det(Um(i*An/2）) is the answer.. I use long double because I need to judge the sign of sqrt(ans^2) Edited by author 21.10.2017 09:46 ComebackSeason Re: AC with long double [1] // Problem 1594. Aztec Treasure 21 Oct 2017 19:59 Delete the code please. Posting AC code here violates the rules. You can explain your idea (which is not recommended either) Shen Yang Re: AC with long double // Problem 1594. Aztec Treasure 2 Nov 2018 19:23 100 100 exactly result: 211296849512315762188619578574048657110653043609449472144725843973442479614058285996396387014570402447830177110492225916018306620473309898122553032154580078102848452707439935767561964432764309438889871659414420572001206784720890894593722611533746574726650832697664485530063095995962974740556608440361525520881534009295321784945692404915331234788462418215336479515406547891566477310928856298254153861327506039317299734093964771367687300616477954739907701770903890588939771176356807995358624375906635501695115399580918628783125903772434369374398388373031207325810190683145008704318854255120274024753774893652675256050843161415941752800234892558301824773136514256893938068687029095739098286424428752900415743287209790876036884080292271611832363684077924978489349099638343563775430445274281910983984807471952213028600596500243377496299053827784481766322799764412944529657092342282080566012889979741375614523723377108743228485047911163027695369684514018557778209543315449702696764786683247792132799136211383970764610828007749277178715661259454260357449248458683734007683846942145977953891807183259007702385978401831386444472112720952063414073905105738447216839800171442748174691808886777635485410113868685679678838952355104065272999262338505349001538065924096 Al.Cash How to solve this problem? (+) [12] // Problem 1594. Aztec Treasure 17 Jun 2009 19:43 The number of ways to tile an MxN rectangle with 1x2 dominos is 2^(M*N/2) times the product of { cos^2(m*pi/(M+1)) + cos^2(n*pi/(N+1)) } ^ (1/4) over all m,n in the range 0<m<M+1, 0<n<N+1. I have found this formula in internet and I would like to know is there a way to use it for solving this problem? Samsonov Alex [USU] Re: How to solve this problem? (+) [10] // Problem 1594. Aztec Treasure 18 Jun 2009 14:08 There is a solution of this problem which doesn't use this formula. But it uses something related to the problem name :) Vedernikoff Sergey (HSE: АОП) Re: How to solve this problem? (+) [9] // Problem 1594. Aztec Treasure 18 Jun 2009 21:21 Don't you mean Aztec Diamond? And how is it connected then? =) Samsonov Alex [USU] Re: How to solve this problem? (+) [8] // Problem 1594. Aztec Treasure 19 Jun 2009 15:39 Your guess is correct. The connection, however, is quite unobvious. Partisan Re: How to solve this problem? (+) [3] // Problem 1594. Aztec Treasure 21 Jun 2009 20:58 The answer can be calculated as number of perfect matching in corresponding planar graph using Kasteleyn theorem. But it uses determinant of matrix (nm/2)x(mn/2) (symmetric and with zeroes) and complex numbers, so now i don't know, can or cannot it to be applied to this problem. Hm, maybe it gives the formula posted by Al.Cash :-)))) Edited by author 21.06.2009 20:59 Vedernikoff Sergey (HSE: АОП) Re: How to solve this problem? (+) [2] // Problem 1594. Aztec Treasure 22 Jun 2009 20:18 Yes, it gives exactly this formula =) But you can't use it due to precision reasons. We need integral-numbers formula... svr Re: How to solve this problem? (+) [1] // Problem 1594. Aztec Treasure 23 Jun 2009 19:59 Very interesting from theoretical and practical point of view to use Java.BigDecimal with 1000-10000 digits and catch right answer. Partisan Re: How to solve this problem? (+) // Problem 1594. Aztec Treasure 23 Jun 2009 22:21 Connection with Aztec Diamond! Something interest, but only for (2n)x(2n) squares: Consider the 2n-by-2n matrix View the MathML source with mi,j=1 for i,j satisfying |2i−2n−1|+|2j−2n−1|less-than-or-equals, slant2n and mi,j=0 for all other i,j, consisting of a central diamond of 1's surrounded by 0's. When ngreater-or-equal, slanted4, the λ-determinant of the matrix M (as introduced by Robbins and Rumsey [Adv. Math. 62 (1986) 169–184]) is not well defined. However, if we replace the 0's by t's, we get a matrix whose λ-determinant is well defined and is a polynomial in λ and t. The limit of this polynomial as t→0 is a polynomial in λ whose value at λ=1 is the number of domino-tilings of a 2n-by-2n square. zbao Re: How to solve this problem? (+) [3] // Problem 1594. Aztec Treasure 25 Jun 2009 11:44 Nice problem! Finally got accepted after trying for 2 hours. best, Josh Bao Edited by author 25.06.2009 12:34 Al.Cash Re: How to solve this problem? (+) // Problem 1594. Aztec Treasure 25 Jun 2009 13:34 2zbao: I think this gave us no useful information! Edited by author 25.06.2009 15:27 Partisan Re: How to solve this problem? (+) [1] // Problem 1594. Aztec Treasure 25 Jun 2009 15:59 Your submissions looks like some binary search or other cheatings... Why you get different wrongs many times for tests 29,33,34,36,38,40,42? P.S. Sorry, if I am wrong. Edited by author 25.06.2009 19:39 bsu.mmf.team Re: How to solve this problem? (+) // Problem 1594. Aztec Treasure 29 Mar 2011 19:02 Wolfram Mathematica 8 allows you to use this formula with trigonometry. He is a genius! It's a wonderful package!!! :) PrankMaN Re: How to solve this problem? (+) // Problem 1594. Aztec Treasure 25 Mar 2013 03:38 Didn't read the whole thread, but it's DP problem http://e-maxx.ru/algo/profile_dynamics
|