WuTao's Blog

2019 杭电多校 9 1006

题目链接：HDU 6685

比赛链接：2019 Multi-University Training Contest 9

Problem Description

Rikka hates coins, and she used to never carry any coins with her. These days, Rikka is doing her summer internship abroad. Without mobile payment, Rikka has to face strange prices of commodities, and as a result of always using paper currency, she has to face mountainous coins on here table.

In the local currency system, there are $4$ kinds of coins: $10$ cents, $20$ cents, $50$ cents and $1$ dollar. Up to now, Rikka has gained at least $10^{100}$ coins for each kind.

Now, Rikka is going to have dinner in the canteen, and she decides to pay the bill only with coins. There are $n$ different combos in the canteen and the price of the $i$th is $w_i$ cents. Rikka would like to choose one combo as dinner but she has not decided to choose which one yet. Therefore, she wants to take some coins so that whichever she chooses, she can always pay the bill without receiving any change.

Since Rikka hates coins, she wants to carry as few coins as possible with her. As it is generally known that Rikka is not good at math, she wants you to help her make the decision.

2019 杭电多校 8 1003

题目链接：HDU 6659

比赛链接：2019 Multi-University Training Contest 8

Problem Description

Acesrc is a famous mathematician at Nanjing University second to none. Playing with interesting numbers is his favorite. Today, he finds a manuscript when cleaning his room, which reads

… Let $f(d,n)$ denote the number of occurrences of digit $d$ in decimal representations of integers $1,2,3,⋯,n$. The function has some fantastic properties …

… Obviously, there exist some nonnegative integers $k$, such that $f(d,k)=k$, and I decide to call them $d$-good numbers …

… I have found all d-good numbers not exceeding $10^{1000}$, but the paper is too small to write all these numbers …

Acesrc quickly recollects all $d$-good numbers he found, and he tells Redsun a question about $d$-good numbers: what is the maximum $d$-good number no greater than $x$? However, Redsun is not good at mathematics, so he wants you to help him solve this problem.

题目链接：UVA 811

Description

Once upon a time, in a faraway land, there lived a king. This king owned a small collection of rare and valuable trees, which had been gathered by his ancestors on their travels. To protect his trees from thieves, the king ordered that a high fence be built around them. His wizard was put in charge of the operation.

Alas, the wizard quickly noticed that the only suitable material available to build the fence was the wood from the trees themselves. In other words, it was necessary to cut down some trees in order to build a fence around the remaining trees. Of course, to prevent his head from being chopped off, the wizard wanted to minimize the value of the trees that had to be cut. The wizard went to his tower and stayed there until he had found the best possible solution to the problem. The fence was then built and everyone lived happily ever after.

You are to write a program that solves the problem the wizard faced.

题目链接：POJ 1113

Description

Your friend to the south is interested in building fences and turning plowshares into swords. In order to help with his overseas adventure, they are forced to save money on buying fence posts by using trees as fence posts wherever possible. Given the locations of some trees, you are to help farmers try to create the largest pasture that is possible. Not all the trees will need to be used.

However, because you will oversee the construction of the pasture yourself, all the farmers want to know is how many cows they can put in the pasture. It is well known that a cow needs at least 50 square metres of pasture to survive.

题目链接：POJ 1113

Description

Once upon a time there was a greedy King who ordered his chief Architect to build a wall around the King’s castle. The King was so greedy, that he would not listen to his Architect’s proposals to build a beautiful brick wall with a perfect shape and nice tall towers. Instead, he ordered to build the wall around the whole castle using the least amount of stone and labor, but demanded that the wall should not come closer to the castle than a certain distance. If the King finds that the Architect has used more resources to build the wall than it was absolutely necessary to satisfy those requirements, then the Architect will loose his head. Moreover, he demanded Architect to introduce at once a plan of the wall listing the exact amount of resources that are needed to build the wall.

Your task is to help poor Architect to save his head, by writing a program that will find the minimum possible length of the wall that he could build around the castle to satisfy King’s requirements.

The task is somewhat simplified by the fact, that the King’s castle has a polygonal shape and is situated on a flat ground. The Architect has already established a Cartesian coordinate system and has precisely measured the coordinates of all castle’s vertices in feet.

题目链接：LightOJ 1203

Problem Description

Once there was a lazy monkey in a forest. But he loved banana too much. One day there was a storm in the jungle and all the bananas fell from the trees. The monkey didn’t want to lose any of the bananas. So, he wanted to find a banana such that he can eat that and he can also look after the other bananas. As he was lazy, he didn’t want to move his eyes too wide. So, you have to help him finding the banana from where he can look after all the bananas but the degree of rotating his eyes is as small as possible. You can assume that the position of the bananas can be modeled as 2D points.

Here a banana is shown, from where the monkey can look after all the bananas with minimum eye rotation.

题目链接：HDU 1392

Problem Description

There are a lot of trees in an area. A peasant wants to buy a rope to surround all these trees. So at first he must know the minimal required length of the rope. However, he does not know how to calculate it. Can you help him?

The diameter and length of the trees are omitted, which means a tree can be seen as a point. The thickness of the rope is also omitted which means a rope can be seen as a line.

There are no more than 100 trees.

题目链接：轰炸区最优选取

题目描述

现在给出一个正方形地图，其边长为n，地图上有的地方是空的，有的地方会有敌人。

我们现在有一次轰炸敌人的机会，轰炸敌人的区域是一个k*k的正方形区域，现在需要你解决的问题就是计算最多轰炸的敌人数量是多少。

题目链接：Rake It In

比赛链接：ICPC Asia Nanning 2017

Description

The designers have come up with a new simple game called “Rake It In”. Two players, Alice and Bob, initially select an integer k and initialize a score indicator. An $4 \times 4$ board is created with 16 values placed on the board. Starting with player Alice, each player in a round selects a $2 \times 2$ region of the board, adding the sum of values in the region to the score indicator, and then rotating these four values $90$ degrees counterclockwise.

After $2k$ rounds in total, each player has made decision in k times. The ultimate goal of Alice is to maximize the final score. However for Bob, his goal is to minimize the final score.

In order to test how good this game is, you are hired to write a program which can play the game. Specifically, given the starting configuration, they would like a program to determine the final score when both players are entirely rational.

题目链接：Twice Equation

比赛链接：ICPC Asia Nanning 2017

Description

For given $L$, find the smallest $n$ no smaller than $L$ for which there exists an positive integer $m$ for which $2m(m + 1) = n(n + 1)$.