因?yàn)樘脹](méi)有更新博客了，最近比較忙世落。抹竹。所以就把兩周簽EL-ROUND-TWO我AC的兩道題簡(jiǎn)單的講講，以后很多更新可能都直接貼一個(gè)github的賬號(hào)了quq
pppppkun · GitHub
↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑
A – Save Energy
Julia is going to cook a chicken in the kitchen of her dormitory. To save energy, the stove in the kitchen automatically turns off after kminutes after turning on.
During cooking, Julia goes to the kitchen every d minutes and turns on the stove if it is turned off. While the cooker is turned off, it stays warm. The stove switches on and off instantly.
It is known that the chicken needs t minutes to be cooked on the stove, if it is turned on, and 2t minutes, if it is turned off. You need to find out, how much time will Julia have to cook the chicken, if it is considered that the chicken is cooked evenly, with constant speed when the stove is turned on and at a constant speed when it is turned off.
Input
The single line contains three integers k, d and t (1?≤?k,?d,?t?≤?1018).
Output
Print a single number, the total time of cooking in minutes. The relative or absolute error must not exceed 10?-?9.
Namely, let's assume that your answer is x and the answer of the jury is y. The checker program will consider your answer correct if
.
Examples
Input
3 2 6
Output
6.5
Input
4 2 20
Output
20.0
Note
In the first example, the chicken will be cooked for 3 minutes on the turned on stove, after this it will be cooked for
. Then the chicken will be cooked for one minute on a turned off stove, it will be cooked for
. Thus, after four minutes the chicken will be cooked for
. Before the fifth minute Julia will turn on the stove and after 2.5 minutes the chicken will be ready
.
In the second example, when the stove is turned off, Julia will immediately turn it on, so the stove will always be turned on and the chicken will be cooked in 20 minutes.
首先先注意到m和n都超級(jí)大盏档，1?≤?k,?d?≤ 1018，所以我們需要用long long 來(lái)保存燥爷◎谀叮考慮到m和n之間的關(guān)系，有三種情況
n|m
此時(shí)一直都是高溫加熱的狀態(tài)前翎，所以時(shí)間就直接是t了
n<m或者n>m
此時(shí)勺拣，因?yàn)槊縩次都會(huì)去開(kāi)一次烤爐（如果關(guān)上了的話），所以我們可以考慮當(dāng)烤爐滅了的時(shí)間和n之間的關(guān)系鱼填，如果存在一個(gè)最小的數(shù)k药有，使得kn>m，那么我們就稱一個(gè)周期是kn苹丸，這個(gè)周期所做出的貢獻(xiàn)是(kn-m)*1/2 + m
后面就很簡(jiǎn)單了愤惰，下面看第二題。
C-Lock Puzzle
Welcome to another task about breaking the code lock! Explorers Whitfield and Martin came across an unusual safe, inside of which, according to rumors, there are untold riches, among which one can find the solution of the problem of discrete logarithm!
Of course, there is a code lock is installed on the safe. The lock has a screen that displays a string of n lowercase Latin letters. Initially, the screen displays string s. Whitfield and Martin found out that the safe will open when string t will be displayed on the screen.
The string on the screen can be changed using the operation ?shiftx?. In order to apply this operation, explorers choose an integer xfrom 0 to n inclusive. After that, the current string p?=?αβ changes to βRα, where the length of β is x, and the length of α is n?-?x. In other words, the suffix of the length x of string p is reversed and moved to the beginning of the string. For example, after the operation ?shift 4? the string ?abcacb? will be changed with string ?bcacab ?, since α?=?ab, β?=?cacb, βR?=?bcac.
Explorers are afraid that if they apply too many operations ?shift?, the lock will be locked forever. They ask you to find a way to get the string t on the screen, using no more than 6100 operations.
Input
The first line contains an integer n, the length of the strings s and t (1?≤?n?≤?2?000).
After that, there are two strings s and t, consisting of n lowercase Latin letters each.
Output
If it is impossible to get string t from string s using no more than 6100 operations ?shift?, print a single number ?-?1.
Otherwise, in the first line output the number of operations k (0?≤?k?≤?6100). In the next line output k numbers xi corresponding to the operations ?shift xi? (0?≤?xi?≤?n) in the order in which they should be applied.
Examples
Input
6
abacbb
babcba
Output
4
6 3 2 3
Input
3
aba
bba
Output
-1
In the first example, after applying the operations, the string on the screen will change as follows:
abacbb→bbcaba
bbcaba→ababbc
ababbc→cbabab
cbabab→babcba
本人認(rèn)為這題還是有點(diǎn)復(fù)雜的赘理，因?yàn)槲覀兇藭r(shí)不知道題目例子中給出的變化是不是通用的變換宦言，第二是通用的變換如果存在的話能不能在6100步以內(nèi)結(jié)束呢？注意到1?≤?n?≤?2?000商模，3*n 剛好是在6000以內(nèi)的數(shù)奠旺，這可能說(shuō)明了存在一個(gè)通用的變化，使得3步以內(nèi)歸位一個(gè)數(shù)施流？
經(jīng)過(guò)不斷嘗試响疚，我發(fā)現(xiàn)可以通過(guò)一下操作使得一個(gè)數(shù)從中間的某一位換到這一串?dāng)?shù)的最末尾，且不改變已經(jīng)排好的那段瞪醋。
A忿晕，D是任意的一個(gè)子串，B是已經(jīng)排好的子串银受，c是B后一位的字符践盼，用A/表示A的逆序，我們從t串的最后一位開(kāi)始排宾巍，假設(shè)現(xiàn)在是如下?tīng)顟B(tài) BDcA
BDcA →A/cD/B/
A/cD/B/→BDA/c
BDA/c→cBDA/→BDA/
這樣就解決了問(wèn)題咕幻，下面開(kāi)始code。
首先先判斷兩個(gè)string字母數(shù)是不是一樣的顶霞，如果不一樣直接return -1
如果是肄程，我們有一個(gè)循環(huán)，在循環(huán)中要不斷地歸為原來(lái)的子串，考慮到我們最后把操作的步數(shù)和怎么操作的都列出來(lái)绷耍，所以我們需要用一個(gè)東西來(lái)存每一步的操作，用一個(gè)向量就行了鲜侥。最后只需要打印即可褂始！
