标签归档:KMP

[poj 2185] Milking Grid

Description

Every morning when they are milked, the Farmer John's cows form a rectangular grid that is R (1 <= R <= 10,000) rows by C (1 <= C <= 75) columns. As we all know, Farmer John is quite the expert on cow behavior, and is currently writing a book about feeding behavior in cows. He notices that if each cow is labeled with an uppercase letter indicating its breed, the two-dimensional pattern formed by his cows during milking sometimes seems to be made from smaller repeating rectangular patterns.

Help FJ find the rectangular unit of smallest area that can be repetitively tiled to make up the entire milking grid. Note that the dimensions of the small rectangular unit do not necessarily need to divide evenly the dimensions of the entire milking grid, as indicated in the sample input below.

继续阅读

AIO2009 Solution

Travelling Salesperson

Even in uncertain economic times, no home can be without electrical appliances. Realising that there is still a sales opportunity, you have recently taken up a part-time job selling electrical appliances the old fashioned way--travelling door to door. However, your hometown of Perth is full of electrical salespeople who have cornered the market, and so you must travel across Australia to find customers.

You will start in your hometown, Perth, drive across Australia to Sydney, and then back again to Perth. There are three routes between Perth and Sydney. In your market research, you have counted the number of customers living along each route. You wish to plan your trip to Sydney and back so that you visit the greatest number of customers possible. You must take a different route on the return journey, otherwise you would simply end up visiting the same satisfied customers twice.

Your task is to write a program which, given the number of customers along each of the three routes between Perth and Sydney, determines the greatest number of customers you can visit by travelling from Perth to Sydney and back.

继续阅读