COMP 321: Programming Challenges

Assignment 3

This assignment includes two problems, one problem on kattis and one separate.

Please remember that the assignment must be solved individually. What I expect from

you is to upload the following in the “Assignment 3” folder:

1) The codes that you used for solving the problems. The files must be named

Problem_ IDi.extension, where ‘Problem’ is the problem ID, IDi is

your McGill id and ‘extension’ is the program extension (.java).

NOTE: Make sure to add comments to your code.

2) A .pdf file for kattis problems. This .pdf must be named Assignment3_IDi.pdf, where

IDi is your McGill id number. Inside the pdf file, include a screenshot of the acceptance

notification that you received on your Kattis account. Please make sure your name

appears in it.

The due date for this assignment is Sunday October 7th before 11:59 PM.

A. Kattis problem

For this assignment, we will solve the following problem on kattis:

1. All about that base: https://open.kattis.com/problems/allaboutthatbase

B. Separate problem

Problem: Sofas Collection

ProblemID: sofas

Mr. Caron owns a small company, called Gazo, selling home furniture in a French village.

Mr. Caron buys the furniture from a bigger company, called Mazo, and sells it at slightly

higher costs to make a profit. Today, he found a good deal at Mazo on nice sofas. These

sofas are each characterized by a style and a color. There are 36 different styles and 36

different colors. In total, there are 1296 different sofas. However, today, not all these sofas

are available at Mazo.

To satisfy customers and still take advantage of the deal, Mr. Caron decided to get from

Mazo today all combinations of 𝑘 styles and 𝑘 colors, for a 𝑘 value that is as large as

possible. However, he has discovered that determining this 𝑘 for a given collection is not

always trivial. Can you help him?

Input

On the first line of the input, there is a single positive integer 𝑛, telling the number of test

scenarios to follow. Each test scenario begins with a line containing a single positive

integer 𝑚 ≤ 100, the number of sofas available at Mazo. Then follow 𝑚 lines, one per

sofa, each with a pair of numbers, 𝑠𝑖 and 𝑐𝑖

, separated by a single space,

where 𝑠𝑖

(0<𝑠𝑖≤36) indicates the style of the 𝑖th sofa, and 𝑐𝑖

(0<𝑐𝑖≤36) indicates its color.

Output

For each test scenario, output one line containing the maximum 𝑘, such that there

are 𝑘 styles and 𝑘 colors for which Mr. Caron’s sofas collection contain all 𝑘 ⋅

𝑘 combinations of those styles and colors.

Sample Input 1

2

5

11 13

23 5

17 36

11 5

23 13

2

23 15

15 23

Sample Output 1

2

1

Sale!