Algorithm


Problem Name: 2 AD-HOC - beecrowd | 2384

Problem Link: https://www.beecrowd.com.br/judge/en/problems/view/2384

Tradutor Alienígena

 

Por OBI - Olimpíada Brasileira de Informática, 2010 BR Brazil

Timelimit: 1

É de conhecimento público e notório que já fomos visitados por alienígenas diversas vezes. A grande dificuldade que temos, porém, é a comunicação com eles, por causa de grandes diferenças entre as línguas. Além disso, assim como nós, eles também têm várias línguas diferentes.

Com o intuito de auxiliar no processo de tradução, foi criado um método de mapeamento dos símbolos do alfabeto de cada língua alienígena, atribuindo um número inteiro para cada símbolo. Sendo assim, para um alfabeto alienígena com N elementos, atribui-se números de 1 a N a cada um.

O problema é que o encarregado de transcrever os textos alienígenas para números não foi muito cuidadoso e usou o mesmo espaçamento entre dígitos e números. Assim, por exemplo, digamos que para um alfabeto com 32 símbolos, uma sequência que deveria ser “31 20 4 19” virou “3120419”. Como se pode notar, há diferentes maneiras válidas de interpretar essa sequência além da original, como por exemplo “3 1 20 4 19” e “31 20 4 19”. Repare que a transcrição nunca usa zeros à esquerda de um número e, portanto, a sequência “3 12 04 19” é inválida, assim como “31 20 41 9” por conter um número (49) que não corresponde a um símbolo.

Dados a quantidade de símbolos do alfabeto e uma sequência transcrita, determine quantas sequências válidas podem ser formadas.

 

Entrada

 

A entrada é composta por duas linhas. A primeira contém um número inteiro N (1 < N < 10100) que indica a quantidade de símbolos do alfabeto. A segunda linha contém uma cadeia de dígitos de tamanho mínimo 1 e tamanho máximo 100.000 que corresponde a sequência transcrita.

 

Saída

 

Seu programa deve imprimir uma linha com o resto da divisão da quantidade de sequências válidas por 1.000.000.007.

 

 

 

Exemplos de Entrada Exemplos de Saída

32

3120419

4

 

Code Examples

#1 Code Example with C++ Programming

Code - C++ Programming


#include <algorithm>
#include <cstring>
#include <iostream>
using namespace std;
const int MAXN = 1e5 + 100;
typedef long long ll;
const ll MODULO = 1e9 + 7;
string ALFABETO, cadeia;
ll dp[MAXN], N, M;
bool valido(ll ini, ll fim) {
    if (cadeia[ini] == '0') return false;
    if (fim - ini + 1  <  N) return true;
    for (ll i = ini; i  < = fim; i++) {
        if (ALFABETO[i - ini] > cadeia[i]) return true;
        if (ALFABETO[i - ini]  <  cadeia[i]) return false;
    }
    return true;
}
ll solve(ll pos) {
    if (dp[pos] != -1) return dp[pos];
    ll val = 0;
    for (ll quebra = pos; quebra + 1  < = M; quebra++) {
        if (quebra - pos + 1 > N) break;
        if (valido(pos, quebra)) {
            val += solve(quebra + 1);
            val %= MODULO;
        }
    }
    return dp[pos] = val;
}
int main() {
    cin.tie(0);
    ios_base::sync_with_stdio(0);
    cin >> ALFABETO >> cadeia;
    N = ALFABETO.size();
    M = cadeia.size();
    memset(dp, -1, sizeof(dp));
    dp[M] = 1LL;
    cout << solve(0) << endl;
    return 0;
}
Copy The Code & Try With Live Editor

Input

x
+
cmd
32
3120419

Output

x
+
cmd
4
Advertisements

Demonstration


Previous
#2383 Beecrowd Online Judge Solution 2383 Altas Aventuras Solution in C, C++, Java, Js and Python
Next
#2385 Beecrowd Online Judge Solution 2385 Multiplicação de Matrizes Solution in C, C++, Java, Js and Python