Wesley's Anger Contest 2 Problem 6 - Haunted Houses

View as PDF

Submit solution

Points: 30
Time limit: 2.5s
Java 4.5s
Memory limit: 1G

Problem types
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

Halloween has finally arrived and the ghosts on your street have decided to volunteer at your local haunted houses. Each of the N ghosts (numbered from 1 to N) will volunteer at exactly one of the 5 haunted houses and perform their prepared routine. The i^{th} ghost will perform k_i unique moves in their routine, with the k_i moves each being one of 4 types of moves:

  • spook
  • hide
  • creep
  • float

Each move has an associated scare factor, s_{move} for move \in \{spook, hide, creep, float\}.

In addition, the ghosts are separated into groups based on the sum of the digits of their number. All ghosts who have the same sum of digits are in the same group. In order to keep the group happy, at least half of the ghosts in that group must be assigned to the same haunted house.

On Halloween night, each ghost will arrive at their assigned haunted house in the order of their number. They will ask the other ghosts inside the house if any of them are currently planning on performing any of the same moves as them in their routine. To avoid their routines being too similar, all of these ghosts that are currently inside the house (but not outside) will agree to remove that move from their routine.

Once all the ghosts have arrived, the haunted house will open, and the ghosts will perform their routines. Each move a ghost performs contributes the scariness of the haunted house. The scariness of a haunted house is the sum of the scare factors of all moves performed by any ghost inside the house.

You will be asked Q questions. For the i^{th} question, you want to determine the number of ways to assign ghosts to the 5 haunted houses such that each group is happy, and the sum of the scariness of the 5 houses is between a_i and b_i (inclusive). Since this number can be very large, please output it modulo 998244353. It may be helpful to know that 998244353 is prime and 998244353 = 119 \times 2^{23} + 1.


1 \le N \le 80
1 \le Q \le 200\,000
1 \le k_i \le 4 for 1 \le i \le N
1 \le s_{move} \le 10^9 for move \in \{spook, hide, creep, float\}
1 \le a_i \le b_i \le 10^9 for 1 \le i \le Q

Input Specification

The first line of input contains 2 integers, N, Q.

The next N lines of input describe the moves in the i^{th} ghost's routine. Each line begins with an integer k_i, the number of unique moves in the ghosts routine. The next k_i words on the line are the moves the i^{th} ghost will perform in their routine. Each word will be one of spook, hide, creep, or float. Each move will only appear once in a ghost's routine.

The next line of input contains 4 integers, s_{spook}, s_{hide}, s_{creep}, s_{float}

The next Q lines of input describe the questions. Each line contains 2 integers, a_i, b_i.

Output Specification

This problem is graded with an identical checker. This includes whitespace characters. Ensure that every line of output is terminated with a \n character and that there are no trailing spaces.

Output Q lines. On the i^{th} line, output the number of ways, modulo 998244353, to assign ghosts to the 5 haunted houses such that each group is happy, and the sum of the scariness of the 5 houses is between a_i and b_i (inclusive). Two ways are considered different if there is at least one ghost that is assigned to a different house.

Sample Input

3 1
2 spook float
3 creep spook float
2 hide creep
10 5 7 8
19 41

Sample Output


Sample Explanation

There are 20 ways to assign ghosts to houses such that the sum of the scare factors is 19, and 20 ways such that the sum is 41.


There are no comments at the moment.