Problem Links:
poj1879,
Problem:
Tempus et mobilius Time and motion
| Time Limit: 1000MS |
| Memory Limit: 30000K |
| Total Submissions: 599 |
| Accepted: 355 |
Description
Tempus est mensura motus rerum mobilium.
Time is the measure of movement.--Auctoritates Aristotelis
...and movement has long been used to measure time. For example, the
ball clock is a simple device which keeps track of the passing minutes
by moving ball-bearings. Each minute, a rotating arm removes a ball
bearing from the queue at the bottom, raises it to the top of the clock
and deposits it on a track leading to indicators displaying minutes,
five-minutes and hours. These indicators display the time between 1:00
and 12:59, but without 'a.m.' or 'p.m.' indicators. Thus 2 balls in the
minute indicator, 6 balls in the five-minute indicator and 5 balls in
the hour indicator displays the time 5:32.
Unfortunately, most commercially available ball clocks do not
incorporate a date indication, although this would be simple to do with
the addition of further carry and indicator tracks. However, all is not
lost! As the balls migrate through the mechanism of the clock, they
change their relative ordering in a predictable way. Careful study of
these orderings will therefore yield the time elapsed since the clock
had some specific ordering. The length of time which can be measured is
limited because the orderings of the balls eventually begin to repeat.
Your program must compute the time before repetition, which varies
according to the total number of balls present.
Operation of the Ball Clock
Every minute, the least recently used ball is removed from the queue
of balls at the bottom of the clock, elevated, then deposited on the
minute indicator track, which is able to hold four balls. When a fifth
ball rolls on to the minute indicator track, its weight causes the track
to tilt. The four balls already on the track run back down to join the
queue of balls waiting at the bottom in reverse order of their original
addition to the minutes track. The fifth ball, which caused the tilt,
rolls on down to the five-minute indicator track. This track holds
eleven balls. The twelfth ball carried over from the minutes causes the
five-minute track to tilt, returning the eleven balls to the queue,
again in reverse order of their addition. The twelfth ball rolls down to
the hour indicator. The hour indicator also holds eleven balls, but has
one extra fixed ball which is always present so that counting the balls
in the hour indicator will yield an hour in the range one to twelve.
The twelfth ball carried over from the five-minute indicator causes the
hour indicator to tilt, returning the eleven free balls to the queue, in
reverse order, before the twelfth ball itself also returns to the
queue.
Input
The
input defines a succession of ball clocks. Each clock operates as
described above. The clocks differ only in the number of balls present
in the queue at one o'clock when all the clocks start. This number is
given for each clock, one per line and does not include the fixed ball
on the hours indicator. Valid numbers are in the range 27 to 127. A zero
signifies the end of input.
Output
Output
For each clock described in the input, your program should report the
number of balls given in the input and the number of days (24-hour
periods) which elapse before the clock returns to its initial ordering.
Sample Input
30
45
0
Sample Output
30 balls cycle after 15 days.
45 balls cycle after 378 days.
Source
World Finals 1995
Solution:
1st, consider the position situation after 24 hours (A Day),
2nd, you can get the period for each ball to get back to the original position.
3rd, Take the least common multiple.
PS:
1. Take care of the red marked part of the code, that's the way how to get the period for each ball. That's a smart way to calculate.
2. When calculate the position situation after 24 hours, take care of the number of ball each track can take.
Source Code:
//Mon Apr 26 03:42:02 CDT 2010
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
using namespace std;
int gcd(int xx, int yy)
{
if (yy != 0)
return gcd(yy, xx % yy);
return xx;
}
int main(int argc, const char* argv[])
{
// freopen("input.in", "r", stdin);
// freopen("output.out", "w", stdout);
int N;
while (cin >> N && N)
{
queue<int> All;
stack<int> minute, fives, hour;
for (int i = 0; i < N; i++)
{
All.push(i);
}
int mins = 60 * 24;
while (mins--)
{
int now = All.front();
All.pop();
if (4 != minute.size())
{
minute.push(now);
}
else
{
for (int i = 0; i < 4; i++)
{
All.push(minute.top());
minute.pop();
}
if (11 != fives.size())
{
fives.push(now);
}
else
{
for (int i = 0; i < 11; i++)
{
All.push(fives.top());
fives.pop();
}
if (11 != hour.size())
{
hour.push(now);
}
else
{
for (int i = 0; i < 11; i++)
{
All.push(hour.top());
hour.pop();
}
All.push(now);
}
}
}
}
vector<int> src(N);
for (int i = 0; i < N; i++)
{
src[i] = All.front();
All.pop();
// cout << src[i];
}
// cout << endl;
vector<int> count(N, 1);
for (int i = 0; i < N; i++)
{
int tmp = src[i];
while (tmp != i)
{
tmp = src[tmp];
count[i]++;
}
}
int product = 1;
for (int i = 0; i < N; i++)
{
product = product * count[i] / gcd(count[i], product);
}
cout << N << " balls cycle after " << product << " days." << endl;
}
// fclose(stdin);
// fclose(stdout);
return 0;
}
