TF Məsələ#10941
Daxil ol

TF Məsələ (Həll təhlili)

Əgər sətirin ilk simvolu -dirsə, -1 çap edirik. Əks halda, sonuncu simvolunun indeksini binary search (ikili axtarış) ilə tapırıq.

Alqoritmin reallaşması

BinSearch funksiyası ikili axtarış aparır və sonuncu simvolunun indeksini qaytarır.

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++

Proqramın əsas hissəsi. Giriş sətiri oxuyuruq.

cin >> s;

Əgər sətirin ilk simvolu -dirsə, -1 çap edirik.

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

Cavabı çap edirik.

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

Java reallaşması

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 reallaşması

BinSearch funksiyası ikili axtarış aparır və sonuncu simvolunun indeksini qaytarır.

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

Proqramın əsas hissəsi. Giriş sətiri oxuyuruq.

s = input()

Əgər sətirin ilk simvolu -dirsə, -1 çap edirik.

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

Cavabı çap edirik.

else: print(my_bin_search(s))

Python reallaşması — bisect

import bisect

Giriş sətiri oxuyuruq.

s = input()

Əgər sətirin ilk simvolu '', -1 çap edirik.

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

Əks halda cavabı hesablayıb çap edirik.

else:

Mətnin tərsini çevirir. İndi hərflər lüğəvi qaydada sıralanıb ('' < ''). Binary search (ikili axtarış) ilə ilk '' hərfinin mövqeyini (indeks) tapırıq (bu hərf '' -dan dərhal sonra gəlir).

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

İndeksi yenidən hesablamaq lazımdır. Orijinal sətirdə sonuncu '' simvolunun mövqeyini hesablayırıq.

  index = len(s) - index - 1

Cavabı çap edirik.

  print(index)