核子聚变_搜狗笔试题

请设计一个程序，在规定步数内，成功的使得一个原子核队列完全湮灭。

7种原子核(用A-G表示)，排成一条直线队列，在初始状态下它们是稳定的。

如果我们发射一个额外的原子核插入到队列，如果插入的位置没有形成大于等于3个相同的原子核的序列，那么队列继续保持稳定。

如果该位置上相邻的三个或以上的原子核种类相同，就会诱发聚变湮灭成能量散失；然后队列上剩下的左右两半会受外部压力重新拼接在一起，拼接点两侧如果类型相同，且拼接后形成三个或以上连续相同序列，则连锁反映继续聚变湮灭。

为了方便描述插入位置，假定队列长度为n，我们把对列最左端外侧位置编号为0，右端外侧位置编号为n，共有n+1个位置。

例如：

AAABC，如果把一个A插入到位置4（或位置5）的时候，队列会变成AAABAC，继续稳定存在。

AABBCCA，如果把一个C插入到位置4（或位置5,6）的时候，会形成3个C，之后3个C会湮灭，队列变成AABBA，重新恢复稳定。

BAABBCCBACCB，一个C色球插入到位置5（或位置6,7）的时候，会触发连锁反应消去的过程如下（"+"表示拼接点）：

BAABB+C+CCBACCCB => BAABB+BACCCB => BAA+ACCCB => B+CCCB => BCCCB (稳定)

注意最后剩下3个连续的C，是因为最后一步拼接时，拼接点左右类型并不相同，不会触发连锁反应。

每在队列中新插入一个原子核，记为一步；每一步可插入任意类型的原子核。

本题给出1）初始的队列，2）要求在几步之内达成完全湮灭。

要求选手给出一个消去过程，将所有的原子核都聚变湮灭。该过程必须在给定的步数上限之内完成才算正确。

请选手注意，本题并不要求最优解，只需要给出一个不超过步数上限的解即可。

共两行，第1行是一行字母(长度<=200)，表示初始原子核的序列，不同的字母表示不同的类型，第2行是一个十进制整数（<=100），表示要求选手在多少步完成全部湮灭。

本题45%的case，初始字符串长度不大于30。

例如：

AAABBAAACCABDCAABC

10

若干行，每一行是一步，包含一个字母和一个数字，用空格分开；分别表示为这一步要插入的原子核类型，以及插入的位置。0表示最左端，n表示第n个字母的右侧。
例如对于上述的例子输入的的合法输出可以是：

C 8
C 3
C 3
D 5
D 5
B 0
B 0
C 0
C 0
这个输出文件共9行，小于输入文件的步数限制10，因此这个消去过程成立，该case通过。

注意：合法输出不唯一，也不要求最优解。

下面具体解释上述消去序列的每一步的输出和变化如下
C 8 ：AAABBAAACCCABDDAA => AAABBAAA+ABDCAABC => AAABB+BDCAABC => AAADDAA
C 3 ：AAACDCAABC
C 3 ：AAACCDCAABC
D 5 ：AAACCDDCAABC
D 5 ：AAACCDDDCAABC => AAACC+CAABC => AAA+AABC => BC
B 0 ：BBC
B 0 ：BBBC => C
C 0 ：CC
C 0 ：CCC => empty

1）球的颜色最多7种。
2）表示颜色的字符从大写字母A开始。2种颜色的字符是A和B，3种是A，B，C。依次递推，表示7种颜色的字符是A，B，C，D，E，F，G。
3）初始序列长度最长为200。
4）消去的步骤限制最大为100。
5）给定的初始球序列可能存在3个或者更长的球相连的情况，但是这些子序列不会自动消除。
6）消去序列并不是唯一的，不同的消去序列只要符合消去规则，都算作正确。例如对于如下的序列
AABB
如果消去步数的上限为2，那么以下的序列都是正确的。
序列1：
A 0
B 0
序列2：
B 2
A 0
序列3：
B 1
A 2
序列4：
A 1
B 0
序列5：
A 0
B 1
序列6：
A 1
B 1
序列7：
B 0
A 2
序列8：
A 2
B 1
序列9：
A 2
B 2

#include <iostream> #include <string> #include <vector> using namespace std; int main() { string initialSequence; cin >> initialSequence; int stepsLimit; cin >> stepsLimit; int n = initialSequence.length(); vector<pair<char, int>> steps; // Function to simulate the fusion process auto fuse = [&]() { int i = 0; while (i < n) { char currentAtom = initialSequence[i]; int count = 0; while (i < n && initialSequence[i] == currentAtom) { i++; count++; } if (count >= 3) { steps.push_back({currentAtom, i}); initialSequence.insert(i, 1, currentAtom); n++; } } }; // Perform fusion steps until reaching the limit while (steps.size() < stepsLimit) { fuse(); } // Output the steps for (const auto& step : steps) { cout << step.first << " " << step.second << endl; } return 0; }

class Solution: def findMinStep(self, board: str, cost:int) -> int: def elimination(s, start): if start < 0: return s # 从start开始对s进行消去 len_s = len(s) if len_s <= 2&nbs***bsp;start==len_s-1: return s if s[start+1]!=s[start]: return s l = start r = start while l > 0 and s[l - 1] == s[start]: l -= 1 while r < len_s - 1 and s[r + 1] == s[start]: r += 1 if r - l <= 1: return s else: temp = s[:l] + s[r + 1:] return elimination(temp, l - 1) def dfs(board,cost,step): if (not board) and cost>=0: return True,step if cost<=0: return False,[] i =0 while i<len(board): res = cost restep = step[:] j = i+1 while j<len(board) and board[i]==board[j]: j+=1 if j-i==1: restep+=[board[i]+' '+str(i),board[i]+' '+str(i)] res -= 2 temp = elimination(board[:i]+board[i]+board[i]+board[i:],i) else: restep+=[board[i]+' '+str(i)] res -= 1 temp = elimination(board[:i] + board[i] + board[i:], i) flag,restep = dfs(temp,res,restep) if flag: return True,restep else: i = j return False,[] flag,step = dfs(board,cost,[]) return step if flag else [] board = input() cost = int(input()) k = Solution().findMinStep(board,cost) for i in k: print(i)

核子聚变

输入描述:

输出描述:

输入

输出

备注:

问题信息

热门推荐

相关试题