Soluție HackerRank pentru Alien Languages. Include cerința formatată, exemple, explicația pașilor și cod sursă.

  • Problemă: Alien Languages

Cerinta completa

Sophia has discovered several alien languages. Suprisingly, all of these languages have an alphabet, and each of them may contain thousands of characters! Also, all the words in a language have the same number of characters in it.

However, the aliens like their words to be aesthetically pleasing, which for them means that for the [Expresie matematică indisponibilă în copia arhivată] letter of an [Expresie matematică indisponibilă în copia arhivată]-letter alphabet (letters are indexed [Expresie matematică indisponibilă în copia arhivată]):

  • if [Expresie matematică indisponibilă în copia arhivată], then the [Expresie matematică indisponibilă în copia arhivată] letter may be the last letter of a word, or it may be immediately followed by any letter, including itself.

  • if [Expresie matematică indisponibilă în copia arhivată], then the [Expresie matematică indisponibilă în copia arhivată] letter can not be the last letter of a word and also can only be immediately followed by [Expresie matematică indisponibilă în copia arhivată] letter if and only if [Expresie matematică indisponibilă în copia arhivată].

Sophia wants to know how many different words exist in this language. Since the result may be large, she wants to know this number, modulo [Expresie matematică indisponibilă în copia arhivată].

Input Format

The first line contains [Expresie matematică indisponibilă în copia arhivată], the number of test cases. The first line is followed by [Expresie matematică indisponibilă în copia arhivată] lines, each line denoting a test case. Each test case will have two space-separated integers [Expresie matematică indisponibilă în copia arhivată], [Expresie matematică indisponibilă în copia arhivată] which denote the number of letters in the language and the length of words in this language respectively.

Constraints

  • [Expresie matematică indisponibilă în copia arhivată]
  • [Expresie matematică indisponibilă în copia arhivată]
  • [Expresie matematică indisponibilă în copia arhivată]

Output Format

For each test case, output the number of possible words modulo [Expresie matematică indisponibilă în copia arhivată].

Sample Input

3
1 3
2 3
3 2

Sample Output

1
3
6

Explanation

For the first test case, there’s one letter (‘a’) and all the words consist of [Expresie matematică indisponibilă în copia arhivată] letters. There’s only one possibility which is „aaa”.

For the second test case, there are two letters (‘a’ and ‘b’) and all the words are of [Expresie matematică indisponibilă în copia arhivată] letters. The possible strings are „abb”, „bab”, & „bbb”. The words can end only with ‘b’ because [Expresie matematică indisponibilă în copia arhivată] and for ‘a’, it’s [Expresie matematică indisponibilă în copia arhivată]. „aab” is not allowed because ‘a’ can not be followed immediately by ‘a’. For a word of length 4 and alphabet of size 2, „abab” would be allowed.

For the third test case, there are three letters (‘a’, ‘b’ and ‘c’) and all of the words are [Expresie matematică indisponibilă în copia arhivată] letters. The words can only end with ‘b’ or ‘c’. The possible words are „ab”, „ac”, „bb”, „cc”, „bc”, „cb”.

Limbajul de programare folosit: cpp14

Cod:

// https://www.hackerrank.com/challenges/alien-languages

#include <iostream>
#include <cstring>

using namespace std;

#define MODULO 100000007
#define MAX_M 500000
#define MAX_N 100000
#define MAX_L 20

int getPossibleWords(int n, int m) {
    static int words[MAX_M + 1];
    static int mult[MAX_L];
    static int t[MAX_N + 1][MAX_L];

    int i, j, k, nb = n / 2;
    long long d;

    memset(words, 0, sizeof(words));
    memset(mult, 0, sizeof(mult));
    memset(t, 0, sizeof(t));

    for (i = n; i > nb; i--)
        t[i][0] = 1;

    for (j = n, k = 0; j > 0; j /= 2, k++) {
        d = 0;

        for (i = n; i > 0; i--) {
            d = (d + t[i][k]) % MODULO;
            t[i / 2][k + 1] = d;
        }

        for (i = n; i > 0; i--)
            mult[k] = (mult[k] + t[i][k]) % MODULO;
    }

    words[0] = 1;

    for (i = 1; i <= m; i++) {
        d = words[i - 1];
        for (j = 0; mult[j] && i + j <= m; j++)
            words[i + j] = (words[i + j] + (d * mult[j]) % MODULO) % MODULO;
    }

    return words[m];
}

int main() {
    int t, n, m;

    cin >> t;

    for (int i = 0; i < t; i++) {
        cin >> n >> m;
        cout << getPossibleWords(n, m) << endl;
    }

    return 0;
}

Scor obtinut: 1.0

Submission ID: 464613784

Link challenge: https://www.hackerrank.com/challenges/alien-languages/problem

Alien Languages