## Wednesday, September 1, 2010

### poj_1961_Period.cpp

poj1961, spoj00263,

## Problem:

Period
 Time Limit: 3000MS Memory Limit: 30000K Total Submissions: 6886 Accepted: 2977
Description
For each prefix of a given string S with N characters (each character has an ASCII code between 97 and 126, inclusive), we want to know whether the prefix is a periodic string. That is, for each i (2 <= i <= N) we want to know the largest K > 1 (if there is one) such that the prefix of S with length i can be written as AK ,that is A concatenated K times, for some string A. Of course, we also want to know the period K.

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;
}

poj1862,

## Problem:

Stripies
 Time Limit: 1000MS Memory Limit: 30000K Total Submissions: 7922 Accepted: 3939
Description
Our chemical biologists have invented a new very useful form of life called stripies (in fact, they were first called in Russian - polosatiki, but the scientists had to invent an English name to apply for an international patent). The stripies are transparent amorphous amebiform creatures that live in flat colonies in a jelly-like nutrient medium. Most of the time the stripies are moving. When two of them collide a new stripie appears instead of them. Long observations made by our scientists enabled them to establish that the weight of the new stripie isn't equal to the sum of weights of two disappeared stripies that collided; nevertheless, they soon learned that when two stripies of weights m1 and m2 collide the weight of resulting stripie equals to 2*sqrt(m1*m2). Our chemical biologists are very anxious to know to what limits can decrease the total weight of a given colony of stripies.

poj1833,

## Problem:

 Time Limit: 1000MS Memory Limit: 30000K Total Submissions: 9723 Accepted: 4297
Description

Input

Output

Sample Input
```3
3 1
2 3 1
3 1
3 2 1
10 2
1 2 3 4 5 6 7 8 9 10```
Sample Output
```3 1 2
1 2 3
1 2 3 4 5 6 7 9 8 10```
Source
qinlu@POJ

## Solution:

sort simulation;

1、考虑最大的排列的下一个排列是最小的排列，如5 4 3 2 1的下一个排列是1 2 3 4 5;
2、考虑效率，输入输出用scanf和printf，用cin和cout会超时.

## Source Code:

//Mon Apr 26 05:13:30 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 cmp ( const void *a , const void *b )
{
return *(int *)a - *(int *)b;
}

void getNext(int v[], int n)
{
int i, j;
if (1 == n)
return;
for (i = n - 2; i >= 0; i--)
{
if (v[i] < v[i + 1])
break;
}
//Check if it's the inverse order;
if (i < 0)
{
for (j = 0; j < n; j++)
v[j] = j + 1;
return;
}
//find the min from i+1 to the end;
int idx = i + 1;
for (j = i + 2; j < n; j++)
{
if (v[j] < v[idx] && v[j] > v[i])
idx = j;
}
//Swap;
int tmp = v[idx];
v[idx] = v[i];
v[i] = tmp;
//  sort(v.begin() + i + 1, v.end());
qsort(v + i + 1, n-1-i, sizeof(v), cmp);
}

int main(int argc, const char* argv[])
{
//  freopen("input.in", "r", stdin);
//  freopen("output.out", "w", stdout);
int N;
scanf("%d", &N);

for (int ncase = 0; ncase < N; ncase++)
{
int m, k;
scanf("%d%d", &m, &k);
int v;
for (int i = 0; i < m; i++)
{
scanf("%d", &v[i]);
}
for (int i = 0; i < k; i++)
{
getNext(v, m);
}
for (int i = 0; i < m; i++)
{
if (i != 0)
printf(" ");
printf("%d", v[i]);
}
printf("\n");
}

//  fclose(stdin);
//  fclose(stdout);
return 0;
}

poj1723,

## Problem:

SOLDIERS
 Time Limit: 1000MS Memory Limit: 10000K Total Submissions: 4758 Accepted: 1761
Description
N soldiers of the land Gridland are randomly scattered around the country.
A position in Gridland is given by a pair (x,y) of integer coordinates. Soldiers can move - in one move, one soldier can go one unit up, down, left or right (hence, he can change either his x or his y coordinate by 1 or -1).

poj1716,

## Problem:

Integer Intervals
 Time Limit: 1000MS Memory Limit: 10000K Total Submissions: 8722 Accepted: 3644
Description
An integer interval [a,b], a < b, is a set of all consecutive integers beginning with a and ending with b.
Write a program that: finds the minimal number of elements in a set containing at least two different integers from each interval.

poj1703,

## Problem:

Find them, Catch them
 Time Limit: 1000MS Memory Limit: 10000K Total Submissions: 15702 Accepted: 4620
Description
The police office in Tadu City decides to say ends to the chaos, as launch actions to root up the TWO gangs in the city, Gang Dragon and Gang Snake. However, the police first needs to identify which gang a criminal belongs to. The present question is, given two criminals; do they belong to a same clan? You must give your judgment based on incomplete information. (Since the gangsters are always acting secretly.)