Detective Task Codeforces Solution | Codeforces Problem Solution 2022

Detective Task Codeforces Solution | Codeforces Problem Solution 2022 

C. Detective Task

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

Polycarp bought a new expensive painting and decided to show it to his 𝑛$n$ friends. He hung it in his room. 𝑛$n$ of his friends entered and exited there one by one. At one moment there was no more than one person in the room. In other words, the first friend entered and left first, then the second, and so on.

It is known that at the beginning (before visiting friends) a picture hung in the room. At the end (after the 𝑛$n$-th friend) it turned out that it disappeared. At what exact moment it disappeared — there is no information.

Solution Click Below:- CLICK HERE

Polycarp asked his friends one by one. He asked each one if there was a picture when he entered the room. Each friend answered one of three:

• no (response encoded with 0);
• yes (response encoded as 1);
• can't remember (response is encoded with ?).

Food for Animals Codeforces Solution | Codeforces Problem Solution 2022 

Make It Increasing Codeforces Solution | Codeforces Problem Solution 2022 

Detective Task Codeforces Solution | Codeforces Problem Solution 2022 

Vertical Paths Codeforces Solution | Codeforces Problem Solution 2022 

Replace With the Previous, Minimize Codeforces Solution 

Vlad and Unfinished Business Codeforces Solution 

Sorting Pancakes Codeforces Solution 

Everyone except the thief either doesn't remember or told the truth. The thief can say anything (any of the three options).

Polycarp cannot understand who the thief is. He asks you to find out the number of those who can be considered a thief according to the answers.

Input

The first number 𝑡$t$ (1≤𝑡≤104$1\le t\le {10}^4$) — the number of test cases in the test.

The following is a description of test cases.

The first line of each test case contains one string 𝑠$s$ (length does not exceed 2⋅105$2\cdot {10}^5$) — a description of the friends' answers, where 𝑠𝑖$s_i$ indicates the answer of the 𝑖$i$-th friend. Each character in the string is either 0 or 1 or ?.

The given regularity is described in the actual situation. In particular, on the basis of answers, at least one friend can be suspected of stealing a painting.

It is guaranteed that the sum of string lengths over the entire input data set does not exceed 2⋅105$2\cdot {10}^5$.

Output

Output one positive (strictly more zero) number – the number of people who could steal the picture based on the data shown.

Join Now for Solution:-