Solving problems between finals :-)

This week is a dead week in our university. There is a policy that restricts professors from giving quizes or midterms during this week. So, instead they just give a lot of homeworks and you are overloaded with deadlines. Some of the homeworks are boring and so, I entertain myself by solving problems in between.
Here are the problems for today:
1004. Sightseeing trip
Given undirected weighted graph, the problem asks to find simple cycle (you can visit vertex only once) with minimum weight . At the beginning it seems you have to consider all possible cycles and choose the one with minimum weight. You can use Dijsktra's algorithm here though. Just try to delete every possible edge and then find minimum path between nodes of the deleted edge. The cost of such cycle is the weight of minimum path + cost_of_deleted_edge. That was enough to get AC.

1014. The Product of Digits
Simple number-theoretic problem. :-) First, realize that if prime factorization of the integer N has any prime that is bigger than 7, then answer is "-1". Otherwise do simple prime factorization and figure out the degrees of 2, 3, 5 and 7. Suppose these numbers are K2, K3, K5 and K7 respectively. Observe that in order to find the smallest integer it has to be as short (in terms of number of digits) as possible. So, we will be constructing our answer from the end in the following way:
first put K3/2 nines in the end and set K3=K3%2,
next put K2/3 eights before nines and set K2=K2%3,
next put K7 sevens before eights,
next if K2>0 and K3>0 put single six before sevens and set K2=K2-1 and K3=K3-1,
next put K5 fives before in the similar way,
next if K2=2 put single four,
next if K3>0 put single three,
finally if K2=1 put single one.
Also need to handle special case when N=0 or N=1.
That's it.

Bruteforce problem

1005. Stone pile (acm.timus.ru).
Just a bruteforce problem. Generate all possible splits of the stones into two piles and select the best.

Couple of DP problems

1018. A Binary Apple Tree (acm.timus.ru)
This was an easy DP problem. The state of the DP is the following: root of the subtree and how many edges we need, in other words dp[node][need] - is the maximum amount of apples that we can preserve if the root of our tree is at the node and we will leave "need" edges. The only tricky part of this problem is that the given input is not necessarily a rooted tree and so after reading the input you have to construct the tree properly.

1002. Phone number (acm.timus.ru)
Another simple DP problem. Let's say S[1..L] is the first L digits of the call number. Let D[L] be the minimum number of words that we can use to split S[1..L]. Obviously, D[0]=0 and D[L]=INFINITY, if we cannot split S[1..L]. In order to compute D[L] we look at S[L..L], S[L-1..L], S[L-2..L], .. up to S[L-49..L] (because there are no words of length more than 50) and check if there are words that match these substrings. For every word matched we try to improve our D[L] in the following way D[L]=min(D[L],D[J]+1), where J=L-(length_of_currently_matched_word). You also have to figure out a fast way to check whether there exists a word that matches certain S[I..J]. This can be done by either creating a c++ map that associates a certain digit sequence with a word or coding your own hashing in pascal.
Also in order to construct the answer we need remember for each L the value of J that D[L] archives the minimum.

First AC-s

Welcome everyone!
I plan on posting here most of the ideas, approaches or hints to the problems that I will solve in near future on any online judge.

Here is the first and problem that I solved today:
1000. A+B Problem (acm.timus.ru).
Basically you have to find sum of two integers. Luckily those integers aren't negative, but unluckily they might not fit into 32-bit variables. So, you should recall your school method for adding two numbers or you can use java's nice BigInteger class(No cheating - I did the former:) .

1001. Reverse Root (acm.timus.ru).
Just do what the problem asks. Beware of the reverse order though...