(AB)Codeforces Round #528 (Div. 2, based on Technocup 2019 Elimination Round
Polycarp loves ciphers. He has invented his own cipher called Right-Left.
Right-Left cipher is used for strings. To encrypt the string s=s1s2…sns=s1s2…sn Polycarp uses the following algorithm:
- he writes down s1s1,
- he appends the current word with s2s2 (i.e. writes down s2s2 to the right of the current result),
- he prepends the current word with s3s3 (i.e. writes down s3s3 to the left of the current result),
- he appends the current word with s4s4 (i.e. writes down s4s4 to the right of the current result),
- he prepends the current word with s5s5 (i.e. writes down s5s5 to the left of the current result),
- and so on for each position until the end of ss.
For example, if ss="techno" the process is: "t" →→ "te" →→ "cte" →→ "cteh" →→ "ncteh" →→ "ncteho". So the encrypted ss="techno" is "ncteho".
Given string tt — the result of encryption of some string ss. Your task is to decrypt it, i.e. find the string ss.
The only line of the input contains tt — the result of encryption of some string ss. It contains only lowercase Latin letters. The length of tt is between 11 and 5050, inclusive.
Print such string ss that after encryption it equals tt.
ncteho
techno
erfdcoeocs
codeforces
z
z
我好菜啊...脑袋都锈住了!
1 #include <iostream> 2 #include <algorithm> 3 #include <cstdlib> 4 #include <cstring> 5 6 using namespace std; 7 8 int main(){ 9 string str{"0"}; 10 string out{"0"}; 11 //memset(s,'\0',sizeof(s)); 12 //memset(out,'\0',sizeof(out)); 13 while(cin>>str){ 14 int len=str.size(); 15 out=str; 16 if(len==1 || len==2){ 17 cout<<str<<endl; 18 continue; 19 } 20 int tmp=0; 21 int len_right=0; 22 int len_left=0; 23 if(len%2==1){ 24 tmp=(len-1)/2; 25 }else{ 26 tmp=len/2-1; 27 } 28 out[0]=str[tmp]; 29 out[1]=str[tmp+1]; 30 for(int i=tmp+2,j=3;i<len;i++,j++,j++){ 31 out[j]=str[i]; 32 } 33 for(int i=tmp-1,j=2;i>=0;i--,j++,j++){ 34 out[j]=str[i]; 35 } 36 cout<<out<<endl; 37 //memset(str,'\0',sizeof(str)); 38 //memset(out,'\0',sizeof(out)); 39 40 41 } 42 43 44 45 46 return 0; 47 }
Vasya likes to solve equations. Today he wants to solve (x div k)⋅(xmodk)=n(x div k)⋅(xmodk)=n, where divdiv and modmod stand for integer division and modulo operations (refer to the Notes below for exact definition). In this equation, kk and nn are positive integer parameters, and xx is a positive integer unknown. If there are several solutions, Vasya wants to find the smallest possible xx. Can you help him?
The first line contains two integers nn and kk (1≤n≤1061≤n≤106, 2≤k≤10002≤k≤1000).
Print a single integer xx — the smallest positive integer solution to (x div k)⋅(xmodk)=n(x div k)⋅(xmodk)=n. It is guaranteed that this equation has at least one positive integer solution.
6 3
11
1 2
3
4 6
10
The result of integer division a div ba div b is equal to the largest integer cc such that b⋅c≤ab⋅c≤a. aa modulo bb (shortened amodbamodb) is the only integer cc such that 0≤c<b0≤c<b, and a−ca−c is divisible by bb.
In the first sample, 11 div 3=311 div 3=3 and 11mod3=211mod3=2. Since 3⋅2=63⋅2=6, then x=11x=11 is a solution to (x div 3)⋅(xmod3)=6(x div 3)⋅(xmod3)=6. One can see that 1919 is the only other positive integer solution, hence 1111 is the smallest one.
思路:让找一个最小的x,使得(x/k)*(x%k)==n,如果对x暴力枚举肯定会超时啊,所以可以从x%k这里下手,x%k的值一定>=0 且<k,又因为n不可能为0,所以x%k是大于0的.所以在1~(k-1)之间枚举k.
再设x%k=i,上式可以变成(x-i)/k * i =n,所以x=n/i * k +i.
#include <bits/stdc++.h> using namespace std; using LL = long long; int main(){ LL n,k; while(cin>>n>>k){ LL x(LONG_MAX); for(LL i=1;i<k;i++){ if(n%i!=0) continue; LL tmp=n/i*k+i; x=(x<tmp?x:tmp); } cout<<x<<endl; } return 0; }
