P151PROH - ROUND 1H - Số ma thuật

Link Sub: http://www.spoj.com/PTIT/problems/P151PROH/
Người Gửi: Dương Lee

• Problem:

Một số ma thuật là số mà được ghép bởi các số 1, 14, 144. Số ma thuật không nhất thiết phải được ghép bởi cả 3 số trên. Các bạn giúp kiểm tra giúp xem một số có là số ma thuất không nhé!

Input

Một dòng duy nhất chứa số n (1 <= n <= 10^9).

Output

In ra “YES” nếu n là số ma thuật và “NO” trong trường hợp ngược lại.

Example:

Input

114144

Output:

YES

Input

111111

Output:

YES

Input

441231

Output:

NO

• Solution:

Vì dãy các số chỉ có 1, 14, 144 vậy nên chỉ cần tìm được một 1 phương án ghép 1, 14 và 144 -> S sao cho S = n thì là số ma thuật.
-> Sử dụng đệ quy để đi tìm các phương án ghép.
VD: Ban đầu có số: 1441144 (ta nhập thành một xâu)
- Các bước chạy:
+ Tìm thấy số đầu 1 -> tìm trong 441144 -> không thấy số nào để ghép tiếp -> dừng;
+ Tìm thấy số đầu 14 -> tìm trong 41144 -> không thấy số nào để ghép tiếp -> dừng;
+ Tìm thấy số đầu 144 -> tìm trong 1144 -> thấy số 1 -> tìm trong 144 -> ... check = 1 khi có thể ghép vừa đủ.

Update: Giờ mình mới nhận ra: Vì không ghép 44, 4 nên nếu có 144 thì 14 và 1 sẽ được bỏ qua, có 14 thì 1 sẽ được bỏ qua (như hình trên). Vậy có thể cải tiến code dưới đây thành O(n) nếu xét 144 trước.

• Code:

C++:

https://ideone.com/jQgbvM

#include <iostream>
using namespace std;

int check = 0;
void find_magic (string s)
{
    int len = s.length();
    string S1="", S2="", S3="";
    if (len >= 1) S1 = S1 + s[0];
    if (len >= 2) S2 = S2 + s[0] + s[1];
    if (len >= 3) S3 = S3 + s[0] + s[1] + s[2];
    if (S1 == "1" && s.length()>=1)
    {
        if (len == 1)
        {
            check = 1;
            return;
        }
        else find_magic (s.substr(1, s.length()-1));
    }
    if (S2 == "14" && len>=2)
    {
        if (len == 2)
        {
            check = 1;
            return;
        }
        else find_magic (s.substr(2, s.length()-2));
    }
    if (S3 == "144" && len>=3)
    {
        if (len == 3)
        {
            check = 1;
            return;
        }
        else find_magic (s.substr(3, s.length()-3));
    }
    return;
}

int main ()
{
    string s;
    cin>>s;
    find_magic (s);
    if (check == 1) cout<<"YES";
    else cout<<"NO";
    return 0;
}

JAVA:

...

Python:

...

Author : DL

Share this

Related Posts