当前位置:网站首页>Krypton Factor purple book chapter 7 violent solution
Krypton Factor purple book chapter 7 violent solution
2022-07-05 23:07:00 【Porter hunter of the program】
Catalog
Title Description
Background
You have been employed by the organisers of a Super Krypton Factor Contest in which contestants have very high mental and physical abilities. In one section of the contest the contestants are tested on their ability to recall a sequenace of characters which has been read to them by the Quiz Master. Many of the contestants are very good at recognising patterns. Therefore, in order to add some difficulty to this test, the organisers have decided that sequences containing certain types of repeated subsequences should not be used. However, they do not wish to remove all subsequences that are repeated, since in that case no single character could be repeated. This in itself would make the problem too easy for the contestants. Instead it is decided to eliminate all sequences containing an occurrence of two adjoining identical subsequences. Sequences containing such an occurrence will be called “easy”. Other sequences will be called “hard”.
For example, the sequence ABACBCBAD is easy, since it contains an adjoining repetition of the subsequence CB. Other examples of easy sequences are:
- BB
- ABCDACABCAB
- ABCDABCD
Some examples of hard sequences are:
- D
- DC
- ABDAB
- CBABCBA
In order to provide the Quiz Master with a potentially unlimited source of questions you are asked to write a program that will read input lines from standard input and will write to standard output.
Input description
Each input line contains integers nn and LL (in that order), where n>0n>0 and LL is in the range 1≤L≤261≤L≤26. Input is terminated by a line containing two zeroes.
Output description
For each input line prints out the nn-th hard sequence (composed of letters drawn from the first LL letters in the alphabet), in increasing alphabetical order (Alphabetical ordering here corresponds to the normal ordering encountered in a dictionary), followed (on the next line) by the length of that sequence. The first sequence in this ordering is ‘A’. You may assume that for given nn and LL there do exist at least nn hard sequences.
As such a sequence is potentially very long, split it into groups of four (4) characters separated by a space. If there are more than 16 such groups, please start a new line for the 17th group.
Your program may assume a maximum sequence length of 80.
For example, with L=3L=3, the first 7 hard sequences are:
A
AB
ABA
ABAC
ABACA
ABACAB
ABACABA
The sample input
7 3
30 3
0 0
Sample output
ABAC ABA
7
ABAC ABCA CBAB CABA CABC ACBA CABA
28
The main idea of the topic
Enter a n and L, From before L A difficult string of letters ( Adjacent ones do not have the same string ), Sort in dictionary order , Output No n A difficult string .
Ideas
Recursive deep search , Add judgment , Judge the time, just judge the suffix , The previous part has determined that the conditions are met , Just judge the later .
AC Code
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N = 1e5+10;
int n,l,cnt;
int a[N];
int dfs(int t)
{
if(cnt++ == n){// Already found No n individual
for(int i = 0;i < t;i++)// Output time pay attention to the format required by the topic
{
if(i%4 == 0 && i != 0 && i%64 != 0)
cout << " ";
else if(i != 0 && i%64 == 0)
cout << endl;
printf("%c", 'A'+a[i]);
}
if(t%64 != 0)
cout << endl;
cout << t << endl;
return 0;
}
for(int i = 0;i < l;i++){// Deep search traversal
a[t] = i;
int flag = 1;
for(int j = 1;j*2 <= t+1;j++){// Judge whether the conditions of difficult string are met
int flag1 = 1;
for(int k = 0;k <j;k++){
if(a[t-k] != a[t-j-k]){
flag1 = 0;
break;
}
}
if(flag1)
{
flag = 0;
break;
}
}
/*
Judgment method : From the end , If the last one is not equal to the one adjacent to the front, the first one is satisfied ,
Secondly, make two judgments at intervals , In turn , Judge whether there is dissatisfaction .
Because it has been judged before , So each one only needs to be sentenced once .
*/
if(flag){
if(!dfs(t+1))//!dfs The representative found it and returned 0
return 0;
}
}
return 1;
}
int main()
{
while(cin >> n >> l){
cnt = 0;
if(n == 0 && l == 0){
return 0;
}
dfs(0);
}
}
Be careful
Particular attention : Format problem , The title clearly states , Every time 4 One for a group , One line at a time 16 Group , Output length time , If there happens to be one last 16 There is no need to wrap a group , If not , Need to output a newline .
边栏推荐
- Composition of interface
- 从 1.5 开始搭建一个微服务框架——日志追踪 traceId
- [speech processing] speech signal denoising and denoising based on Matlab GUI low-pass filter [including Matlab source code 1708]
- Alibaba Tianchi SQL training camp task4 learning notes
- audiopolicy
- Detailed explanation of pointer and array written test of C language
- Go语言实现原理——Map实现原理
- Global and Chinese market of networked refrigerators 2022-2028: Research Report on technology, participants, trends, market size and share
- Arduino measures AC current
- 终于搞懂什么是动态规划的
猜你喜欢
openresty ngx_lua请求响应
14种神笔记方法,只需选择1招,让你的学习和工作效率提高100倍!
Realize reverse proxy client IP transparent transmission
February 13, 2022-4-symmetric binary tree
Registration and skills of hoisting machinery command examination in 2022
Tensor attribute statistics
Hcip day 11 (BGP agreement)
[speech processing] speech signal denoising and denoising based on Matlab GUI low-pass filter [including Matlab source code 1708]
Using LNMP to build WordPress sites
Arduino measures AC current
随机推荐
LeetCode102. Sequence traversal of binary tree (output by layer and unified output)
Distributed solution selection
Tiktok__ ac_ signature
30 optimization skills about mysql, super practical
Commonly used probability distributions: Bernoulli distribution, binomial distribution, polynomial distribution, Gaussian distribution, exponential distribution, Laplace distribution and Dirac delta d
Composition of interface
实现反向代理客户端IP透传
6-axis and 9-axis IMU attitude estimation
Global and Chinese market of networked refrigerators 2022-2028: Research Report on technology, participants, trends, market size and share
VOT Toolkit环境配置与使用
Element operation and element waiting in Web Automation
派对的最大快乐值
Go语言实现原理——锁实现原理
Nangou Gili hard Kai font TTF Download with installation tutorial
[untitled]
东南亚电商指南,卖家如何布局东南亚市场?
Starting from 1.5, build a micro Service Framework -- log tracking traceid
[digital signal denoising] improved wavelet modulus maxima digital signal denoising based on MATLAB [including Matlab source code 1710]
Overview of Fourier analysis
Global and Chinese markets for welding products 2022-2028: Research Report on technology, participants, trends, market size and share