Это не домашнее задание, а скорее мое намерение узнать, требуется ли это для изучения программирования. Я продолжаю входить в TopCoder, чтобы не участвовать, а получить общее представление о том, как решаются проблемы. Но, насколько мне известно, я не понимаю, в чем проблема и как перевести проблему в алгоритм, который может ее решить.
Просто сейчас я смотрю на ACM ICPC 2010 World Finals, который проводится в Китае. Команды получили наборы задач, и одна из них такова:
Given at most 100 points on a plan with distinct x-coordinates,
find the shortest cycle that passes through each point exactly once,
goes from the leftmost point always to the right until it reaches the
rightmost point, then goes always to the left until it gets back to the
leftmost point. Additionally, two points are given such that the the path
from left to right contains the first point, and the path from right to
left contains the second point. This seems to be a very simple DP: after
processing the last k points, and with the first path ending in point a
and the second path ending in point b, what is the smallest total length
to achieve that? This is O(n^2) states, transitions in O(n). We deal
with the two special points by forcing the first path to contain the first
one, and the second path contain the second one.
Теперь я понятия не имею, что я должен решить после прочтения поставленной задачи.
а есть еще один из Google Code Jam:
Problem
In a big, square room there are two point light sources:
one is red and the other is green. There are also n circular pillars.
Light travels in straight lines and is absorbed by walls and pillars.
The pillars therefore cast shadows: they do not let light through.
There are places in the room where no light reaches (black), where only
one of the two light sources reaches (red or green), and places where
both lights reach (yellow). Compute the total area of each of the four
colors in the room. Do not include the area of the pillars.
Input
* One line containing the number of test cases, T.
Each test case contains, in order:
* One line containing the coordinates x, y of the red light source.
* One line containing the coordinates x, y of the green light source.
* One line containing the number of pillars n.
* n lines describing the pillars. Each contains 3 numbers x, y, r.
The pillar is a disk with the center (x, y) and radius r.
The room is the square described by 0 ≤ x, y ≤ 100. Pillars, room
walls and light sources are all disjoint, they do not overlap or touch.
Output
For each test case, output:
Case #X:
black area
red area
green area
yellow area
Требуется ли, чтобы люди, которые программируют, были в состоянии решить проблемы такого типа?
Буду признателен, если кто-нибудь сможет мне помочь с интерпретацией проблемы с застреванием кода в Google, так как я хочу участвовать в этом году Code Jam, чтобы посмотреть, смогу ли я выполнить муравейник или нет.
Спасибо.