Book Recommender

You are given a dataset of book ratings by different users. Each record contains a user ID, a book ID, and a rating (an integer from 1 to 5). Your task is to build a simple book recommendation system based on collaborative filtering using cosine distance.

In this problem, you will construct a user-item rating matrix. The cosine distance between two users (u) and (v) is defined as [ d(u,v) = 1 - \frac{u \cdot v}{|u|,|v|} ] where (u \cdot v) is the dot product and (|u|) denotes the Euclidean norm of (u).

For a prediction query, given a user (u) and a book (b), find the top 5 users (neighbors) who have rated book (b) with the smallest cosine distances and predict the rating using a weighted average: [ \hat{r}{u,b} = \frac{\sum{v \in N(u)} d(u,v), r_{v,b}}{\sum_{v \in N(u)} d(u,v)} ] If no prediction can be made (for example, if the user or book does not exist or if there are no neighbors who rated the book), output None.

For a recommendation query, for a given user, recommend the top (n) books (books the user has not rated) with the highest predicted ratings (using the same prediction method as above). If no recommendations can be made, output None.

Both types of queries are handled via standard input/output as described below.

inputFormat

The input begins with an integer (n) denoting the number of rating records. The next (n) lines each contain three values: user_id, book_id, and rating (an integer).

After this, there is an integer (q) representing the number of queries. Each of the following (q) lines represents a query in one of the following formats:

• Prediction query: P user_id book_id • Recommendation query: R user_id n

All input is provided via standard input (stdin).

outputFormat

For each query, output the result on a new line via standard output (stdout). For a prediction query, print the predicted rating rounded to two decimal places or None if a prediction is not possible. For a recommendation query, print the recommended book IDs separated by a space; if no recommendation is possible, print None.## sample

6
1 101 5
2 102 4
3 103 3
4 101 5
5 102 4
6 103 2
3
P 1 102
R 1 2
P 10 101

4.00
102 103
None