SettingTents
SRM 433 · 2009-01-21 · by gojira_tc
Problem Statement
Once upon a time, there lived a migrant barbarian tribe. Every time it settled down, a tent was set for the chief of the tribe. First, an area was selected and divided into NxM squares with side lengths of 1 unit. Then, they chose a site for the tent in such a way that every vertex of its base coincided with some vertex of one of the squares. According to an ancient tradition, the base had to be a rhomb. For example, there are all 6 different possible sites for the tent in a 2x2 area:
An example of a tent in a 4x2 area:
For a given N and M, return the number of different possible sites for the chief's tent. Two sites are different if there is at least one vertex which belongs to one site but not the other.
Notes
- A rhomb is a four-sided polygon with sides of equal length.
- The tent must have non-zero area.
Constraints
- N will be between 1 and 100, inclusive.
- M will be between 1 and 100, inclusive.
2 2 Returns: 6
The example from the problem statement.
1 6 Returns: 6
The only possible sites are the squares of the area themselves.
6 8 Returns: 527
100 100 Returns: 38235298
98 99 Returns: 35869694
Submissions are judged against all 78 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class SettingTents with a public method int countSites(int N, int M) · 78 test cases · 2 s / 256 MB per case