Weekly Contest 1 - UM ICPC Training Group

2022-10-30 00:39 作者:安然Nano 0人讀過(guò) | 我要投稿

頭文件

A - Roaming Romans

The English word “mile” derives from the Latin “mille passus”, meaning “a thousand paces”. A Roman mile was the distance a soldier would walk in?1000?paces (a pace being two steps, one with each foot).

Over time, the actual distance referred to as a “mile” has changed. The modern English mile is?5280?(modern) feet. The Roman mile is believed to have been about?4854?(modern) feet. Therefore a distance of? $x$ ??English miles would correspond to? $1000%5Ccdot%20%5Cfrac%7B1000%7D%7B4854%7D%20$ ?Roman paces.

Write a program to convert distances in English miles into Roman paces.

Input

Input will consist of a single line containing a single real number? $0%20%5Cleq%20X%20%5Cleq%201000$ ??denoting a distance in English miles. The number? $X$ ?has at most?3?digits of precision after the decimal point.

Output

Print an integer denoting the closest number of Roman paces equivalent to $X$ . Your answer should be rounded to the closest integer (with an exact?.5?decimal part rounded up).

Sample

標(biāo)準(zhǔn)模擬題，按照公式轉(zhuǎn)換即可。

B - Harshad Numbers

We’re all familiar with harshad numbers. For this problem, you will ... what’s that? You?aren’t?familiar with harshad numbers? They’re also known as Niven numbers – does that ring a bell?? Anything???

Well, it’s a simple enough concept. A?harshad?number is a number which is evenly divisible by the sum of its digits. For example,?24?is a harshad number: the sum of its digits is? $2%2B4%3D6$ ?and?24?is divisible by?6.?156?is also a harshad number, since? $1%2B5%2B6%3D12$ ?and? $156%3D(12)(13)$ .?157?is NOT a harshad number since it is not divisible by? $1%2B5%2B7%3D13$ .

OK, let’s start over.

We’re all familiar with harshad numbers. For this problem, you will be given a number? $n$ ?and must find the smallest harshad number? $%5Cgeq%20n$ .

Inpute

Input consists of a single line containing a positive integer? $%20n%20%5Cleq%201%5C%2C%20000%5C%2C%20000%5C%2C%20000$

Output

Display the smallest harshad number greater than or equal to? $n$ .

Sample

模擬題。如果一個(gè)數(shù)可以整除其每位數(shù)之和，這個(gè)數(shù)就稱(chēng)為Harshad Number。給一個(gè)數(shù)，讓求大于等于這個(gè)數(shù)的Harshad Number。

C - Increasing Array

You are given an array of? $n$ ?integers. You want to modify the array so that it is increasing, i.e., every element is at least as large as the previous element.
On each move, you may increase the value of any element by one. What is the minimum number of moves required?
Input
The first input line contains an integer $n$ : the size of the array.

Then, the second line contains? $n n$ ?integers? $x_1%2Cx_2%2C%5Cldots%2Cx_n$ : the contents of the array.
Output
Print the minimum number of moves.
Constraints

$1%20%5Cle%20n%20%5Cle%202%20%5Ccdot%2010%5E5%2C%201%20%5Cle%20x_i%20%5Cle%2010%5E9$

Sample

模擬題。題意將輸入的數(shù)組修改為遞增數(shù)組，每次僅修改一個(gè)值將其加一。不是排序！

D - So I’ll Max Out My Constructive Algorithm Skills

BaoBao the Witch is stuck in a maze with $n$ rows and $n$ columns, where the height of the cell in the $i$ -th row and the $j$ -th column is $h_%7Bi%2Cj%7D$ . To get out of the maze, BaoBao has to find a path which passes through each cell exactly once. Each time she can only move into the neighboring cell sharing a same edge with the current one. But as we know, BaoBao is super lazy, so every time when she climbs up (that is to say, moving from a cell with a smaller height to another with a larger height) her happiness value will decrease. As her helping hand, your task is to find a valid path so that when moving along the path, the number of times BaoBao climbs up will not be more than the number of times she climbs down. More formally, you need to find a sequence? $%20(x_1%2C%20y_1)%2C(x_2%2C%20y_2)%2C%20%C2%B7%20%C2%B7%20%C2%B7%20%2C(x_%7Bn2%7D%20%2C%20y_%7Bn2%7D)%20$ such that:

For all? $1%20%5Cleq%20i%20%5Cleq%20n%5E2%2C%201%20%5Cleq%20x_i%2C%20y_i%20%5Cleq%20n%3B$
For all? $1%20%5Cleq%20i%2Cj%20%5Cleq%20n%5E2%2C%20i%20%5Cneq%20j%2C%20(x_i%2Cy_i)%20%5Cneq%20(x_j%2Cy_j)%3B$
For all? $2%20%5Cleq%20i%20%5Cleq%20n%5E2%2C%20%7C%20x_i%20-%20x_%7Bi-1%7D%7C%2B%7Cy_i-y_%7Bi-1%7D%7C%3D1%3B$
$%5Csum_%7Bi%3D2%7D%5E%7Bn%5E2%7D%5Bh_%7Bx_%7Bi-1%7D%2Cy_%7Bi-1%7D%7D%20%3C%20h_%7Bx_%7Bi%7D%2Cy_%7Bi%7D%7D%20%5D%20%5Cleq%20%5Csum_%7Bi%3D2%7D%5E%7Bn%5E2%7D%5Bh_%7Bx_%7Bi-1%7D%2Cy_%7Bi-1%7D%7D%20%3E%20h_%7Bx_%7Bi%7D%2Cy_%7Bi%7D%7D%20%5D%2C$ ?where $%5BP%5D$ ?equals $1$ ?when? $%5BP%5D$ ?is true, and equals? $0$ ?when it is false.

Additionally, you discover that the heights in all cells are a permutation of $n%5E2$ , so you just need to output the height of each cell in a valid path.

Input

There are multiple test cases. The first line of the input contains an integer $T%20(1%20%E2%89%A4%20T%20%E2%89%A4%20100)$ ?indicating the number of test cases.?

For each test case: The first line contains an integer $n%20(2%20%E2%89%A4%20n%20%E2%89%A4%2064)$ ?indicating the size of the maze.?

For the following? $n$ ?lines, the $i$ -th line contains $n$ integers? $h_%7Bi%2C1%7D%2C%20h_%7Bi%2C2%7D%2C%20%C2%B7%20%C2%B7%20%C2%B7%20%2C%20h_%7Bi%2Cn%7D%20(1%20%E2%89%A4%20h_%7Bi%2Cj%7D%20%E2%89%A4%20n%5E2%20)$ ?where $h_%7Bi%2Cj%7D$ ? indicates the height of the cell in the $i$ -th row and the $j$ -th column. It’s guaranteed that all integers in the input make up a permutation of $n%5E2$ .

Output

For each test case output one line containing $n%5E2$ separated by a space indicating the heights of each cell in a valid path. If there are multiple valid answers you can output any of them. It’s easy to prove that an answer always exists.

Please, DO NOT output extra spaces at the end of each line, or your answer may be considered incorrect!

Example

本題為2021 ICPC Asia Macau區(qū)域賽A題（簽到題）。題目大意為一個(gè) $n*n$ 矩陣，其中的值代表高度，每個(gè)各不相同，只能上下左右移動(dòng)，求一條路下降次數(shù)大于等于上升次數(shù)。最開(kāi)始想用DFS，WA四次之后發(fā)現(xiàn)只用看最后up和down誰(shuí)大就好，蛇形矩陣遍歷一遍，如果不符合要求翻轉(zhuǎn)一遍就是結(jié)果。

E - Link-Cut Tree

BaoBao just learned how to use a data structure called link-cut tree to find cycles in a graph and decided to give it a try. BaoBao is given an undirected graph with $n$ vertices and $m$ edges, where the length of the $i$ -th edge equals $2%5Ei$ . She needs to find a simple cycle with the smallest length.

A simple cycle is a subgraph of the original graph containing? $%20k%20(3%20%E2%89%A4%20k%20%E2%89%A4%20n)%20$ vertices $a_1%2C%20a_2%2C%20%C2%B7%20%C2%B7%20%C2%B7%20%2C%20a_k$ ?and $k$ edges such that for all $1%20%E2%89%A4%20i%20%E2%89%A4%20k$ ?there is an edge connecting vertices $a_i$ and $a_%7B(i%20mod%20k)%2B1%7D$ ?in the subgraph. The length of a simple cycle is the total length of the edges in the cycle.

Input

There are multiple test cases. The first line of the input contains an integer $T$ indicating the number of test cases.

For each test case: The first line contains two integers $n$ and $m%20(3%20%E2%89%A4%20n%20%E2%89%A4%2010%5E5%20%2C%201%20%E2%89%A4%20m%20%E2%89%A4%2010%5E5%20)$ ?indicating the number of vertices and edges in the original graph. For the following m lines, the $i$ -th line contains two integers $u_i$ and $v_i%20(1%20%E2%89%A4%20u_i%20%2C%20v_i%20%E2%89%A4%20n)%20$ indicating an edge connecting vertices ui and vi with length $2%5Ei$ .

There are no self loops nor multiple edges. Note that the graph is not necessarily connected.

It’s guaranteed that neither the sum of $n$ nor the sum of m of all test cases will exceed $10%5E6$ .

Output

For each test case output one line. If there are no simple cycles in the graph output “-1” (without quotes); Otherwise output $k$ integers separated by a space in increasing order indicating the indices of the edges in the simple cycle with the smallest length. It can be shown that there is at most one answer.

Please, DO NOT output extra spaces at the end of each line, or your solution may be considered incorrect!

Example

本題為2021 ICPC Asia Macau區(qū)域賽K題（簽到題），人菜沒(méi)做出來(lái)。解法應(yīng)該是并查集判環(huán)，DFS或者BFS遍歷輸出。上個(gè)AC代碼下來(lái)研究。

F - Random Permutation

An integer sequence with length? $n$ , denoted by? $a_1%2Ca_2%2C%5Ccdots%2Ca_n$ , is generated randomly, and the probability of being? $1%2C2%2C%5Ccdots%2Cn$ ?are all? $%5Cfrac%7B1%7D%7Bn%7D$ ?for each? $a_i(i%3D1%2C2%2C%5Ccdots%2Cn)$ .

Your task is to calculate the expected number of permutations? $p_1%2Cp_2%2C%5Ccdots%2Cp_n$ ?from? $1$ ?to? $n$ ?such that? $p_i%20%5Cle%20a_i$ ?holds for each? $i%3D1%2C2%2C%5Ccdots%2Cn$ .

Input

The only line contains an integer? $n(1%20%5Cleq%20n%20%5Cleq%2050)$ .

Output

Output the expected number of permutations satisfying the condition. Your answer is acceptable if its absolute or relative error does not exceed? $10%5E%7B-9%7D$ .

Formally speaking, suppose that your output is? $x$ ?and the jury's answer is? $y$ . Your output is accepted if and only if? $%5Cfrac%7B%7Cx%20-%20y%7C%7D%7B%5Cmax(1%2C%20%7Cy%7C)%7D%20%5Cleq%2010%5E%7B-9%7D$ .

本題為2020?ICPC Asia Macau區(qū)域賽L題（簽到題）數(shù)學(xué)推論題。題意大概為長(zhǎng)度為 $n$ 的數(shù)組 $a$ ，每個(gè)數(shù)都為 $1%2C2%2C3%2C%5Ccdot%5Ccdot%5Ccdot%2Cn$ 的概率都為 $%5Cfrac%7B1%7D%7Bn%7D$ ，對(duì)于其全排列數(shù)組 $p$ ，對(duì)任意的 $i$ ，? $p_i%20%5Cle%20a_i$ 都成立的概率為多少。

G - Prince and Princess

線(xiàn)性DP題。題目說(shuō)了一大串，但實(shí)際上就是求 $n%2B1$ 個(gè)數(shù)字和 $m%2B1$ 個(gè)數(shù)字的最長(zhǎng)公共子序列。但用普通的LCS算法復(fù)雜度直接變成 $n%5E4$ ，所以要換思路。題目中說(shuō)每一個(gè)數(shù)都不相同，可以使序列a有序，使序列b按照相同的法則進(jìn)行映射，轉(zhuǎn)化成LIS。

標(biāo)簽：

最美情侣中文字幕电影,在线麻豆精品传媒,在线网站高清黄,久久黄色视频

Weekly Contest 1 - UM ICPC Training Group

頭文件

A - Roaming Romans

B - Harshad Numbers

C - Increasing Array

D - So I’ll Max Out My Constructive Algorithm Skills

E - Link-Cut Tree

G - Prince and Princess