Skip to content

Instantly share code, notes, and snippets.

@lambda-fairy
Last active January 11, 2019 20:34

Revisions

  1. lambda-fairy revised this gist Jan 11, 2019. 1 changed file with 1 addition and 1 deletion.
    2 changes: 1 addition & 1 deletion twilight-2.md
    Original file line number Diff line number Diff line change
    @@ -40,7 +40,7 @@ you must only output the last 5 digits of each number.
    For example, if the answer is `987654321`,
    output `54321` instead.

    # Subtasks
    ## Subtasks

    * `N ≤ 1000` (25%)
    * No restrictions (75%)
  2. lambda-fairy revised this gist Dec 29, 2018. 1 changed file with 4 additions and 4 deletions.
    8 changes: 4 additions & 4 deletions twilight-2.md
    Original file line number Diff line number Diff line change
    @@ -24,21 +24,21 @@ given the specification for a spell and the number of times she casts it.
    ## Input

    The first line will contain four space-separated integers,
    `0 ≤ A, B, C, D 10`,
    `0 ≤ A, B, C, D < 10`,
    which specify the spell.

    The second line will contain one integer,
    `0 ≤ N 10⁹`.
    `0 ≤ N < 10⁹`.
    This is the number of times Twilight wants to cast the spell.

    ## Output

    Output two space-separated integers: the final number of ukeleles and vuvuzelas, respectively.

    As these numbers can be large,
    you must only output the last 6 digits of each number.
    you must only output the last 5 digits of each number.
    For example, if the answer is `987654321`,
    output `654321` instead.
    output `54321` instead.

    # Subtasks

  3. lambda-fairy revised this gist Dec 25, 2018. 1 changed file with 5 additions and 0 deletions.
    5 changes: 5 additions & 0 deletions twilight-2.md
    Original file line number Diff line number Diff line change
    @@ -39,3 +39,8 @@ As these numbers can be large,
    you must only output the last 6 digits of each number.
    For example, if the answer is `987654321`,
    output `654321` instead.

    # Subtasks

    * `N ≤ 1000` (25%)
    * No restrictions (75%)
  4. lambda-fairy revised this gist Dec 25, 2018. 1 changed file with 1 addition and 3 deletions.
    4 changes: 1 addition & 3 deletions twilight-2.md
    Original file line number Diff line number Diff line change
    @@ -15,7 +15,7 @@ she'll have `2(2u + 3v) + 3(5u + v) = 19u + 9v` ukeleles and `5(2u + 3v) + (5u +
    In general,
    a spell can transform `u` ukeleles and `v` vuvuzelas
    into `Au + Bv` ukeleles and `Cu + Dv` vuvuzelas,
    where `A`, `B`, `C`, and `D` are constants particular to the spell.
    where `A`, `B`, `C`, and `D` are constants specific to the spell.

    Help Twilight figure out how many ukeleles and vuvuzelas she would have,
    given the specification for a spell and the number of times she casts it.
    @@ -26,8 +26,6 @@ given the specification for a spell and the number of times she casts it.
    The first line will contain four space-separated integers,
    `0 ≤ A, B, C, D ≤ 10⁹`,
    which specify the spell.
    Given `u` ukeleles and `v` vuvuzelas,
    casting the spell will result in `Au + Bv` ukeleles and `Cu + Dv` vuvuzelas.

    The second line will contain one integer,
    `0 ≤ N ≤ 10⁹`.
  5. lambda-fairy revised this gist Dec 25, 2018. 1 changed file with 32 additions and 36 deletions.
    68 changes: 32 additions & 36 deletions twilight-2.md
    Original file line number Diff line number Diff line change
    @@ -1,47 +1,43 @@
    # Twilight Sparkle's Combinatorial Research
    # Twilight Sparkle's Magical Research

    After an unfortunate accident (involving a phone booth, a pair of ducks, and a peanut butter sandwich) the administration has vowed to clamp down on Twilight's magical research.
    In particular, Twilight will soon be banned from casting spells that are longer than some limit.
    While experimenting with her spells,
    Twilight Sparkle noticed something peculiar:
    she would often end up with more ingredients than she started with.

    To plan her work going forward, Twilight needs to answer this question:
    For example,
    if she casts the *Boulanger* spell on `u` ukeleles and `v` vuvuzelas,
    she would end up with `2u + 3v` ukeleles and `5u + v` vuvuzelas afterward.

    > How many different safe spells can be created, given a limit on the length of the spell?
    This effect can stack:
    if she casts *Boulanger* again,
    she'll have `2(2u + 3v) + 3(5u + v) = 19u + 9v` ukeleles and `5(2u + 3v) + (5u + v) = 15u + 16v` vuvuzelas.

    ## Background
    In general,
    a spell can transform `u` ukeleles and `v` vuvuzelas
    into `Au + Bv` ukeleles and `Cu + Dv` vuvuzelas,
    where `A`, `B`, `C`, and `D` are constants particular to the spell.

    A spell is a non-empty finite sequence of **A**pples, **B**ananas, or **C**iwifruit.

    Spells can be **safe** or **unsafe**.
    An unsafe spell contains one or more of the following patterns:

    | Pattern | Name |
    | --- | --- |
    | `AAAAA` | Appleboom |
    | `ABBA` | Stockholm Syndrome |
    | `ABCABC` | Double Rainbow |

    A safe spell contains none of these patterns.

    ### Examples

    `BAAAAAB` is unsafe, as it contains an Appleboom.

    `AAAACA` is safe.
    While it has five Apples, the Ciwifruit in between means that it can't form an Appleboom.

    `ABBABBA` is unsafe, as it contains two (overlapping) Stockholm Syndromes.

    `ABBAAAAA` is also unsafe, as it contains *both* a Stockholm and an Appleboom.
    They don't cancel out!

    `CBACBA` is safe.
    It has the same fruit as a Double Rainbow, but the fruit are in the wrong order.
    Help Twilight figure out how many ukeleles and vuvuzelas she would have,
    given the specification for a spell and the number of times she casts it.
    (Whether that is a good idea or not is out of scope for this task.)

    ## Input

    The input will consist of a single line, containing one integer `0 ≤ N ≤ 1000000`.
    This is the limit on the length of the spell.
    The first line will contain four space-separated integers,
    `0 ≤ A, B, C, D ≤ 10⁹`,
    which specify the spell.
    Given `u` ukeleles and `v` vuvuzelas,
    casting the spell will result in `Au + Bv` ukeleles and `Cu + Dv` vuvuzelas.

    The second line will contain one integer,
    `0 ≤ N ≤ 10⁹`.
    This is the number of times Twilight wants to cast the spell.

    ## Output

    Output a single integer: the number of distinct safe spells that have length less than or equal to `N`.
    Output two space-separated integers: the final number of ukeleles and vuvuzelas, respectively.

    As these numbers can be large,
    you must only output the last 6 digits of each number.
    For example, if the answer is `987654321`,
    output `654321` instead.
  6. lambda-fairy revised this gist Jun 12, 2018. 1 changed file with 6 additions and 6 deletions.
    12 changes: 6 additions & 6 deletions twilight-2.md
    Original file line number Diff line number Diff line change
    @@ -1,11 +1,11 @@
    # Twilight Sparkle's Combinatorial Research

    After an unfortunate accident, the budget for Twilight's magic research was cut significantly.
    Now she has to work with limited resources.
    After an unfortunate accident (involving a phone booth, a pair of ducks, and a peanut butter sandwich) the administration has vowed to clamp down on Twilight's magical research.
    In particular, Twilight will soon be banned from casting spells that are longer than some limit.

    To plan her work going forward, Twilight needs to answer this question:

    > How many different safe spells can be created, given a limit on the number of each resource?
    > How many different safe spells can be created, given a limit on the length of the spell?
    ## Background

    @@ -39,9 +39,9 @@ It has the same fruit as a Double Rainbow, but the fruit are in the wrong order.

    ## Input

    The input will consist of a single line, containing three integers `0 ≤ A, B, C ≤ 100`.
    These each represent the limits on the number of Apples, Bananas, and Ciwifruits respectively.
    The input will consist of a single line, containing one integer `0 ≤ N ≤ 1000000`.
    This is the limit on the length of the spell.

    ## Output

    Output a single integer: the number of distinct safe spells that can be cast with the given resources.
    Output a single integer: the number of distinct safe spells that have length less than or equal to `N`.
  7. lambda-fairy revised this gist Jun 12, 2018. 2 changed files with 0 additions and 0 deletions.
    File renamed without changes.
  8. lambda-fairy renamed this gist Jun 12, 2018. 1 changed file with 2 additions and 4 deletions.
    Original file line number Diff line number Diff line change
    @@ -1,8 +1,6 @@
    # Twilight Sparkle's Magical Research
    # Twilight Sparkle's Combinatorial Research

    Twilight Sparkle is researching some more magic spells.

    After an unfortunate accident, the budget for Twilight's research was cut significantly.
    After an unfortunate accident, the budget for Twilight's magic research was cut significantly.
    Now she has to work with limited resources.

    To plan her work going forward, Twilight needs to answer this question:
  9. lambda-fairy revised this gist Jun 12, 2018. 1 changed file with 49 additions and 0 deletions.
    49 changes: 49 additions & 0 deletions twilight-sparkle-magical-research.md
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,49 @@
    # Twilight Sparkle's Magical Research

    Twilight Sparkle is researching some more magic spells.

    After an unfortunate accident, the budget for Twilight's research was cut significantly.
    Now she has to work with limited resources.

    To plan her work going forward, Twilight needs to answer this question:

    > How many different safe spells can be created, given a limit on the number of each resource?
    ## Background

    A spell is a non-empty finite sequence of **A**pples, **B**ananas, or **C**iwifruit.

    Spells can be **safe** or **unsafe**.
    An unsafe spell contains one or more of the following patterns:

    | Pattern | Name |
    | --- | --- |
    | `AAAAA` | Appleboom |
    | `ABBA` | Stockholm Syndrome |
    | `ABCABC` | Double Rainbow |

    A safe spell contains none of these patterns.

    ### Examples

    `BAAAAAB` is unsafe, as it contains an Appleboom.

    `AAAACA` is safe.
    While it has five Apples, the Ciwifruit in between means that it can't form an Appleboom.

    `ABBABBA` is unsafe, as it contains two (overlapping) Stockholm Syndromes.

    `ABBAAAAA` is also unsafe, as it contains *both* a Stockholm and an Appleboom.
    They don't cancel out!

    `CBACBA` is safe.
    It has the same fruit as a Double Rainbow, but the fruit are in the wrong order.

    ## Input

    The input will consist of a single line, containing three integers `0 ≤ A, B, C ≤ 100`.
    These each represent the limits on the number of Apples, Bananas, and Ciwifruits respectively.

    ## Output

    Output a single integer: the number of distinct safe spells that can be cast with the given resources.
  10. lambda-fairy revised this gist Mar 30, 2018. 1 changed file with 1 addition and 1 deletion.
    2 changes: 1 addition & 1 deletion twilight-sparkle-magic-spells.md
    Original file line number Diff line number Diff line change
    @@ -4,7 +4,7 @@ Twilight Sparkle is researching some magic spells.
    A spell is a non-empty finite sequence of **A**pples, **B**ananas, or **C**iwifruit.

    Spells can be **safe** or **unsafe**.
    An unsafe spell contains one of the following patterns:
    An unsafe spell contains one or more of the following patterns:

    | Pattern | Name |
    | --- | --- |
  11. lambda-fairy revised this gist Mar 30, 2018. 1 changed file with 1 addition and 0 deletions.
    1 change: 1 addition & 0 deletions twilight-sparkle-magic-spells.md
    Original file line number Diff line number Diff line change
    @@ -7,6 +7,7 @@ Spells can be **safe** or **unsafe**.
    An unsafe spell contains one of the following patterns:

    | Pattern | Name |
    | --- | --- |
    | `AAAAA` | Appleboom |
    | `ABBA` | Stockholm Syndrome |
    | `ABCABC` | Double Rainbow |
  12. lambda-fairy created this gist Mar 30, 2018.
    74 changes: 74 additions & 0 deletions twilight-sparkle-magic-spells.md
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,74 @@
    # Twilight Sparkle's Magic Spells

    Twilight Sparkle is researching some magic spells.
    A spell is a non-empty finite sequence of **A**pples, **B**ananas, or **C**iwifruit.

    Spells can be **safe** or **unsafe**.
    An unsafe spell contains one of the following patterns:

    | Pattern | Name |
    | `AAAAA` | Appleboom |
    | `ABBA` | Stockholm Syndrome |
    | `ABCABC` | Double Rainbow |

    A safe spell contains none of these patterns.

    Help Twilight determine whether a spell is safe or unsafe.

    ## Examples

    `BAAAAAB` is unsafe, as it contains an Appleboom.

    `AAAACA` is safe.
    While it has five Apples, the Ciwifruit in between means that it can't form an Appleboom.

    `ABBABBA` is unsafe, as it contains two (overlapping) Stockholm Syndromes.

    `ABBAAAAA` is also unsafe, as it contains *both* a Stockholm and an Appleboom.
    They don't cancel out!

    `CBACBA` is safe.
    It has the same fruit as a Double Rainbow, but the fruit are in the wrong order.

    ## Input

    The first line of input will contain a single integer, `0 < N ≤ 100`, representing the length of the spell.

    The next line will contain a string of letters, each either `A`, `B`, or `C`.
    This is the spell itself.

    ## Output

    Output `SAFE` if the spell is safe; otherwise `UNSAFE`.

    ## Samples

    ### Example 1

    Input:

    ```
    1
    A
    ```

    Output:

    ```
    SAFE
    ```

    ### Example 2

    Input:

    ```
    4
    ABBA
    ```

    Output:

    ```
    UNSAFE
    ```