Problems from VOI 2016
Разница между en2 и en3, 56 символ(ов) изменены
VOI (Vietnam National Olympiad in Informatics) 2016 has just ended a few hours ago. You are given 6 problems (3 each day) to solve in the time of 180 minutes per day. As a contestant, I must say for such a small window of time I just couldn't do them all. Anyways here are the (of course, shortened version of) statements of the problems.  ↵

The problems have a total score of 40, which divides to 6 / 7 / 7 per day.↵

### Day 1↵

#### Problem 1 (6 pts)↵
You are given a sequence of numbers $A[1..n]$ ($1 \le A_i \le 10^9$). You have to erase the least amount of numbers in the sequence such that for every $i < j$ in the new sequence the following condition holds: $|A_i - A_j| \notin \{1, 8, 9\}$.↵

50% of the tests have $n \le 20$. The remaining have $n \le 2000$.↵

#### Problem 2 (7 pts)↵
There is a road which has a length of $L$. You have a truck with the fuel tank capacity of $K$, and 
have to deliverstart off with $Q$ litres of fuel fromat one side (point 0) which you will have to deliver to the other side (point L) of the road. Your truck consumes 1 litre of fuel per unit of length it travels. In order to help you, starting from point 0 there is a fuel tank with unlimited capacity every $D$ units of length (so there are tanks on point $D$, $2D$, ... and they are empty at start). You are allowed to transfer the fuel in and out of any tank. Maximize the amount of fuel you can deliver to point $L$.↵

Given $L$, $K$, $Q$, $D$, calculate the maximum amount of fuel you can deliver to point $L$.↵

Constraints: $1 \le L, K, D \le 10^9$, $1 \le Q \le 10^{12}$. On the first 50% of the tests $\dfrac{L}{D} \le 10^4$.↵

#### Problem 3 (7 pts)↵
You are given an undirected connected graph $G(V, E)$ of $n$ vertices and $m$ edges (with no self edges and multi-edges) and the following algorithm to construct $K$:↵

- First, initialize $K[1..n]$ as an array of empty vectors of integers. Let $K[1] = {0}$. ↵

- Let $f[1..n]$ be an array of booleans, all being false at start. Let $Q$ be a set of indices $i$ such that $f[i] = false$ and $|K[i]| > 0$↵

- While $|Q| > 0$:↵

    - Let $u$ be the smallest number in $Q$. Set $f[u] = true$↵

    - For each edge $(u, v)$ in $G$ such that $f[v] = false$ we append $u$ into back of $K[v]$.↵

Please renumber all the vertices in the graph so that for the resulting array $K$ of the algorithm the following condition holds: For every $u < v$ we have $K[u] \le K[v]$ alphabetically. ↵

Constraints: 40% of the tests have $n \le 10$. 80% of the tests have $n \le 10^3, m \le 10^4$. All tests have $n \le 2 \times 10^4, m \le 10^6$.↵

### Day 2↵

#### Problem 1 (6 pts)↵
You are given a grid of $n \times m$ cells, each containing a zero or one. Find the diamond-shaped area (which has to be fully inside the grid) containing the most ones such that no two one cells inside the area share the same edge.↵

A diamond-shaped area with center $(x_0, y_0)$ and radius $r$ is a set of cells $(x, y)$ which satisfies $|x - x_0| + |y - y0| \le r$.↵

Constraints: 40% of the tests have $n \le 100$. 80% of the tests have $n \le 500$. All tests have $n \le 1000$.↵

#### Problem 2 (7 pts)↵
You are given a set of $n$ operations containing at most 4 numbers within $[0..10^6]$ and operators `+`, `-`, `*`. You have add brackets to some of the equations such that each of them has an unique value. ↵

Constraints: 50% of the tests have $n \le 20$ and operations having at most 3 numbers. All tests have $n \le 2000$.↵

#### Problem 3 (7 pts)↵
You are given $n$ trees (real world trees) with the $i$-th tree having height $h_i$ and stands at position $i$ and you have to fall down all of them. Falling the tree $i$ to the left causes all trees $j$ with $i - h_i < j < i$ to fall to the left, and falling tree $i$ to the right causes all trees $j$ with $i < j < i + h_i$ to fall to the right (and they to make chains like dominoes). Find a way of cutting the trees such that the number of trees manually fell at minimized.↵

All trees have height not exceeding $4 \times 10^6$ ↵

Constraints: 40% of the tests have $n \le 10^4$, 80% of the tests have $n \le 10^5$, all tests have $n \le 4 \times 10^6$

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en3 Английский natsukagami 2016-01-11 22:08:34 56 Clarify day 1 problem 2's statement.
en2 Английский natsukagami 2016-01-07 11:38:38 14 Minor Grammar edits
en1 Английский natsukagami 2016-01-07 11:18:25 4139 Initial revision (published)