CodeForces Round#352 Div.2

总结:面对问题要多角度思考,多多挖掘题目的特殊性质,不要一上来就先入为主暴力算法...

A. Summer Camp

Every year, hundreds of people come to summer camps, they learn new algorithms and solve hard problems.

This is your first year at summer camp, and you are asked to solve the following problem. All integers starting with 1 are written in one line. The prefix of these line is "123456789101112131415...". Your task is to print the n-th digit of this string (digits are numbered starting with 1.

Input

The only line of the input contains a single integer n (1 ≤ n ≤ 1000) — the position of the digit you need to print.

Output

Print the n-th digit of the line.

Solution

n辣么小,为什么不来一发惊险而又刺激的枚举呢。。

其实n可以弄到10^{18},利用等差数列求和公式二分即可

B. Different is Good

A wise man told Kerem "Different is good" once, so Kerem wants all things in his life to be different.

Kerem recently got a string s consisting of lowercase English letters. Since Kerem likes it when things are different, he wants allsubstrings of his string s to be distinct. Substring is a string formed by some number of consecutive characters of the string. For example, string "aba" has substrings "" (empty substring), "a", "b", "a", "ab", "ba", "aba".

If string s has at least two equal substrings then Kerem will change characters at some positions to some other lowercase English letters. Changing characters is a very tiring job, so Kerem want to perform as few changes as possible.

Your task is to find the minimum number of changes needed to make all the substrings of the given string distinct, or determine that it is impossible.

Input

The first line of the input contains an integer n (1 ≤ n ≤ 100 000) — the length of the string s.

The second line contains the string s of length n consisting of only lowercase English letters.

Output

If it's impossible to change the string s such that all its substring are distinct print -1. Otherwise print the minimum required number of changes.

Solution

弄个26大小的hash,每次扫扫就行了,时间复杂度\Theta(26n)

C. Recycling Bottles

It was recycling day in Kekoland. To celebrate it Adil and Bera went to Central Perk where they can take bottles from the ground and put them into a recycling bin.

We can think Central Perk as coordinate plane. There are n bottles on the ground, the i-th bottle is located at position (xi, yi). Both Adil and Bera can carry only one bottle at once each.

For both Adil and Bera the process looks as follows:

  1. Choose to stop or to continue to collect bottles.
  2. If the choice was to continue then choose some bottle and walk towards it.
  3. Pick this bottle and walk to the recycling bin.
  4. Go to step 1.

Adil and Bera may move independently. They are allowed to pick bottles simultaneously, all bottles may be picked by any of the two, it's allowed that one of them stays still while the other one continues to pick bottles.

They want to organize the process such that the total distance they walk (the sum of distance walked by Adil and distance walked by Bera) is minimum possible. Of course, at the end all bottles should lie in the recycling bin.

Input

First line of the input contains six integers ax, ay, bx, by, tx and ty (0 ≤ ax, ay, bx, by, tx, ty ≤ 109) — initial positions of Adil, Bera and recycling bin respectively.

The second line contains a single integer n (1 ≤ n ≤ 100 000) — the number of bottles on the ground.

Then follow n lines, each of them contains two integers xi and yi (0 ≤ xi, yi ≤ 109) — position of the i-th bottle.

It's guaranteed that positions of Adil, Bera, recycling bin and all bottles are distinct.

Output

Print one real number — the minimum possible total distance Adil and Bera need to walk in order to put all bottles into recycling bin. Your answer will be considered correct if its absolute or relative error does not exceed 10 - 6.

Namely: let's assume that your answer is a, and the answer of the jury is b. The checker program will consider your answer correct if .

Solution

考虑这样一个图,这样可以容易得到一个思路

先把所有点都连向垃圾桶,然后再找出两个点分别连向A,B

思路和修理牛棚很像

而这两个点显然不可能暴力枚举,那么我们只需要维护出每个点的次近点和最近点即可,为啥呢?

不妨令垃圾桶为c

T=\sum_{i=1}^{n}2dis_{i,c}

那么假设A连了j

则答案

T'=T-dis_{j,c}+dis_{j,A}

B同理

显然T'的取值只与点到A/B的取值有关

所以正确性显然。

注意特殊处理一个人走完全程的情况以及N=1的情况

D. Robin Hood

We all know the impressive story of Robin Hood. Robin Hood uses his archery skills and his wits to steal the money from rich, and return it to the poor.

There are n citizens in Kekoland, each person has ci coins. Each day, Robin Hood will take exactly 1 coin from the richest person in the city and he will give it to the poorest person (poorest person right after taking richest's 1 coin). In case the choice is not unique, he will select one among them at random. Sadly, Robin Hood is old and want to retire in k days. He decided to spend these last days with helping poor people.

After taking his money are taken by Robin Hood richest person may become poorest person as well, and it might even happen that Robin Hood will give his money back. For example if all people have same number of coins, then next day they will have same number of coins too.

Your task is to find the difference between richest and poorest persons wealth after k days. Note that the choosing at random among richest and poorest doesn't affect the answer.

Input

The first line of the input contains two integers n and k (1 ≤ n ≤ 500 000, 0 ≤ k ≤ 109) — the number of citizens in Kekoland and the number of days left till Robin Hood's retirement.

The second line contains n integers, the i-th of them is ci (1 ≤ ci ≤ 109) — initial wealth of the i-th person.

Output

Print a single line containing the difference between richest and poorest peoples wealth.

Solution

一种比较直观的想法就是维护以后一定都是平均数左右分布

那么就可以xjb模拟了,所以问题在于如何处理出平均数分布

考虑直接计算k次以后的最大值最小值即可

E. Ultimate Weirdness of an Array

Yasin has an array a containing n integers. Yasin is a 5 year old, so he loves ultimate weird things.

Yasin denotes weirdness of an array as maximum gcd(ai,  aj) value among all 1 ≤ i < j ≤ n. For n ≤ 1 weirdness is equal to 0,gcd(x,  y) is the greatest common divisor of integers x and y.

He also defines the ultimate weirdness of an array. Ultimate weirdness is where f(i,  j) is weirdness of the new array aobtained by removing all elements between i and j inclusive, so new array is [a1... ai - 1, aj + 1... an].

Since 5 year old boys can't code, Yasin asks for your help to find the value of ultimate weirdness of the given array a!

Input

The first line of the input contains a single integer n (1 ≤ n ≤ 200 000) — the number of elements in a.

The next line contains n integers ai (1 ≤ ai ≤ 200 000), where the i-th number is equal to the i-th element of the array a. It is guaranteed that all ai are distinct.

Output

Print a single line containing the value of ultimate weirdness of the array a.

Solution

题目大意:记[L,R]的权值为max\begin{Bmatrix}gcd(ai,aj)\end{Bmatrix}(1\leq i,j\leq n),记f(i,j)为整个数组移除[i,j]后的最大区间权值,求

 

CodeForces Round#352 Div.2》上有2条评论

  1. Pingback引用通告: CF红名计划 | MedalPluS

发表评论