Постановка задачи
В ряду N мест. Вам дана строка S длины N; для каждого действительного ii i-й символ S равен «0», если i-е место пусто, или «1», если на этом месте кто-то сидит.
Два человека являются друзьями, если они сидят рядом друг с другом. Два друга всегда входят в одну группу друзей. Сможете ли вы найти общее количество групп?
Вход
- Первая строка входных данных содержит единственное целое число T, обозначающее количество тестовых случаев. Ниже приводится описание T тестовых случаев.
- Первая и единственная строка каждого теста содержит одну строку S.
Вывод
Для каждого набора входных данных выведите одну строку, содержащую одно целое число — количество групп.
Ограничения
- 1≤T≤50
- 1≤N≤105
Подзадачи
Подзадача №1 (100 баллов): исходные ограничения
Пример ввода
4
000
010
101
01011011011110Пример вывода
0
1
2
4Объяснение
Пример 1. Поскольку все места свободны, количество групп равно 0.
Пример 2. Поскольку занято только одно место, число групп равно 1.
Пример 3: Здесь заняты два места, но, поскольку они не являются смежными, люди, сидящие на них, принадлежат к разным группам.
Пример 4. Здесь у нас есть 4 группы друзей размером 1, 2, 2 и 4 соответственно. То есть первая группа занимает 2-е место, вторая группа — 4-е и 5-е места, третья группа — 7-е и 8-е места, а четвертая группа — места с 10-го по 13-е.
Код (решение)
Код был реализован на Java
/* package codechef; // don't place package name! */
import java.util.*;
import java.lang.*;
import java.io.*;
class Codechef
{
public static void main (String[] args) throws java.lang.Exception
{
Scanner sc = new Scanner(System.in);
int t = sc.nextInt();
int grp = 0;
while(t-- > 0){
String str = sc.next();
int i=0, n = str.length();
int res = 0;
while(i<n) {
boolean goes = false;
while(i<n && str.charAt(i) == '1') {
i++;
goes = true;
}
if(goes) res++;
else i++;
}
System.out.println(res);
}
}
}
Надеюсь, вам понравилась статья. Пожалуйста, поставьте 50 аплодисментов этой статье и подписывайтесь на меня, чтобы не пропустить новые блоги, связанные с программированием.
Ссылки
