# Algorithm design and analysis - Experiment 3

Question A: algorithm - Data Encryption
[Presenter: 080063]
Time limit: 1.000 sec memory limit: 128 MB

Title Description
Cryptography is a technical science that studies the preparation and decoding of passwords. Studying the objective law of password change and applying it to compiling password to keep communication secret is called coding; Those applied to deciphering passwords to obtain communication information are called deciphering and generally known as cryptography. Password is an important confidential means for both sides of communication to carry out special information transformation according to the agreed rules. According to these rules, changing plaintext into ciphertext is called encryption transformation; Changing ciphertext into plaintext is called declassification transformation. In the early stage, password only added and de encrypted words or numbers. With the development of communication technology, it can add and de encrypt voice, image and data.
Now you are required to encrypt the data with the method given below. Given the string S of length n (1 < = n < = 2000, only uppercase letters in S) as plaintext, it is required to construct a string T as ciphertext. At first, T is an empty string, and then repeat any of the following operations
1. Delete a character from the head of S and add it to the tail of T
2. Delete a character from the tail of S and add it to the tail of T
Finally, S will become an empty string, and T will become a string of length n as a ciphertext. Of course, not all construction schemes are qualified. We require the dictionary order of the constructed ciphertext t to be as small as possible. Can you find the ciphertext with the smallest dictionary order?
input
The input contains multiple groups of data, and each group of data accounts for two lines. The first line is an integer n (1 < = n < = 2000) representing the length of string s, and the second line is a string s with length n representing plaintext to ensure that there are only uppercase letters in S
output
For each group of data, a line of string is output to represent the ciphertext T with the smallest dictionary order
Sample input Copy
6
ACDBCB
Sample output Copy
ABCBCD

```#include<bits/stdc++.h>
using namespace std;
#define ll long long
int n,tip,top;
string s;
int main()
{
ios::sync_with_stdio(false);
while(cin>>n)
{
cin>>s;
tip=0;top=n-1;
while(tip<=top)
{
if(s[tip]<s[top])
{
cout<<s[tip];tip++;
}
else if(s[tip]>s[top])
{
cout<<s[top];top--;
}
else
{
int ti=tip,to=top,f=0;
while(ti<=to)
{
ti++;to--;
if(s[ti]<s[to])
{
f=0;break;
}
else if(s[ti]>s[to])
{
f=1;break;
}
}
if(f)
{
cout<<s[top];top--;
}
else
{
cout<<s[tip];tip++;
}
}
}
cout<<endl;
}
return 0;
}

```

Question B: algorithm - interesting primes
[Presenter: 080063]
Time limit: 2.000 sec memory limit: 128 MB

Title Description
Prime numbers are widely used in cryptography. The so-called public key is to add a number to the information to be transmitted when encoding, and then transmit it to the recipient. After anyone receives this information, if he does not have the secret key owned by the recipient, he will not be able to crack the information in the process of decryption because the prime factor is decomposed for too long. It can be seen that prime numbers are important in cryptography.
Now give you n (2 < = n < = 16) positive integers 1,2,3... N. your task is to form these n positive integers into a ring so that the sum of any two adjacent integers is a prime number, and output how many legal schemes there are.
input
Multiple groups of input data, each group of data has only one positive integer n (2 < = n < = 16), representing n positive integers 1,2,3... N
output
For each group of data, an integer is output to represent the number of different feasible schemes.
Sample input Copy
6
8
Sample output Copy
2
4

```#include<iostream>
#include<vector>
using namespace std;
int sum=0;
void f(vector<vector<int> >&op,vector<int>check,int &a,int n,int start){
if(n==a){
sum++;
return;
}
for(int i=2;i<=a;i++){
if(op[start][i]&&check[i]==0){
check[i]=1;
if(n!=a-1||n==a-1&&op[i])
f(op,check,a,n+1,i);
check[i]=0;
}
}
}
int main() {
int a;
vector<int>res={3, 5, 7, 11, 13, 17, 19, 23, 29, 31};//Minimum 1 + 2, so it can't be 2
vector<int>check=vector<int>(17,0);
check=1;
while(cin>>a){
sum=0;
if(a&1){
cout<<0<<endl;
continue;
}
vector<vector<int> > ans=vector<vector<int> >(a+1,vector<int>(a+1,0));
for(int i:res){
if(i>a*2)break;
for(int j=1;j<=i/2;j++){
if(i-j>a)continue;
ans[j][i-j]=ans[i-j][j]=1;
}
}
f(ans,check,a,1,1);
cout<<sum<<endl;
}
return 0;
}
```

Question C: algorithm - simple password
[Presenter: 080063]
Time limit: 1.000 sec memory limit: 128 MB

Title Description
A password is a symbol compiled according to a specific rule to change the information of both sides of the communication. A password is a sequence of symbols that hides the real content. In fact, it is to change the information represented by the open and standard information code into an information code that can not be read by other people except the communication parties through a transformation means. This unique information code is the password.
Now we define a very simple password. Its length is fixed as n (n < = 30) and each bit can only be composed of the number 0 or the number 1. However, there is a special requirement: at least three consecutive zeros in a password sequence can appear, otherwise it is invalid. Now, given the length n of your password sequence, your task is to calculate how many different and effective passwords can be generated by the sequence with length n?
input
The input contains multiple groups of data. Each group of data has only one positive integer n (1 < = n < = 30) representing the length of the password sequence, which occupies a separate line.
output
For each group of data, an integer is output to represent the number of different types of passwords that can be generated by the sequence with length n.
Sample input Copy
4
5
6
Sample output Copy
3
8
20

```#include<bits/stdc++.h>
using namespace std;
#define ll long long
int n,f={0,0,0,1};
int main()
{
ios::sync_with_stdio(false);
for(int i=4;i<=30;i++)
f[i]=2*f[i-1]+(1<<(i-4))-f[i-4];
while(cin>>n)
cout<<f[n]<<endl;
return 0;
}
```

Method 2 uses dfs + pruning optimization
Question D: algorithm Vigen è re password
[Presenter: 080063]
Time limit: 1.000 sec memory limit: 128 MB

Title Description
In the 16th century, French diplomat Blaise de Vigen è re designed a multi table cipher encryption algorithm - Vigen è re cipher. The encryption and decryption algorithm of Vigen è re password is easy to use and difficult to decipher. It was widely used by the Confederate army in the American Civil War.
In cryptography, we call the information to be encrypted plaintext, represented by M; The encrypted information is called ciphertext, represented by C; The key is a parameter, which is the data input in the algorithm of converting plaintext into ciphertext or ciphertext into plaintext, which is recorded as K. In the Vigen è re password, the key K is a string of letters, k = k1k2... kn. When plaintext M = m1m2... mn, the obtained ciphertext C = c1c2... cn, where ci = mi ® ki, operation ® The rules are shown in the following table:

During the operation of Vigen è re encryption, you should pay attention to:
® The operation ignores the case of the letters involved in the operation and maintains the case of the letters in plaintext M;
When the length of plaintext m is greater than that of key k, key k is reused. For example, when plaintext M=Helloworld and key k=abc, ciphertext C=Hfnlpyosnd.

input
The first line is a string representing the key k, with a length of no more than 100, which only contains upper and lower case letters.
The second line is a string, which represents the encrypted ciphertext, with a length of no more than 1000, including only uppercase and lowercase letters.
output
The output consists of 1 line and a string representing the plaintext corresponding to the input key and ciphertext.
Sample input Copy
CompleteVictory
Yvqgpxaimmklongnzfwpvxmniytm
Sample output Copy
Wherethereisawillthereisaway

```#include <stdio.h>
int main()
{
char k,c;
int i,j;
char temp;

scanf("%s",k);
getchar();
scanf("%s",c);

for(i=0,j=0;c[j]!='\0';j++)
{

if(c[j]>='A'&&c[j]<='Z')
{
if(k[i]>='A'&&k[i]<='Z')
temp=(c[j]-'A'-(k[i]-'A')+26)%26+'A';
else  temp=(c[j]-'A'-(k[i]-'a')+26)%26+'A';
}
else
{
if(k[i]>='A'&&k[i]<='Z')
temp=(c[j]-'a'-(k[i]-'A')+26)%26+'a';
else temp=(c[j]-'a'-(k[i]-'a')+26)%26+'a';
}
printf("%c",temp);
i++;
if(k[i]=='\0') i=0;
}
return 0;
}
```

Question E: algorithm Caesar encryption
[Presenter: 080063]
Time limit: 1.000 sec memory limit: 128 MB

Title Description
Caesar encryption, or Caesar encryption, Caesar transform, transform encryption, is the simplest and most well-known encryption technology. It is a replacement encryption technology. All letters in plaintext are shifted backward (or forward) according to a fixed number on the alphabet and replaced with ciphertext.
For example, when the offset is shifted 3 to the left:
Plaintext alphabet: ABCDEFGHIJKLMNOPQRSTUVWXYZ
Ciphertext alphabet: DEFGHIJKLMNOPQRSTUVWXYZABC
When in use, the encryptor finds the position of each letter in the message to be encrypted in the plaintext alphabet and writes down the corresponding letter in the ciphertext alphabet. The person who needs to decrypt operates in reverse according to the previously known key to obtain the original plaintext. For example:
Plaintext: THE QUICK BROWN FOX JUMPS OVER THE LAZY DOG
Ciphertext: WKH TXLFN EURZQ IRA MXPSV RYHU WKH ODCB GRJ
Now, given a string S (the length will not exceed 1000000) and an integer k (- 1000000000 < = k < = 1000000000), representing the ciphertext received by the recipient and the backward offset when encrypting the ciphertext, your task is to calculate the original plaintext
Note: only letters will be offset during encryption, and other characters will remain unchanged
input
The input contains multiple groups of data, in which the number of data groups in the first row is t (T < = 10)
The first line of each group of data is a string S, which is composed of numbers, letters and common characters (excluding spaces), and the second line is an integer k, which represents the backward offset during encryption (| S | < = 10000000, - 1000000000 < = k < = 1000000000)
output
For each group of data, a line of string is output to represent the plaintext corresponding to the ciphertext in the input.
Sample input Copy
1
DEFGHIJKLMNOPQRSTUVWXYZABC
3
Sample output Copy
ABCDEFGHIJKLMNOPQRSTUVWXYZ

Note that the input string here can have other characters, but in the end, only the letter type needs to be converted

```#include<bits/stdc++.h>
using namespace std;
#define ll long long
string str;
int t,off;
int main()
{
cin >> t;
for(int i = 0; i < t; i++)
{
cin >> str[i];
cin >> off[i];
off[i]%=26;
}
for(int i = 0; i < t; i++)
{
for(int j = 0; j < str[i].length(); j++)
{
if(str[i][j] >= 'A' && str[i][j] <= 'Z')
str[i][j] = 'A' + (str[i][j] - 'A' - off[i] + 26) % 26;
else if(str[i][j] >= 'a' && str[i][j] <= 'z')
str[i][j] = 'a' + (str[i][j] - 'a' - off[i] + 26) % 26;
}
cout<< str[i] << endl;
}
return 0;
}

```

Posted by ckhitler at Oct 29, 2021 - 9:26 PM Tag: dfs Algorithm
{"ft_lang_label":"__label__en","ft_lang_prob":0.7824784,"math_prob":0.9656002,"size":11227,"snap":"2023-40-2023-50","text_gpt3_token_len":2937,"char_repetition_ratio":0.12349639,"word_repetition_ratio":0.107957706,"special_character_ratio":0.2837802,"punctuation_ratio":0.13711073,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.98969823,"pos_list":[0],"im_url_duplicate_count":[null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2023-12-11T06:36:43Z\",\"WARC-Record-ID\":\"<urn:uuid:8832745a-62e2-4d7d-ac6c-5319808a60f8>\",\"Content-Length\":\"22289\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:e482bed1-c3df-493a-8418-92d327ecb36f>\",\"WARC-Concurrent-To\":\"<urn:uuid:5d986a0e-2dff-4498-a546-5eac716e4702>\",\"WARC-IP-Address\":\"178.238.237.47\",\"WARC-Target-URI\":\"https://www.fatalerrors.org/a/algorithm-design-and-analysis-experiment-3.html\",\"WARC-Payload-Digest\":\"sha1:DG5RZU3Q6UE5EMPPICKINY356SALECLE\",\"WARC-Block-Digest\":\"sha1:NKLBD6NXAPRSR2ZZ6OUA5YR2R3E4U2AI\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2023/CC-MAIN-2023-50/CC-MAIN-2023-50_segments_1700679103558.93_warc_CC-MAIN-20231211045204-20231211075204-00449.warc.gz\"}"}