TF Завдання#10941

TF Завдання (Розбір)

Якщо першим символом рядка є літера $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;
}

C++

Основна частина програми. Читаємо вхідний рядок $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();
  }
}

Java

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;

Python

Основна частина програми. Читаємо вхідний рядок $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)