WuTao's Blog

while(!(succeed = try()));

0%

发表于 更新于 分类于 阅读次数： Valine：
本文字数： 2.9k 阅读时长 ≈ 3 分钟

Codeforces Round #574 (Div. 2)

题目链接：E. OpenStreetMap

Seryozha conducts a course dedicated to building a map of heights of Stepanovo recreation center. He laid a rectangle grid of size $n×m$ cells on a map (rows of grid are numbered from $1$ to $n$ from north to south, and columns are numbered from $1$ to $m$ from west to east). After that he measured the average height of each cell above Rybinsk sea level and obtained a matrix of heights of size $n×m$. The cell $(i,j)$ lies on the intersection of the $i$-th row and the $j$-th column and has height $h_{i,j}$.

Seryozha is going to look at the result of his work in the browser. The screen of Seryozha’s laptop can fit a subrectangle of size $a×b$ of matrix of heights $(1≤a≤n, 1≤b≤m)$. Seryozha tries to decide how the weather can affect the recreation center — for example, if it rains, where all the rainwater will gather. To do so, he is going to find the cell having minimum height among all cells that are shown on the screen of his laptop.

Help Seryozha to calculate the sum of heights of such cells for all possible subrectangles he can see on his screen. In other words, you have to calculate the sum of minimum heights in submatrices of size $a×b$ with top left corners in $(i,j)$ over all $1≤i≤n−a+1$ and $1≤j≤m−b+1$.

Consider the sequence $g_i=(g_{i−1}⋅x+y) mod z$. You are given integers $g0$, $x$, $y$ and $z$. By miraculous coincidence, $h_{i,j}=g_{(i−1)⋅m+j−1}$ ($(i−1)⋅m+j−1$ is the index).

阅读全文 »

发表于 更新于 分类于 阅读次数： Valine：
本文字数： 2.5k 阅读时长 ≈ 2 分钟

题目链接：POJ 2001

Description

A prefix of a string is a substring starting at the beginning of the given string. The prefixes of “carbon” are: “c”, “ca”, “car”, “carb”, “carbo”, and “carbon”. Note that the empty string is not considered a prefix in this problem, but every non-empty string is considered to be a prefix of itself. In everyday language, we tend to abbreviate words by prefixes. For example, “carbohydrate” is commonly abbreviated by “carb”. In this problem, given a set of words, you will find for each word the shortest prefix that uniquely identifies the word it represents.

In the sample input below, “carbohydrate” can be abbreviated to “carboh”, but it cannot be abbreviated to “carbo” (or anything shorter) because there are other words in the list that begin with “carbo”.

An exact match will override a prefix match. For example, the prefix “car” matches the given word “car” exactly. Therefore, it is understood without ambiguity that “car” is an abbreviation for “car” , not for “carriage” or any of the other words in the list that begins with “car”.

阅读全文 »

发表于 更新于 分类于 阅读次数： Valine：
本文字数： 1.6k 阅读时长 ≈ 1 分钟

Codeforces Round #320 (Div. 1) [Bayan Thanks-Round]

题目链接：B. “Or” Game

You are given $n$ numbers $a_1, a_2, …, a_n$. You can perform at most $k$ operations. For each operation you can multiply one of the numbers by $x$. We want to make $a_1 | a_2 | … | a_n$ as large as possible, where $|$ denotes the bitwise OR.

Find the maximum possible value of $a_1 | a_2 | … | a_n$ after performing at most $k$ operations optimally.

阅读全文 »

发表于 更新于 分类于 阅读次数： Valine：
本文字数： 2.1k 阅读时长 ≈ 2 分钟

题目链接：Fruit Ninja
比赛链接：2018 ACM 国际大学生程序设计竞赛上海大都会赛重现赛

题目描述

Fruit Ninja is a juicy action game enjoyed by millions of players around the world, with squishy,

splat and satisfying fruit carnage! Become the ultimate bringer of sweet, tasty destruction with every slash.

Fruit Ninja is a very popular game on cell phones where people can enjoy cutting the fruit by touching the screen.

In this problem, the screen is rectangular, and all the fruits can be considered as a point. A touch is a straight line cutting

thought the whole screen, all the fruits in the line will be cut.

A touch is EXCELLENT if $\frac{M}{N} \ge x$, ($N$ is total number of fruits in the screen, $M$ is the number of fruits that cut by the touch, $x$ is a real number.)
Now you are given $N$ fruits position in the screen, you want to know if exist a EXCELLENT touch.

阅读全文 »

发表于 更新于 分类于 阅读次数： Valine：
本文字数： 1.8k 阅读时长 ≈ 2 分钟

题目链接：HDU 1700

Problem Description

There is a cycle with its center on the origin.

Now give you a point on the cycle, you are to find out the other two points on it, to maximize the sum of the distance between each other

you may assume that the radius of the cycle will not exceed 1000.

阅读全文 »

发表于 更新于 分类于 阅读次数： Valine：
本文字数： 1.7k 阅读时长 ≈ 2 分钟

Codeforces Global Round 2

题目链接：

E. Pavel and Triangles

Pavel has several sticks with lengths equal to powers of two.

He has $a_0$ sticks of length $2^0=1$, $a1$ sticks of length $2^1=2$, …, $a_{n−1}$ sticks of length $2^{n−1}$.

Pavel wants to make the maximum possible number of triangles using these sticks. The triangles should have strictly positive area, each stick can be used in at most one triangle.

It is forbidden to break sticks, and each triangle should consist of exactly three sticks.

Find the maximum possible number of triangles.

阅读全文 »