10941. TF задача

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

Вход. Строка из не более чем 10⁶ символов.

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

Пример входа	Пример выхода
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 реализация

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 = input()

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

else: print(my_bin_search(s))