Organize Your Train part II

Time Limit: 1000MS Memory Limit: 65536K

Total Submissions: 5998 Accepted: 1730


RJ Freight, a Japanese railroad company for freight operations has recently constructed exchange lines at Hazawa, Yokohama. The layout of the lines is shown in Figure 1.

Figure 1: Layout of the exchange lines



POJ 3393

Lucky and Good Months by Gregorian Calendar

Time Limit: 1000MS Memory Limit: 65536K

Total Submissions: 1159 Accepted: 354


Have you ever wondered why normally an year has 365 days, not 400 days? Why August have 31 days, but February have only 28 days? Why there are 7 days, not 6 days, in a week? Do people in ancient time use the same calendar as we do? There are many interesting conjectures and theories about those problems. Now we will tell you one story that may help explaining plausible answers to these questions. Using information in the story, you are then ask to solve an interesting problem using computer. Note that there are many theories about the calendar system discussed. This problem set will tell only one of them in a simplified way.

Throughout history, people keep track of time by observing the relative positions of the earth, the moon and the sun. A day is the amount of time the earth completes a self rotation. An year is defined to be the amount of time the earth orbits the sun. The earth takes roughly 365.242190 days to orbit the sun with some small variations. For practical purpose, a calendar year needs to have an integral number of days. Hence people need to add leap days to keep the calendar synchronized with the sun. If you keep a calendar year to have 365 years, you need to add one more day in a leap year roughly about every 4 years. However, this kind of calendar will not be in perfect synchronization with the earth’s position orbiting the sun because it advanced 365.25 days in average, which is slightly more than the actual period.



以poj 1837 为例


Gigel has a strange “balance” and he wants to poise it. Actually, the device is different from any other ordinary balance.

It orders two arms of negligible weight and each arm’s length is 15. Some hooks are attached to these arms and Gigel wants to hang up some weights from his collection of G weights (1 <= G <= 20) knowing that these weights have distinct values in the range 1..25. Gigel may droop any weight of any hook but he is forced to use all the weights.

Finally, Gigel managed to balance the device using the experience he gained at the National Olympiad in Informatics. Now he would like to know in how many ways the device can be balanced.


2009 Google code jam 资格赛Problem A

Problem A. Alien Language


After years of study, scientists at Google Labs have discovered an alien language transmitted from a faraway planet. The alien language is very unique in that every word consists of exactly L lowercase letters. Also, there are exactly D words in this language.

Once the dictionary of all the words in the alien language was built, the next breakthrough was to discover that the aliens have been transmitting messages to Earth for the past decade. Unfortunately, these signals are weakened due to the distance between our two planets and some of the words may be misinterpreted. In order to help them decipher these messages, the scientists have asked you to devise an algorithm that will determine the number of possible interpretations for a given pattern.