269 - Counting Patterns
Moderator: Board moderators
[269 ]Counting Patterns ,TLE
I got TLE in this problem ,what's the algo for it,just only burte force?
-
- Guru
- Posts: 724
- Joined: Wed Dec 19, 2001 2:00 am
- Location: Germany
I'm not sure how good you are at programming, but this question has a VERY VERY low submission count (70+) and only 16 people got it correct.. so unless you are really quite experienced at brute force, you shouldn't be too worried if you cannot solve it within time limit.zizi wrote:wat's smart burte force
Anyway, "smart brute force" generally means pruning.. if you visual the paths taken by an exhaustive search, it is in the form of a tree. Pruning simply means removing parts of the tree. How and which branch to remove is the "smart" part.
![:)](./images/smilies/icon_smile.gif)
-
- Guru
- Posts: 647
- Joined: Wed Jun 26, 2002 10:12 pm
- Location: Hong Kong and New York City
- Contact:
269 - Counting Patterns
How many sequence for:
I get:
1
11
30
285
1558
8221
28227
60638
61121
19586
655
Thanks.
Code: Select all
1 11
2 10
3 9
4 8
5 7
6 6
7 5
8 4
9 3
10 2
11 1
1
11
30
285
1558
8221
28227
60638
61121
19586
655
Thanks.
-
- Guru
- Posts: 724
- Joined: Wed Dec 19, 2001 2:00 am
- Location: Germany
Could someone verify my I/O test ?
input:
output:
And the sequence for :
I get
Thanks in advance.
input:
Code: Select all
1 3
3 0
2 2
3 3
3 4
4 3
Code: Select all
1
(0)
1
(0,0,0)
3
(0,0)
(1,-1)
(2,-2)
6
(0,0,0)
(1,0,-1)
(2,-1,-1)
(2,0,-2)
(3,-1,-2)
(3,0,-3)
9
(0,0,0)
(1,0,-1)
(2,-1,-1)
(2,0,-2)
(3,-1,-2)
(3,0,-3)
(4,-2,-2)
(4,-1,-3)
(4,0,-4)
30
(0,0,0,0)
(1,-1,1,-1)
(1,0,-1,0)
(1,0,0,-1)
(1,1,-1,-1)
(2,-2,2,-2)
(2,-1,0,-1)
(2,-1,1,-2)
(2,0,-2,0)
(2,0,-1,-1)
(2,0,0,-2)
(2,1,-2,-1)
(2,1,-1,-2)
(2,2,-2,-2)
(3,-3,3,-3)
(3,-2,1,-2)
(3,-2,2,-3)
(3,-1,-1,-1)
(3,-1,0,-2)
(3,-1,1,-3)
(3,0,-3,0)
(3,0,-2,-1)
(3,0,-1,-2)
(3,0,0,-3)
(3,1,-3,-1)
(3,1,-2,-2)
(3,1,-1,-3)
(3,2,-3,-2)
(3,2,-2,-3)
(3,3,-3,-3)
Code: Select all
5 5
5 4
7 3
3 7
8 3
Code: Select all
483
228
2281
20
13023
-
- Experienced poster
- Posts: 209
- Joined: Sun Jan 16, 2005 6:22 pm
Because (2, -1, -1, 0) is equivalent to (2, 0, -1. -1).
Code: Select all
(2, 0, -1, -1) --rule(a)--> (0, -1, -1, 2) --rule(b)--> (2, -1, -1, 0)