290E - HQ - CodeForces Solution


*special problem constructive algorithms *2500

Please click on ads to support us..

Python Code:

a = input()
b = []
h = ''
c = 0
for i in a:
	if i == 'Q':
		c += 1
if c == 0:
	print('Yes')
	exit(0)
r = -1
for i in range(1001):
	if i*i == c:
		r = i
		break
if r == -1:
	print('No')
	exit(0)
h = [a.split('Q')[0], a.split('Q')[-1]]
c = [len(h[0]), len(h[1])]
if c[0] % 2 != 0 or c[1] % 2 != 0:
	print('No')
	exit(0)
c[0] //= 2
c[1] //= 2
resp = ''
i = c[0]
while True:
	if i >= len(a):
		break
	if r == 0 and a[i] == 'Q':
		break
	resp += a[i]
	if r == 0 and a[i] == 'H':
		c[1] -= 1
	if c[1] == 0 and r == 0:
		break
	if a[i] == 'Q':
		r -= 1
	if r == -1:
		print('No')
		exit(0)
	i += 1


def hq(a):
	resp = ''
	for i in a:
		if i == 'H':
			resp += 'H'
		else:
			resp += a
	return resp

if a == hq(resp):
	print('Yes')
else:
	print('No')


Comments

Submit
0 Comments
More Questions

97. Interleaving String
543. Diameter of Binary Tree
124. Binary Tree Maximum Path Sum
1465. Maximum Area of a Piece of Cake After Horizontal and Vertical Cuts
501A - Contest
160A- Twins
752. Open the Lock
1535A - Fair Playoff
1538F - Interesting Function
1920. Build Array from Permutation
494. Target Sum
797. All Paths From Source to Target
1547B - Alphabetical Strings
1550A - Find The Array
118B - Present from Lena
27A - Next Test
785. Is Graph Bipartite
90. Subsets II
1560A - Dislike of Threes
36. Valid Sudoku
557. Reverse Words in a String III
566. Reshape the Matrix
167. Two Sum II - Input array is sorted
387. First Unique Character in a String
383. Ransom Note
242. Valid Anagram
141. Linked List Cycle
21. Merge Two Sorted Lists
203. Remove Linked List Elements
733. Flood Fill