fork download
copy 
  1. from time import*
  2. from fractions import*
  3. from collections import*
  4. from itertools import*
  5.  
  6. def solve1a():
  7. 	dotprod = lambda A,B: sum(a*b for a,b in zip(A,B))
  8.  
  9. 	for n in xrange(1,7):
  10. 		numer=0
  11. 		for A in product([1,-1],repeat=n):
  12. 			for B in product([1,0,0,-1],repeat=n):
  13. 				if not dotprod(A,B):
  14. 					if not dotprod(A[1:]+A[:1],B):
  15. 						numer+=1
  16. 		denom=8**n
  17. 		print n,Fraction(numer,denom)
  18.  
  19. solve1a()
  20.  
  21. def solve1b():
  22. 	for n in xrange(1,8):
  23. 		def f(i,a,b,s,t):
  24. 			if i==n:
  25. 				return not s and not t+a*b
  26.  
  27. 			res=0
  28.  
  29. 			for A in 1,-1:
  30. 				for B in 1,0,0,-1:
  31. 					res+=f(i+1,a,B,s+A*B,t+A*b)
  32.  
  33. 			return res
  34.  
  35. 		numer=0
  36.  
  37. 		for a in 1,-1:
  38. 			for b in 1,0,0,-1:
  39. 				numer+=f(1,a,b,a*b,0)
  40.  
  41. 		denom=8**n
  42.  
  43. 		print n,Fraction(numer,denom)
  44.  
  45. solve1b()
  46.  
  47. def solve2a():
  48. 	dotprod = lambda A,B: sum(a*b for a,b in zip(A,B))
  49.  
  50. 	for n in xrange(2,7):
  51. 		numer=0
  52. 		for A in product([1,-1],repeat=n):
  53. 			for B in product([1,0,0,-1],repeat=n):
  54. 				if not dotprod(A,B):
  55. 					if not dotprod(A[1:]+A[:1],B):
  56. 						if not dotprod(A[2:]+A[:2],B):
  57. 							numer+=1
  58. 		denom=8**n
  59. 		print n,Fraction(numer,denom)
  60.  
  61. solve2a()
  62.  
  63. def solve2b():
  64. 	for n in xrange(2,8):
  65. 		def f(i,a1,a2,b1,b2,s,t,u):
  66. 			if i==n:
  67. 				return not s and not t+a1*b2 and not u+a1*b1+a2*b2
  68.  
  69. 			res=0
  70.  
  71. 			for A in 1,-1:
  72. 				for B in 1,0,0,-1:
  73. 					res+=f(i+1,a1,a2,b2,B,s+A*B,t+A*b2,u+A*b1)
  74.  
  75. 			return res
  76.  
  77. 		numer=0
  78.  
  79. 		for a1 in 1,-1:
  80. 			for b1 in 1,0,0,-1:
  81. 				for a2 in 1,-1:
  82. 					for b2 in 1,0,0,-1:
  83. 						numer+=f(2,a1,a2,b1,b2,a1*b1+a2*b2,a2*b1,0)
  84.  
  85. 		denom=8**n
  86.  
  87. 		print n,Fraction(numer,denom)
  88.  
  89. solve2b()
Time limit exceeded #stdin #stdout 5s 8608KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/33Ug8a
language:
Python (cpython 2.7.16)
created:
8 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!