Submeter | Todas submissőes | Melhores | Voltar |
BQUAD - Building A Fence |
Points: 250
Industrious Farmer John wants a build a four-sided fence to enclose the cows. He has one plank of wood of integer length N (4 <= N <= 2,500) that he wants to cut at three points to make four integer-length pieces.
The four pieces can be of any positive integer length as long as Farmer John can form a quadrilateral fence with them. How many different ways can he cut the plank of wood so that he can make a complete fence?
Notes
- Two ways of cutting are different if one has a cut at a spot that the other doesn't. Don't worry about eliminating symmetries or other complexities like that.
- Do make sure, though, that the fence has greater than 0 area.
- Rejoice that the answer will always fit into a signed 32-bit integer.
Input
- Line 1: A single integer: N
Output
- Line 1: A single integer that is the number of ways that Farmer John can cut the plank of wood into four pieces such that they form a valid quadrilateral.
Example
Input: 6 Output: 6
Input details
The plank of wood has length 6.
Output details
Farmer John can cut the plank 10 ways into four pieces: (1, 1, 1, 3); (1, 1, 2, 2); (1, 1, 3, 1); (1, 2, 1, 2); (1, 2, 2, 1); (1, 3, 1, 1); (2, 1, 1, 2); (2, 1, 2, 1); (2, 2, 1, 1); or (3, 1, 1, 1). Four of these -- (1, 1, 1, 3), (1, 1, 3, 1), (1, 3, 1, 1), and (3, 1, 1, 1) -- cannot be used to form a quadrilateral, though.
Adicionado por: | Wanderley Guimarăes |
Data: | 2008-10-24 |
Tempo limite: | 0.200s-0.400s |
Tamanho do fonte: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Linguagem permitida: | ADA95 DOC ASM32 BASH BF C CSHARP CPP C99 CLPS LISP sbcl LISP clisp D FORTRAN HASK ICON ICK JAVA LUA NEM NICE OCAML PAS-GPC PAS-FPC PDF PERL PHP PIKE PS PRLG-swi PYTHON RUBY SCM guile SCM qobi ST TEXT WHITESPACE |
Origem: | USACO October 2008 Qualifying Round |