I'm not sure how to approach these two problems:

http://main.edu.pl/en/archive/oi/2/obc

http://main.edu.pl/en/archive/oi/14/wag

The first one seems like some dfs, and I really have no clue about the second one (maybe dp?).

Any ideas or hints? Thanks!

First problem:

Second problem:

You want to write

A(the input) as a sum / subtraction of powers of four. Then it's a natural step to writeAin base 4. If we could only add weights to one side of the scale, knowing the optimal number of weights would be simple: just sum all digits ofA. Subtractions are annoying, so instead of using subtractions, let's introduce an alternateinversionoperation by which you can invert a contiguous sequence of digits (by invert, I mean digit = 3-digit) of the number.For example, this is 182 in base 4: 2312

Then we can use "invert" in the two middle digits to get: 2022

You can perform an inversion by adding two weights on the scale: an inversion from digit x to digit y is equivalent to adding 4

^{x + 1}- 4^{y}. We can see that inverting two overlapping segments is always equivalent to inverting two nonoverlapping segments (or sometimes zero if the segments are coincident), so the number of ways to makeAis the number of ways to select nonoverlapping segments to invert such that the overall cost to make the number is minimum. This is a problem that can solved by a DP.Can you explain the motivation behind of using this inversion operation and also why simply using this operation is correct?