SimpleMazeEasy
SRM 723 · 2017-11-17 · by cgy4ever
SRM 723 · 2017-11-17 · by cgy4ever · Math
Problem Statement
Problem Statement
A level-n simple maze consists of five squares arranged into the shape of a cross.
Each square consists of n times n rooms, each having the shape of a unit square.
Simple mazes of level 1 and level 3 are shown below, with each '.' representing one cell.
In a single step you can move from your current room into any room that shares a side with your room. The distance between two rooms is the smallest number of steps needed to get from one room to the other.
You are given thelong n.
Consider the level-n simple maze.
For each pair of rooms compute their distance.
Let S be the sum of all those distances.
Compute and return the value S modulo (10^9 + 7).
. ... . ... ... ... ......... ......... ......... ... ... ...
In a single step you can move from your current room into any room that shares a side with your room. The distance between two rooms is the smallest number of steps needed to get from one room to the other.
You are given the
Constraints
- n will be between 1 and 1,000,000,000,000,000,000 (10^18), inclusive.
Examples
0)
1 Returns: 16
The level-1 simple maze consists of five rooms. There are four pairs of adjacent rooms (i.e., distance = 1). There are six pairs of rooms that are at distance 2. Thus, the sum of all distances is 4*1 + 6*2 = 16.
1)
3 Returns: 4680
2)
5 Returns: 61000
3)
12345 Returns: 598011702
don't forget mod.
4)
1000000000000 Returns: 763641672
Submissions are judged against all 73 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class SimpleMazeEasy with a public method int findSum(long long n) · 73 test cases · 2 s / 256 MB per case