pleasurepain's blog

By pleasurepain, 2 months ago, In English,

106A - Card Game

As the problem requires, we first check the suits of the given two cards. If they have the same suit, then we compare their ranks; otherwise we check whether the first card is the the trump card or not.

106B - Choosing Laptop

We can adopt a double loop to eliminate all the outdated laptops. Next, we find the cheapest one as the answer.

106C - Buns

At first, I tried to solve it based on greedy algorithm. However, it turns out that such a greedy algorithm fails since all the involved numbers are integers...

Well, this is essentially a backpack problem, if we implement some equivalent transformation. More specifically, it is a multiple-backpack problem, one can also check the one in 95E - Lucky Country, which is also solved based on multiple-backpack.

106D - Treasure Island

The solution is straightforward implementation. However, trivial implementation ends up with TLE. To avoid this, for each position, we should calculate in previous the farthest position that we can reach when we move to any one of the four directions. This can be computed by using DP algorithm with complexity O(mn).

 
 
 
 
  • Vote: I like it  
  • -5
  • Vote: I do not like it