CCC '14 S1 - Party Invitation - DMOJ: Modern Online Judge

CCC '14 S1 - Party Invitation

View as PDF

Submit solution

All submissions

Best submissions

Points: 5 (partial)

Time limit: 2.0s

Memory limit: 256M

Problem type

Canadian Computing Competition: 2014 Stage 1, Junior #4, Senior #1

You are hosting a party and do not have room to invite all of your friends. You use the following unemotional mathematical method to determine which friends to invite.

Number your friends $1, 2, \dots, K$ $1, 2, \dots, K$ and place them in a list in this order. Then perform $m$ $m$ rounds. In each round, use a number to determine which friends to remove from the ordered list.

The rounds will use numbers $r_1, r_2, \dots, r_m$ $r_{1}, r_{2}, \dots, r_{m}$ . In round $i$ $i$ remove all the remaining people in positions that are multiples of $r_i$ $r_{i}$ (that is, $r_i, 2r_i, 3r_i, \dots$ $r_{i}, 2 r_{i}, 3 r_{i}, \dots$ ) The beginning of the list is position $1$ $1$ .

Output the numbers of the friends that remain after this removal process.

Input Specification

The first line of input contains the integer $K$ $K$ $(1 \le K \le 100)$ $(1 \leq K \leq 100)$ . The second line of input contains the integer $m$ $m$ $(1 \le m \le 10)$ $(1 \leq m \leq 10)$ , which is the number of rounds of removal. The next $m$ $m$ lines each contain one integer. The $i^{th}$ $i^{t h}$ of these lines $(1 \le i \le m)$ $(1 \leq i \leq m)$ contains $r_i$ $r_{i}$ $(2 \le r_i \le 100)$ $(2 \leq r_{i} \leq 100)$ indicating that every person at a position which is multiple of $r_i$ $r_{i}$ should be removed.

Output Specification

The output is the integers assigned to friends who were not removed. One integer is printed per line in increasing sorted order.

Sample Input

Copy

Output for Sample Input

Copy

Explanation of Output for Sample Input

Initially, our list of invitees is $1, 2, 3, 4, 5, 6, 7, 8, 9, 10$ $1, 2, 3, 4, 5, 6, 7, 8, 9, 10$ . There will be two rounds of removals. After the first round of removals, we remove the even positions (i.e., every second position), which causes our list of invitees to be $1, 3, 5, 7, 9$ $1, 3, 5, 7, 9$ . After the second round of removals, we remove every 3rd remaining invitee: thus, we keep $1$ $1$ and $3$ $3$ , remove $5$ $5$ and keep $7$ $7$ and $9$ $9$ , which leaves us with an invitee list of $1, 3, 7, 9$ $1, 3, 7, 9$ .

Comments

4

HisMonDon commented on Feb. 19, 2024, 8:04 p.m.

this took me way longer than expected

3

thunder200911133 commented on Jan. 29, 2024, 7:47 a.m.

hardest Junior 4 in a while

3

boomer9367 commented on March 2, 2024, 12:02 a.m.

agreed

3

longcow commented on Feb. 12, 2024, 1:09 a.m.

is this sarcasm or something

2

boomer9367 commented on Feb. 3, 2024, 12:08 a.m. ← edited →

buddy this is senior 1

4

b_nary commented on Feb. 19, 2024, 8:56 p.m. ← edited →

Canadian Computing Competition: 2014 Stage 1, Junior #4, Senior #1

So... actually thunder200911133 isn't wrong. it is both J4 and S1.

-2

kyleandersen commented on Feb. 21, 2024, 12:00 a.m.

holy nerd emoji

2

HisMonDon commented on Feb. 19, 2024, 7:58 p.m. ← edit 2 →

fax