Phoenix, a skilled warrior, has been assigned an important mission: to deliver critical information from the city of Nagpur to the stronghold of Mumbai. The journey is filled with danger, as monsters guard the roads connecting different cities. Each road has a certain number of monsters that Phoenix will need to fight.
Phoenix has a special ability that he can use once during his journey. This ability allows him to halve the number of monsters (rounded down to the nearest whole number) on either one road or two consecutive roads. By using this ability wisely, Phoenix can reduce the total number of monsters he has to fight and increase his chances of completing the mission.
Your task is to help Phoenix find the minimum total number of monsters he must face to deliver the information to Mumbai.
The first line contains two integers $$$n$$$ and $$$m$$$ ($$$2 \leq n \leq 10^5$$$ and $$$1 \leq m \leq 2 \cdot 10^5$$$): the number of cities and the number of roads connecting them. The cities are numbered $$$1,$$$ $$$2,$$$ $$$\ldots$$$ $$$n$$$. City $$$1$$$ is Nagpur, and city $$$n$$$ is Mumbai.
After this, there are $$$m$$$ lines describing the roads. Each line contains three integers $$$u$$$, $$$v$$$, and $$$w$$$ ($$$1 \leq u, v \leq n$$$ and $$$1 \leq w \leq 10^9$$$): a road starts at city $$$u$$$, ends at city $$$v$$$, and has $$$w$$$ monsters on that road. Each road is unidirectional.
You can assume that it is always possible to get from Nagpur to Mumbai.
Output a single integer — the minimum total number of monsters Phoenix must face to deliver the information from Nagpur to Mumbai.
5 61 2 52 3 23 5 11 4 104 5 52 4 3
4
2 11 2 5
2
6 81 2 71 3 42 4 32 5 23 4 64 6 25 6 43 5 8
6
Thanos, the most feared villain in the universe, had conquered countless worlds. But there was one secret, one weakness that haunted him: the Palindrome Sequence. A mysterious force, ancient and powerful, had once foretold that a properly formed sequence of palindromes could undo his cosmic power.
Spidey stumbled upon this knowledge during a secret mission. He learned that the only way to shatter the invincibility of Thanos was to create a palindrome sequence. Since he was always out of school, he needs your help to defeat Thanos.
You are given a string $$$s$$$ of length $$$n$$$ containing lowercase letters.
A palindrome sequence is a sequence containing only palindromes of size $$$m$$$ $$$(m\ge2)$$$ and has at least $$$2$$$ palindromes. (All palindromes are of equal size)
Your task is to determine whether or not it is possible to defeat Thanos by creating a palindrome sequence by re-arranging the given string and if so, create a palindrome-sequence.
The first line contains a single integer $$$t$$$ $$$(1\le t \le 10^4)$$$ — the number of testcases.
The only line of each testcase contains the string $$$s$$$ of size $$$n$$$ $$$(1\le n\le2\cdot10^5)$$$. Sum of $$$n$$$ over all testcases does not exceed $$$2\cdot10^5$$$.
For each testcase,
If possible,
If not possible, output $$$-1$$$.
5abbccaabcabcabcdotslashracecardeed
2 ccaabb 3 bbbcccaaa -1 -1 2 eedd
You are given a reverse binary string of a number $$$n$$$.
Alice and Bob are playing a game.
The play starts with the number $$$n$$$. In each turn a player can choose any one of the following moves:
The player who is unable to play wins the game.
Bob starts the game. Determine the winner if both Alice and Bob play optimally.
The first line contains a single integer $$$t$$$ $$$(1 \le t \le 10_{}^3)$$$ – the number of test cases. The description of the test cases follows.
The first line of each test case contains a single integer $$$x$$$ $$$(1 \le x \le 34)$$$ — the length of binary string.
The second line of each test case contains a reverse binary string of $$$n$$$.
For each test case print single world in a new line:
Note that the output is case sensitive.
3 2 11 3 001 3 101
BOB ALICE BOB
Harsh has started a business of trading scrap along with his friend. The profit he makes on day $$$1$$$ is $$$0$$$, on day $$$2$$$ is $$$1$$$, on day $$$3$$$ is $$$3$$$, on day $$$4$$$ is $$$6$$$, on day $$$5$$$ is $$$10$$$. More formally, the increment in Harsh's profit increases by one every day.
Harsh has a girlfriend, and he goes to her father to ask for permission for the marriage. Her father wants to know how much money Harsh made that day. Harsh is stressed and asks for your help to find his profit today.
Help him with the calculation of the profit if he asks for marriage on the $$$d$$$th day.
The first line will contain the integer $$$t$$$ $$$(1 \le t \le 10^4)$$$ — The number of test cases.
The next $$$t$$$ lines will each contain a single integer $$$d$$$, where $$$(1 \le d \le 10^9)$$$ — The current number of days.
For each test output a single integer — The profit on the $$$dth$$$ day.
3 5 6 3
10 15 3
In a magical land, the currency is based on certain $$$denominations$$$. These $$$denominations$$$ (coins) are of the order $$$11,111,1111,11111,...$$$ and so on.
Gopal has bought an item, determine if it is possible for him to pay with the help of these coins.
He can use any coin $$$any$$$ number of times.
The input consists of multiple test cases.
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — The number of test cases.
Each test case $$$t$$$ contains a single integer $$$n$$$ ($$$1 \le n \le 10^9$$$) — Cost of the item.
For each test case, output YES if it is possible to pay, otherwise output NO.
33314469
YES YES NO
For $$$n = 33$$$, Gopal can use three coins of $$${11}$$$ ,so the output is YES.
For $$$n = 144$$$, Gopal can use one $$$\textbf{coin}$$$ of $$${111}$$$ and three coins of $$${11}$$$ to make 144, so the output is YES.
For $$$n = 69$$$, no combination is possible, so the output is NO.
In the world of Dr. Numerus, machines communicate using special codes that follow a strict rule: the digits of a number must follow a specific pattern. Odd digits must appear at odd indices, and even digits must appear at even indices (indices are 1-based). Given a number $$$N$$$, your task is to determine how many numbers from $$$0$$$ to $$$N$$$ follow this pattern.
The only line contains single integer $$$N$$$ $$$(1 \le N \le 10^{18})$$$
Print a single integer — the number of valid numbers between $$$0$$$ and $$$N$$$ that have odd digits at odd indices and even digits at even indices.
12
7
38
15
9724
755
The possible numbers for $$$N = 12$$$ are $$$1$$$, $$$3$$$, $$$5$$$, $$$7$$$, $$$9$$$, $$$10$$$ and $$$12$$$
Roshan has devised an intriguing card game for his friends Gopal and Vasu. He presents them with a deck of cards, each labeled with an integer, and challenges them to find the maximum value of a special expression based on the cards in any sub-deck. The value of special expression of a sub-deck is determined using the following rule:
A sub-deck is any contiguous sequence (containing atleast 1 card) of cards drawn from the original deck. Gopal and Vasu must find the sub-deck that maximizes the value of this expression. While Gopal thinks about calculating the value for each possible sub-deck, Vasu suspects there might be a more efficient way to figure it out.
Can you help them determine the highest value of special expression?
Each test contains multiple test cases. The first line contains a single integer t $$$(1 \le t \le 10_{}^3)$$$ — the number of test cases. The description of the test cases follows.
The first line of each test case contains one integer n $$$(1 \le n \le 10_{}^3)$$$ — the number of cards.
The second line of each test case contains n integers $$$a_1 , a_2 , ... , a_n$$$ $$$(1 \le a_i \le 10_{}^6)$$$ — the number of cards of type i, for each $$${1 \le i \le n}$$$ .
It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10_{}^3$$$.
For each test case, output a single integer — the maximum possible value of the special expression.
561 2 3 4 5 685 7 3 8 3 9 10 166 3 3 3 5 565 6 4 1 4 598 6 4 2 1 3 5 7 9
1 2 0 1 2
In the first testcase, the maximum possible value of the special expression is when we only select the first card.
In the third testcase, the maximum possible value of the special expression is when we select the subdeck starting at third and ending at fourth card.
In the last testcase, the maximum possible value of the special expression is when we select the subdeck starting at fifth and ending at ninth card $$$1,3,5,7,9$$$.
We are in the year, 2050 and AI has advanced to a whole new level. AI is planning to take over humans but needs to communicate with one another without human interception. To do so they decide to create a language of their own.
There are many levels of AI bots from level-1 to level-$$$n$$$.
The bots perform the following tasks:
Spidey being the savior he is, decides to learn this language to stop AI. How many words will he have to learn to stop them if $$$t$$$ $$$(1\le t \le 10^4)$$$ minutes have passed?
The only input line consists of three integers $$$n$$$ $$$(1\le n\le 100)$$$ — Highest level of the bots, $$$k$$$ $$$(1\le k \le 10^9)$$$ — Initial number of level-$$$n$$$ bots and $$$t$$$ $$$(1\le t \le 10^4)$$$ — Time passed.
Output a single integer — The number of words Spidey has to learn after $$$t$$$ minutes have passed. Since the answer can be huge, output it modulo $$$10^9 + 7$$$.
5 10 40
560
40 100 50
0
10 10 100
1847560
In testcase 1 we have level-5 bots.