Hamlet needs your help to solve this very deep and existential question. In front of him is a message from Shakespeare himself (don't question how this makes sense), and it is Hamlet's job to decipher its meaning.
The message consists of English letters as well as spaces. Hamlet is especially interested in whether or not the message contains "be" (without quotation marks and ignoring capitalization) as a substring at any point. For example, if the message were "To BE or not to bE that is the question", then clearly it would contain "be", whereas if the message were "To or not to that is the question", it would not contain "be".
Can you help Hamlet with this daunting task?
The input consists of a single line containing a string $$$s\ (1 \leq |s| \leq 10^3)$$$ denoting Shakespeare's message to Hamlet. It is guaranteed that $$$s$$$ consists only of English letters and spaces, and the first and last characters are guaranteed to be English letters ($$$s$$$ will not begin or end with a space).
The output should consist of a single string, either "yes" or "no" (without quotation marks), denoting whether or not the message contains "be" (without quotation marks) as a substring at any point (ignoring capitalization). The output is case insensitive; if the answer is "yes", then answers such as "Yes", "YES", and "yEs" will also be accepted.
To Be or Not to BE that is the QUESTION
YES
To b or not to b that is the question
NO
Romeo is searching for Juliet, who is located on one of the $$$N (1\leq N\leq 10^5)$$$ points $$$P$$$ located on a line segment at time $$$0$$$. Romeo knows Juliet can move at most a distance $$$1$$$ every minute. Romeo eventually hears Juliet at time $$$d (0\leq d\leq 10^9)$$$ minutes and knows she is between $$$[A, B] (0\leq A\leq B\leq 10^9)$$$. Romeo wants to find the possibilities of where Juliet originally was. Can you help him find the locations that Juliet could have originally been at?
The first line contains $$$N, A, B, d$$$. The next line contains $$$N$$$ space-separated integers $$$P_i (0\leq P_i\leq 10^9)$$$. $$$P$$$ is $$$0$$$-indexed, meaning that the first number on the line is $$$P_0$$$, followed by $$$P_1$$$, and so on...
Output the indices of possible locations Juliet could have been at the start on one space-separated line in ascending order. If there are none, your output should be empty.
10 3 5 14 10 14 17 5 11 13 6 17 10
0 4 7
Shakespeare the Tenth has grown bored of writing plays and sonnets all day and wants to get into painting. However, he feels that painting with color is not very artistic, and instead, he wants to paint with letters.
One day, he finds a $$$N \times N$$$ canvas in his basement and starts his painting career. $$$(0, 0)$$$ is the top-left corner of the canvas, and $$$(N-1, N-1)$$$ is the bottom-right corner. A letter takes up a $$$1 \times 1$$$ region and must be aligned on whole number coordinates. As he begins painting, he realizes that a 3D-like effect can be created by stacking letters on each other. Furthermore, he discovers that some letters look better in a given stack and would like these letters to have a majority (making up strictly more than half of the letters) count, which makes it a beautiful stack.
Shakespeare the Tenth decides to paint conduct $$$Q$$$ painting operations, one at a time. One operation is to paint a letter onto a spot in the canvas, which adds it to the top of its stack. Unfortunately, he is not very good at keeping track of his 3D painting and might also ask you to help him determine whether a stack is beautiful. As an inexperienced painter, he might change his mind a lot; therefore, he might like one letter more than the other for a given stack across different queries. In addition, he might choose to remove the top letter of a stack at any given time. If he decides to remove from a stack that he never began painting, it does not do anything. Can you help Shakespeare the Tenth create his favorite painting?
The first line contains $$$N\ (1 \leq N \leq 100)$$$, $$$Q\ (2 \leq Q \leq 2 \cdot 10^5)$$$, the size of the canvas and the number of queries he will ask/paint respectively.
The next $$$Q$$$ lines contain Shakespeare the Tenth's painting steps, removing step, or queries. Each line starts with an integer, $$$s \in \{0, 1, 2\}$$$. If $$$s = 0$$$, then this is a painting step, if $$$s = 1$$$, then this is a remove step, else (if $$$s = 2$$$) a query.
A painting step is followed by 1 (lowercase English) letter and 2 integers, $$$l, x, y\ (0 \leq x, y \leq N - 1)$$$, representing the letter he is painting and the position where he wants to stack the letter.
A remove step is followed by 2 integers, $$$x, y\ (0 \leq x, y \leq N - 1)$$$, representing the position of stack that he wants to remove from.
A query is followed by 1 letter and 2 integers, $$$l, x, y\ (0 \leq x, y \leq N - 1)$$$, the coordinate of the stack he wants to know is beautiful or not and the letter that he thinks will make the stack beautiful at the moment.
All letters that Shakespeare the Tenth uses are lowercase letters.
For each query, output one line denoting whether the stack is beautiful or not with "yes" for beautiful, and "no" for not beautiful. The output is case insensitive.
2 100 a 1 10 b 0 10 a 1 12 a 1 10 c 0 00 d 0 12 b 0 12 c 0 01 0 12 b 0 1
yes no yes yes
While searching for an open room in the GDC, Macbeth discovers three witches. They prophesy that he will be the highest rated CodeForces competitor at UT.
Elated, Macbeth devises a masterful plan to fulfill the witches' prophecy. Instead of training on CodeForces to improve his rating, he'll gain access to the UT database and forcefully graduate students rated equal to or higher than him.
Macbeth has a list of all the CodeForces accounts connected to UT students, but he doesn't know who's behind each username. He knows the CodeForces usernames of only his friends, who know the CF usernames of only their friends. The network of who knows each other's usernames can be represented as a tree with $$$N$$$ nodes, with Macbeth at node 1. This tree spans all the competitive programmers at UT.
For Macbeth to learn more usernames, he must ask someone whose username he already knows, and this person will tell Macbeth all the usernames they know. Output the minimum number of asks Macbeth must make for him to learn of everyone who has a rating greater than or equal to his.
Line 1: $$$N \:(1 \leq N \leq 10^5)$$$, specifying the number of competitive programmers at UT.
Line 2: $$$r_1\:r_2\: ...\: r_i \:... \:r_n\: (1 \leq r_i \leq 5000)$$$, where $$$r_i$$$ denotes the rating of account $$$i$$$.
Lines $$$3 .. N + 2$$$: $$$p\;q \:(1 \leq p, q \leq N)$$$, specifying that the people behind accounts $$$p$$$ and $$$q$$$ know each other's usernames.
One integer specifying the minimum number of people Macbeth must ask to have the #1 rated CodeForces account at UT.
71000 1400 800 1800 3800 400 9001 21 33 63 45 66 7
2
William recently started studying Shakespeare in his high school English class. However, he is having trouble understanding old English. Every time he comes across an old English word, he searches it up in the dictionary. However, because he has a bad memory, he can only remember the most recent word he searched for.
To help others who struggle with old English, he plans to rewrite all of Shakespeare using modern English. He is very organized and would like to rewrite each word and sentence in order. His friend Anne wants to support him on his journey and has offered to memorize one word for him. If Anne memorizes a word, then William will not have to search it up and can ask Anne instead.
William wants to figure out which word he wants Anne to memorize. As such, for every word $$$w_i$$$, he wants to know how many searches he would have to perform if Anne memorized $$$w_i$$$, and he needs your help.
The first line contains two integers $$$N\ (1 \leq N \leq 10^5)$$$ and $$$M\ (1 \leq M \leq 10^5)$$$ representing the number of words he doesn't know and the number of sentences he needs to rewrite.
The second line contains $$$N$$$ space-separated lowercase words $$$w_i$$$, all distinct, each of which represents a word that William doesn't recognize and has to search up.
The next $$$M$$$ lines each contain space-separated words, each of which represents a sentence that William plans to rewrite. Each sentence consists only of lowercase letters and is terminated with a period. Furthermore, each sentence contains no punctuation other than the period.
It is guaranteed that each string in the input consists of at most 10 characters (excluding punctuation) and that each sentence consists of at least 1 word and at most 10 words.
Output $$$N$$$ integers, one on each line, with the $$$i^\text{th}$$$ integer representing the number of searches William would have to perform if Anne memorized $$$w_i$$$
3 2thou thy speakstspeakst thou speakst.thy speakst thou.
3 4 3
3 3dost thou lovestby my sword beatrice thou lovest me.with my sword ill prove the lie thou speakst.if thou dost seek to have what thou dost hide.
3 2 4
If Anne memorized the word "thou" in sample 1, then William would do the following actions on each word.
This is a total of 3 searches ("speakst," "thy," "speakst").
Shakespeare is writing a new play, but he's struggling to think of what word to use next, so he wants to invent one! To do this, he will start with a given word $$$s$$$, and will perform the following operation any number of times:
Shakespeare wants to know how many distinct words he can construct after any number of operations (possibly none). Unfortunately, Shakespeare doesn't have a computer and he is low on time, so he needs you to do this for him. Since there may be many strings, output this number modulo $$$10^9+7$$$.
The first line of input will contain integers $$$n$$$ and $$$k\ (1 \leq k \leq n \leq 10^6$$$). The second line will contain string $$$s$$$, consisting of $$$n$$$ lowercase English characters.
Output one line containing the answer to the problem (modulo $$$10^9+7$$$).
4 2aabb
4
4 1utpc
24
26 5abcdefghijklmnopqrstuvwxyz
299198957
Cyrano, upon facing Roxane, is elated to have delivered a poetic declaration despite his internal doubts. Soon, another challenge rises in the shape of her now angered suitors. As Cyrano's only weakness is a superficial one, for every parry he swiftly makes a ballade. When he ends the refrain, his sword will have swiftly ended their courage's bane.
Cyrano currently distributes the pastries from Ragueneau's bakery to families around town. There are $$$N$$$ bakeries labeled $$$1$$$ through $$$N$$$, and $$$M$$$ community bakery mailboxes numbered $$$1$$$ through $$$M$$$. Cyrano must make $$$N$$$ total trips, one trip for each bakery, and for each trip he can choose to arrive at a mailbox of his choice. We denote the position of the $$$ith$$$ bakery by $$$x_i$$$ $$$(1\leq i\leq N)$$$, and the position of the $$$jth$$$ mailbox by $$$y_j$$$ $$$(1\leq j\leq M)$$$.
Initially, Cyrano starts from a bakery $$$x_i$$$. From there, traveling from point $$$x_i$$$ to $$$y_j$$$ requires fighting off $$$x_i\cdot y_j$$$ suitors. Upon arriving at destination mailbox $$$y_i$$$, Cyrano is greeted with a horde of $$$k_i$$$ angry suitors (mailboxes can be repeated, in which case $$$k_j$$$ suitors must be fought again). Since he does not want to overwork his sword, Cyrano would prefer to take on the minimum number of total suitors.
Please compute the minimum number of suitors Cyrano has to defeat, modulo $$$10^9+7$$$, to complete his deliveries.
The first line contains two integers $$$N$$$ and $$$M$$$ $$$(1\leq N,M\leq 10^5)$$$, the number of bakeries and number of mailboxes.
The next $$$N$$$ lines contain an integer $$$x_i$$$ $$$(0\leq x_i\leq 10^9)$$$, the location of each bakery.
The next $$$M$$$ lines contain two integers $$$y_j$$$ and $$$k_j$$$ $$$(0\leq y_j, k_j\leq 10^9)$$$, the location of each mailbox and number of suitors gathered at each.
Please print one integer, the amount of suitors Cyrano will have to fight off modulo $$$10^9+7$$$.
4 414584 12 73 20 20
56
8 8141025305055805074220 43361216504740 3532905149711 75166642920615 991828204300097 260601357321301 80737706718972 81406192800643 107037826
204794907
Let us look at the first test case.
Cyrano can initially choose to travel from the first bakery to either the first or third mailbox to fight off $$$5$$$ suitors.
From the second bakery, he will choose to travel to the third mailbox to fight off $$$2+3\cdot 4 = 14$$$ suitors.
From the third bakery, he can either travel to the second or third mailbox to fight off $$$17$$$ suitors.
From the fourth bakery, he will choose to travel to the fourth mailbox to fight off $$$20+ 0\cdot 8=20$$$ suitors.
The total number of suitors he will have to fight is $$$5+14+17+20=56$$$.
Shakespeare is writing a soliloquy for his newest play. The soliloquy is represented as a string of $$$N$$$ characters. Shakespeare has a set of $$$M$$$ distinct words where the sum of the word lengths for all words in the set is no greater than $$$10^5$$$. Shakespeare has $$$Q$$$ intervals that cover some portion of the soliloquy. He wants to know, for each interval, how many substrings in that interval are words in the set.
The first line of input contains $$$N,\ M,\ Q\ (1 \leq N \leq 5\cdot 10^4, 1 \leq M, Q \leq 10^5)$$$.
The second line of input contains a string of size $$$N$$$ representing the soliloquy.
The next $$$M$$$ lines each contain a word in the set. The sum of all $$$M$$$ word lengths is no greater than $$$10^5$$$.
The next $$$Q$$$ lines each contain two numbers $$$l_i, r_i,\ (1 \leq l_i \leq r_i \leq N)$$$ representing the $$$i^{th}$$$ query interval.
Note: All characters in all strings contain only uppercase letters between $$$A$$$ and $$$Z$$$.
Please output $$$Q$$$ lines, where the $$$i^{th}$$$ line contains the answer to the $$$i^{th}$$$ query.
12 4 3ABCDABCDABCDABCDBCA4 75 121 1
3 8 1
5 5 1AAAAAAAAAAAAAAAAAAAA1 5
15
Let's break down the queries in the first sample case.
The first query is an interval on positions $$$[4, 7]$$$ of the soliloquy corresponding to the substring "DABC". In this interval, there is $$$1$$$ occurrence of word "AB", $$$1$$$ occurrence of "BC", and $$$1$$$ occurrence of "A", so the answer is $$$1+1+1=3$$$.
The second query is an interval on positions $$$[5, 12]$$$ of the soliloquy corresponding to the substring "ABCDABCD". In this interval, there are $$$2$$$ occurrences of word "AB", $$$2$$$ occurrences of "CD", $$$2$$$ occurrences of "BC", and $$$2$$$ occurrences of "A", so the answer is $$$2+2+2+2=8$$$.
The third query is an interval on position $$$[1, 1]$$$ of the soliloquy corresponding to the substring "A". In this interval, there is just $$$1$$$ occurrence of word "A", so the answer is $$$1$$$.