問題一覧 > 通常問題

No.2454 Former < Latter

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 83
作問者 : srjywrdnprkt / テスター : 👑 p-adic
3 ProblemId : 9858 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2023-08-21 08:05:57

問題文

英小文字のみからなる長さ NN の文字列 S=S1S2⋯SNS=S_1S_2\cdots S_N が与えられます。

1≤i≤N−11\leq i\leq N-1 を満たす整数 ii のうち、SS を ii 文字目で分割することで得られる文字列の前半を U=S1⋯SiU=S_1\cdots S_i、後半を V=Si+1⋯SNV=S_{i+1}\cdots S_N とするとき、UU が辞書順で VV より真に小さくなるものの総数を求めてください。

TT 個のテストケースが与えられるので、それぞれについて答えを求めてください。

入力

TT
case1case_1
⋮\vdots
caseTcase_T
ここで、caseicase_i とは ii 個目のテストケースである。各テストケースは以下の形式で与えられる。 
NN
SS

入力は以下の制約を満たす。

  • T,NT, N は整数
  • 1≤T1\leq T
  • 2≤N2\leq N
  • SS は英小文字のみからなる長さ NN の文字列
  • 11 個の入力に含まれるテストケースについて、それらの NN の総和は 3×1053\times 10^5 を超えない。

出力

TT 行出力してください。ii 行目には ii 番目のテストケースに対する答えを出力してください。

サンプル

サンプル1
入力
3
6
banana
26
abcdefghijklmnopqrstuvwxyz
7
xxxxxxx
出力
2
25
3

11 つ目のテストケースについて、

  • i=1i=1 のとき、U=b,V=ananaU=b, V=anana で U>VU > V です。
  • i=2i=2 のとき、U=ba,V=nanaU=ba, V=nana で U<VU < V です。
  • i=3i=3 のとき、U=ban,V=anaU=ban, V=ana で U>VU > V です。
  • i=4i=4 のとき、U=bana,V=naU=bana, V=na で U<VU < V です。
  • i=5i=5 のとき、U=banan,V=aU=banan, V=a で U>VU > V です。
よって、条件を満たす ii は i=2,4i=2, 4 の 22 個あります。

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。