10941. TF задача

Дана строка длины n, состоящая из блока символов T, за которым следует блок символов F. Найдите индекс последнего символа T или выведите -1, если символ T отсутствует в строке.

Нумерация символов в строке начинается с 0.

Вход. Одна строка, содержащая не более 10⁶ символов.

Выход. Выведите индекс последнего символа T. Если в строке нет символа T, выведите -1.

Пример входа	Пример выхода
TTTTFF	3

РЕШЕНИЕ

бинарный поиск

Анализ алгоритма

Если первым символом строки является буква F, то выводим -1. В противном случае ищем индекс последнего символа T с помощью бинарного поиска.

Реализация алгоритма

Функция BinSearch выполняет бинарный поиск и возвращает индекс последнего символа T.

int BinSearch(string& s)

{

int l = 0, r = s.size();

while (l < r)

{

int mid = (l + r) / 2;

if (s[mid] == 'T') l = mid + 1;

else r = mid;

}

return l - 1;

}

Основная часть программы. Читаем входную строку s.

cin >> s;

Если первый символ строки F, выводим -1.

if (s[0] == 'F') cout << -1 << endl;

Выводим ответ.

else cout << BinSearch(s) << endl;

Java реализация

import java.util.*;

public class Main

{

static int BinSearch(String s)

{

int l = 0, r = s.length();

while (l < r)

{

int mid = (l + r) / 2;

if (s.charAt(mid) == 'T') l = mid + 1;

else r = mid;

}

return l - 1;

}

public static void main(String[] args)

{

Scanner con = new Scanner(System.in);

String s = con.next();

if (s.charAt(0) == 'F') System.out.println(-1);

else System.out.println(BinSearch(s));

con.close();

}

}

Python реализация

Функция BinSearch выполняет бинарный поиск и возвращает индекс последнего символа T.

def my_bin_search(s):

l = 0; r = len(s)

while l < r:

mid = (l + r) // 2

if (s[mid] == 'T'): l = mid + 1

else: r = mid

return l - 1;

Основная часть программы. Читаем входную строку s.

s = input()

Если первый символ строки F, выводим -1.

if (s[0] == 'F'): print(-1)

Выводим ответ.

else: print(my_bin_search(s))

Python реализация – bisect

import bisect

Читаем входную строку s.

s = input()

Если первый символ строки ‘F’, выводим -1.

if s[0] == 'F':

print(-1)

Иначе вычисляем и выводим ответ.

else:

Инвертируем строку. Теперь буквы в ней расположены в лексикографическом порядке (‘F’ < ‘T’). При помощи бинарного поиска ищем положение (индекс) первой буквы ‘T’ (индекс буквы ‘T’, которая следует сразу за буквой ‘F’).

index = bisect.bisect_right(s[::-1], 'F')

Пересчитываем индекс. Вычисляем позицию последнего символа ‘T’ в исходной строке.

index = len(s) - index – 1

Выводим ответ.

print(index)