當(dāng)前位置：首頁 > 编程资源 > 编程问答 >内容正文

编程问答

JXCPC 试题册

發(fā)布時(shí)間：2024/8/26 编程问答 34 豆豆

生活随笔收集整理的這篇文章主要介紹了 JXCPC 试题册小編覺得挺不錯(cuò)的,現(xiàn)在分享給大家,幫大家做個(gè)參考.

JXCPC 試題冊

Input file: standard input

Output file: standard output

Time limit: 1s

Memory limit: 256 megabytes

Problem A. Cotree

Avin has two trees which are not connected. He asks you to add an edge between them to make them connected while minimizing the function \(\sum_{i=1}^{n} \sum_{j=i+1}^{n} dis(i,j)\)

,where dis(i,j) represents the number of edges of the path from i to j . He is happy with only the function value.

Input

The first line contains a number n(\(2 \leq n \leq 100,000\)). In each of the following n-2 lines , there are two numbers u and v , meaning that there is an edge between u and v .The input is guaranteed to contain exactly two trees.

Output

Just print the minimum function value

中文簡述題意

給出兩棵樹T1,T2，連接一條邊使得這兩顆樹合成一棵樹，你所連的邊要使\(\sum_{i=1}^{n} \sum_{j=i+1}^{n} dis(i,j)\)最小，dis(i,j)指鏈接i,j的簡單路徑所含邊的數(shù)目

Example

Input
3 1 2
Output
4

Problem B.Math

Avin sells robots to clients. At second 0,Avin is at the location (0,0) on a number axis with a robot. He wants to go to (L,0) with the robot. He walks a unit distance per second , and he can only stop at integer coordinates. Now he decides to follow these walking rules repeatedly until he arrives (L,0) with the robot :

1) If Avin has the robot with himself,the robot may be dropped down with probability p
2) If Avin had dropped the robot , he will figure it out with probability q. Specially, if Avin arrives at (L,0) without robot , he will trun around immediately
3) If Avin does not see that the robot had been dropped, he walks one step right; otherwise, he walks left until he is at the same location as the robot.

What is the expectation of walking time he needs to arrive (L,0) with the robot.

中文簡述題意

Avin要帶著機(jī)器人從0走到L，走路速度為每秒一格并且只會(huì)在整數(shù)格停下，他走路按照以下規(guī)則：

如果Avin沒有弄丟機(jī)器人，則有p的概率弄丟機(jī)器人
如果Avin已經(jīng)弄丟了機(jī)器人，則有q的概率發(fā)現(xiàn)，特別的，當(dāng)他到達(dá)終點(diǎn)卻沒有機(jī)器人時(shí)，會(huì)立刻發(fā)現(xiàn)
如果Avin發(fā)現(xiàn)他弄丟了機(jī)器人，則會(huì)一直往左走直到遇見機(jī)器人，否則他會(huì)向右走一格

Input

One line with three numbers L,p and q, where L(\(1\leq L \leq100,000\)) is an integer,p and q are real numbers with three digits and within(0,1)

Output

Print the expected walking time . Your answer is considered correct if the absolute or relative error doesn't exceed \(10^{-6}\).Formally, let you answer be a , and the jury's answer be b. Your answer is considered correct if \(\frac{|a-b|}{max(1,|b|)} \leq 10^{-6}\)

Problem C.Trap

GuGuGu

Problem D.Wave

Avin is studying series. A series is called "wave" if the following conditions are satiffied:

1) It contains at least two elements

2) All elements at odd positions are the same

3) All elements at even positions are the same

4) Elements at odd positions are NOT the same as the elements at even positions

You are given a series with length n. Avin asks you to find the longest "wave" subseries. A subseries is a subsequence of a series.

Input

The first line contains two numbers n,c(\(1 \leq n \leq 100,000, 1 \leq c \leq 100\)). The second line contains n integers whose range is [1,c] , which represents the series. It is guaranteed that there is always a "wave" subseries.

Output

Print the length of the longest "wave" subseries.

插幾句嘴qwq

本題考試時(shí)\(O(nc^2)\)可以通過,實(shí)際上\(O(nc^2) \leq O(10^5 \times (10^2)^2) = O(10^9)\),不能通過

所以很迷...我寫的是\(O(nc)\)

Example

Input
5 3 1 2 1 3 2
Output
4

Problem E.Packing

GuGuGu

Problem F.String

Avin has a string. He would like to uniform-randomly select four characters (selecting the same character is allowed) from it. You are asked to calculate to probability of four characters being "avin" in order.

Input

The first line contains n(\(1 \leq n \leq 100\)), the length of the string. The second line contains the string. To simplify the problem , the characters of the string are from 'a' , 'v' , 'i' , 'n'.

Output

Print the reduced fraction (the greatest common divisor of the numerator and denominator is 1),representing the probability. If the answer is 0 , you should output "0/1"

Example

Input1
4 avin
Output1
1/256
Input2
4 aaaa
Output2
0/1

Problem G.Traffic

GuGuGu

Problem H.RNG(RNG 牛逼)

Avin is studying how to synthesize data . Given a integer n, he constructs ans interval using the following method: He first generates a integer r between 1 and n (both inclusize) uniform-randomly, and generates a integer l between 1 and r (both inclusize) uniform-randomly. The interval [l,r] is the constructed. Avin has constructed two intervals using the method above. He asks you what the probalility that two intervals intersect(相交) is. You should print \(q \times q^{-1}(MOD 1,000,000,007)\), while \(\frac{p}{q}\) denoting the probalility.

Input

Just one line contains the number n (\(1 \leq n \leq 1,000,000\))

Output

Print the answer

Example

Input1
1
Output1
1
Input2
2
Output2
750000006

Problem I.Budget

Avin's company has many ongoing projects with difference budgets. His company records the budgets using numbers rounded to 3 digits after the decimal place.However, the company is updating the system and all budgets will be rounded up to 2 digits after the decimal place. For example, 1.004 will be rounded down to 1.00 while 1.995 will be rounded up to 2.00. Avin wants to konw the difference of the total budget caused by update.

Input

The first line contains an integer n(\(1 \leq n \leq 1,000\)). The second line contains n decimals, and the i-th decimal \(a_i\)(\(0 \leq n \leq 10^{18}\)) repersents the budget of the i-th project. All decimals are rounded to 3 digits.

Output

Print the difference rounded to 3 digits.

Example

Input1
1 1.001
Output1
-0.001
Input2
1 0.999
Output2
0.001
Input3
2 1.001 0.999
Output3
0.000

Problem J.Worker

Avin meets a rich customer today. He will earn 1 million dollars if he can solve a hard problem. There are n warehouses and m workers. Any worker in the i-th warehouse can handle \(a_i\) orders per day. The customer wonders whether there exists one worker assignment method satiisfying that every warehouse handles the ssame number of orders every day. Note that each worker should be assigned to exactly warehouse and no worker is lazy when working.

Input

The first line contains two integers n(\(1 \leq n \leq 1,000\)) ,m(\(1 \leq m \leq 10^{18}\)). The second lie contains n integers. The i-th integer \(a_i\) (\(1 \leq a_i \leq 10\)) represensts one worker in the i-th warehouse can handle \(a_i\) orders per day.

Output

If there is feasible assignment method, orint "Yes" in the first line. Then , i th second line, print n integers with i-th integer representing the number of workers assigned too the i-th warehouse. Otherwise , print "No" in one line. If there are multiple solutions, any is accepted.