Người Gửi: Dương Lee
- Problem:
Những con bò đang chuẩn bị bắt đầu chơi trò “Moo”. Chúng đứng trên một hàng dài, trong đó mỗi con bò trong hàng sẽ nói một chữ cái nhanh nhất có thể. Con bò nào phạm luật đầu tiên thì sẽ thua.
Dãy các kí tự “Moo” có thể kéo dài liên tục và không giới hạn. Chúng sẽ bắt đầu như sau:
m o o m o o o m o o m o o o o m o o m o o o m o o m o o o o
Dãy kí tự được diễn tả như sau: Gọi S(0)là một trong ba kí tự “m o o”. Sau đó dãy kí tự S(k)sẽ bằng dãy S(k-1) và thêm vào “m o … o” với k+2 chữ o, và sau đó cộng thêm một lần cho S(k-1). Ví dụ:
S(0) = "m o o"
S(1) = "m o o m o o o m o o"
S(2) = "m o o m o o o m o o m o o o o m o o m o o o m o o"
Với cách này sẽ tạo được dãy kí tự rất dài, và dãy này sẽ dùng cho game Moo.
Cô bò Bessie muốn biết kí tự thứ N của dãy này là chữ “m” hay chữ “o”. Bạn hãy giúp Bessie nhé!
Input
*Dòng 1: Gồm một số nguyên N(1 <= N <= 10^9).
Output
*Dòng 1: Dòng duy nhất chứa kí tự “m” hoặc “o”.
Example:
Input
11
Output:
m
- Solution:
Ta sẽ quy hoạch thế này:
- Ban đầu: length xâu=3: S_đầu=0, S_giữa=3, S_cuối=3. Vậy là xâu k=0: (moo) chia ra làm 3 đoạn: S_đầu: (0->0), S_giữa: (0->3), S_cuối (0->3);
- Tạo ra các trường hợp tiếp theo theo quy luật của đề:
VD: xâu k=1: (moomooomoo): S_đầu = length_xâu_S0 (moo), S_giữa = S_đầu+1+(k+2) (moomooo), S_cuối = S_giữa + S_đầu (moomooomoo), length xâu = S_cuối.
- Tạo trường hợp i cho đến khi length xâu i >= N;
Sau khi quy hoạch xong ta sẽ đệ quy để tìm vị trí:
- Nếu N > S_đầu && N <= S_giữa: Đệ quy vào trường hợp i-1;
- Nếu N > S_giữa && N <= S_cuối: N=N-S_đầu: (N==1)?m:o
- Nếu N > S_cuối: N=N-S_giữa: Đệ quy vào trường hợp i-1;
- Code:
#include <iostream>
using namespace std;
struct data
{
long long leng;
long long Sd;
long long Sg;
long long Sc;
};
struct data S[200];
void khoitao ()
{
S[0].leng=3;
S[0].Sd=0;
S[0].Sg=3;
S[0].Sc=3;
}
char Dequy (long long n, int cs)
{
if (1<=n && n<=S[cs].Sd) return Dequy (n, cs-1);
else if (S[cs].Sd<n && n<=S[cs].Sg)
{
n=n-S[cs].Sd;
if (n==1) return 'm';
else return 'o';
}
else if (S[cs].Sg<n && n<=S[cs].Sc)
{
n=n-S[cs].Sg;
return Dequy (n, cs-1);
}
}
int main ()
{
khoitao();
int i=0;
long long N;
cin>>N;
while (1)
{
if (S[i].leng>=N) break;
i++;
S[i].Sd=0+S[i-1].leng;
S[i].Sg=S[i].Sd+1+i+2;
S[i].Sc=S[i].Sg+S[i-1].leng;
S[i].leng=S[i].Sc;
}
cout<<Dequy (N, i);
return 0;
}