Problem Statement
Manao is playing a game called "Divide and Shift". There is a sequence of N slots in the game numbered from 1 to N. Initially each of them contains an object. Manao's goal is to obtain the object which is initially in slot M. At any time of the game, he can only
obtain an object that is in slot 1 at that time. Manao can perform two types of moves. The first is choosing a prime number p which divides N and dividing the sequence of the slots in p contiguous subsequences, namely the slots from 1 to N/p, the slots from
N/p+1 to 2N/p, etc. Then, Manao keeps the subsequence which contains the desired object and gets rid of the remaining slots. The length of the chosen subsequence is then assigned to N and the slots in it are renumbered from 1 to the new value of N.
The second type of move is shifting the objects in the slots. Manao can perform a left shift and a right shift. After a left shift, for each i > 1 the object in slot i is moved to slot i-1 and the object in slot 1 is moved to the last slot of the sequence. After a right shift, each
object is moved to the slot to the right and the object in the last slot is moved to slot 1. Determine the least number of moves in which Manao can reach the goal. Taking the object from slot 1 is not considered a move.
Definition
Class:
DivideAndShift
Method:
getLeast
Parameters:
int, int
Returns:
int
Method signature:
int getLeast(int N, int M)
(be sure your method is public)
Notes
-
A positive integer number is called prime if it has exactly two divisors - 1 and itself. For example, 2, 3, 5 and 7 are prime numbers, and 4, 6, 8 and 9 are not prime. By convention, 1 is not considered to be a prime number.
-
A prime number p divides N if the ratio N/p is an integer.
Constraints
-
N will be between 1 and 1,000,000, inclusive.
-
M will be between 1 and N, inclusive.
Examples
0)
56
14
Returns: 3
One possible way to obtain the object in slot 14 is to perform the following operations: 1. Divide by 2. N becomes equal to 28 now. 2. Shift right. The object moves to slot 15. 3. Divide by 2 again. The sequence 15..28 is kept, renumbered as 1..14 and the object
appears in slot 1.
1)
49
5
Returns: 2
Manao divides by 7 twice and gets a single slot.
2)
256
7
Returns: 6
Shift left until the object is in slot 1.
3)
6
1
Returns: 0
The object may be in slot 1 right in the beginning.
4)
77777
11111
Returns: 2
///////////////////
I was UNABLE to figure out an algorithm and had to check other people's code. The following is what I copied from a guy who scored full points! It is even hard to understand the code which takes me quite some time to understand. So, here is my little question:
What might be the practical question behind this little problem. And my little wild guess is that it shows a way to calculate steps to find out some prime number. For example, let's say we have a ceiling N and we want to find out any prime number within it. Then
on average how many steps do we have to take? So, we divide the scope by a series of prime number into chunks. Then we iterate by "moving" from either side of "boundaries". That is what I thought. Or we can imagine this is a simulation for some hard drive
which is pre-divided by some prime number and need to find out how many steps to reach a particular point within some "sector". Anyway the possible application is countless. The upper limit of steps should be smaller than logN which is a binary search.
#include <iostream>
#include <string>
#include <vector>
#include <sstream>
using namespace std;
struct DivideAndShift
{
int factor(int num)
{
int result = 0;
for (int i = 2; i <= num; i ++)
{
while (num % i == 0)
{
result ++;
num /= i;
}
}
return result;
}
int getLeast(int N, int M)
{
int result = 9876543210;
for (int n = 1; n <= N; n ++)
{
if (N % n == 0)
{
int m = (M - 1) % n;
int dist = factor(N) - factor(n);
result = min(result, min(m, n - m) + dist);
}
}
return result;
}
};
int main(int argc, char** argv)
{
DivideAndShift das;
int num = 100;
if (argc == 2)
{
stringstream strStream(argv[1]);
strStream >> num;
}
for (int N = 1; N <= num; N ++)
{
cout << "N=" << N << endl;
for (int M = 2; M <= N; M ++)
{
if (das.factor(N) <= 1)
{
continue;
}
int result = das.getLeast(N, M);
if (result > 3)
{
cout << "\n******************\n";
}
cout << "M=" << M << ":"<< result << "\t";
if (result > 3)
{
cout << "\n******************\n";
}
}
cout << endl;
}
//cout<< das.getLeast(67, 5)<<endl;
return 0;
}
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
The problem is of 300 points and it is a bit difficult as it may seem:
Manhattan
can be represented as an infinite two-dimensional plane with a
Cartesian coordinate system. Manhattan is crossed by horizontal and
vertical streets parallel to the axes. Each point with integer
coordinates lies on the intersection of two streets.
Manao is
in charge of the Manhattan Police Department. He is currently
investigating patrol routes. There are N control
intersections numbered from 0 to N-1 in Manhattan. A patrol
route is a pair {A, B} of control intersections. When a squad is
completing a patrol route, it moves only along the streets and takes
the shortest path from A to B. When there are multiple shortest
paths from A to B, the squad can take any of them. Two paths
intersect if there is an intersection that belongs to both of them.
Two patrol routes intersect if no matter which paths the squads
completing them choose, these paths intersect.
You are given
ints AX, BX, MX, AY, BY, MY.
The X-coordinates of the intersections are computed as follows:
X0
= BX
Xi = (AX * Xi-1 + BX)
mod MX for 0 < i < N
Y-coordinates are
computed correspondingly using AY, BY, MY. The
X-coordinates will be pairwise distinct, as will be the
Y-coordinates.
We treat routes {A, B} and {B, A} as the same.
Consider the pairs of routes {{A, B}, {C, D}} such that all points
A, B, C and D are distinct. Return the number of such pairs which
intersect.
// basically the testing of intersection is exactly same as those testing in 2D graphic.
///////////////////////////////////////////////////////////////////////////////////////
#include <vector>
#include <string>
#include <iostream>
using namespace std;
typedef pair<int, int> IntPair;
typedef vector<pair<int, int> > IntPairVector;
class ManhattanPatrol
{
private:
bool isIntersection(const IntPair& p1, const IntPair& p2, const IntPair& p3, const IntPair& p4)
{
return
(
(
(p1.first <= p3.first && p1.first<= p4.first && p2.first >= p3.first && p2.first>=p4.first
|| p2.first <= p3.first && p2.first<= p4.first && p1.first >= p3.first && p1.first>=p4.first)
&&
(p3.second <= p1.second && p3.second<= p2.second && p4.second >= p1.second && p4.second>=p2.second
|| p4.second <= p1.second && p4.second<= p2.second && p3.second >= p1.second && p3.second>=p2.second)
)
||
(
(p3.first <= p1.first && p3.first<= p2.first && p4.first >= p1.first && p4.first>=p2.first
|| p4.first <= p1.first && p4.first<= p2.first && p3.first >= p1.first && p3.first>=p2.first)
&&
(p1.second <= p3.second && p1.second<= p4.second && p2.second >= p3.second && p2.second>=p4.second
|| p2.second <= p3.second && p2.second<= p4.second && p1.second >= p3.second && p1.second>=p4.second)
)
);
}
public:
long long countIntersections(int N, int AX, int BX, int MX, int AY, int BY, int MY)
{
IntPairVector controls;
int i, j;
int x, y;
int prevX = BX, prevY = BY;
controls.push_back(make_pair(prevX, prevY));
for (i = 0; i < N-1; i ++)
{
x = (AX*prevX + BX) % MX;
y = (AY*prevY + BY) % MY;
controls.push_back(make_pair(x, y));
prevX = x;
prevY = y;
}
long long counter = 0;
IntPairVector routes;
for (i = 0; i < controls.size()-1; i ++)
{
for (j = i + 1; j < controls.size(); j ++)
{
routes.push_back(make_pair(i, j));
}
}
/*
for (i = 0; i < controls.size(); i ++)
{
cout << i <<":("<< controls[i].first << "," << controls[i].second <<")"<<endl;
}
*/
for (i = 0; i < routes.size()-1; i ++)
{
for (j = i + 1; j < routes.size(); j ++)
{
int index1, index2, index3, index4;
index1 = routes[i].first;
index2 = routes[i].second;
index3 = routes[j].first;
index4 = routes[j].second;
if (index1 == index3 || index2 == index3 || index2 == index4 || index1 == index4)
{
continue;
}
if (isIntersection(controls[index1], controls[index2], controls[index3], controls[index4]))
{
//cout << "route("<<index1<<","<<index2 <<")intersect with ("<<index3<<","<<index4<<")"<<endl;
counter ++;
}
}
}
return counter;
}
};
