Giao lưu


Submit solution

Points: 400
Time limit: 1.0s
Memory limit: 1G

Authors:
Problem type

Vietnamese Statement: Giao lưu
English Statement ( below ): Socialise

Đợt tập huấn 3H có \(N\) bạn học sinh tham gia. Bạn thứ \(i\) được đánh giá khả năng là số nguyên dương \(a_i\). Tại buổi học thứ \(x\), mỗi bạn tự tính cho mình một chỉ số khả năng là \(\lfloor \frac{a_i}{x} \rfloor\) và các bạn có cùng chỉ số khả năng sẽ ngồi với nhau tạo thành một nhóm trao đổi và giao lưu.

Yêu cầu: với mỗi giá trị \(g = 1, 2, \dots N\), hãy xác định xem buổi học sớm nhất xuất hiện nhóm có \(g\) học sinh. (Ghi ra \(-1\) nếu không tồn tại)

Dữ liệu vào:

  • Dòng đầu chứa số nguyên dương \(N\)
  • Dòng tiếp theo chứa \(N\) só nguyên không âm \(a_1, a_2, \dots, a_n\)

Dữ liệu ra:

  • Xuất ra \(n\) dòng, dòng thứ \(i\) là buổi học sớm nhất để có \(g\) học sinh. Hoặc in ra \(-1\) nếu không tồn tại

Giới hạn:

  • Subtaks 1: \(n \leq 100\) and \(a_i \leq 2.10^5\)
  • Subtaks 2: \(n \leq 300\) and \(a_i \leq 3.10^6\)
  • Subtaks 3: \(n \leq 300\) and \(a_i \leq 5.10^7\)

Input 1:

3
1 2 5

Output 1:

1
3
6
Giải thích
Ngày 1: \(x[d] = \) { \( \lfloor \frac{1}{1} \rfloor, \lfloor \frac{2}{1} \rfloor, \lfloor \frac{5}{1} \rfloor\) } \(=\) { \(1, 2, 5\) } — Nhóm đầu tiên có giá trị 1: Một trong các nhóm {\(1\)} {\(2\)} {\(5\)}
Ngày 2: \(x[d] = \) { \( \lfloor \frac{1}{2} \rfloor, \lfloor \frac{2}{2} \rfloor, \lfloor \frac{5}{2} \rfloor\) } \(=\) { \(0, 1, 2\) }
Ngày 3: \(x[d] = \) { \( \lfloor \frac{1}{3} \rfloor, \lfloor \frac{2}{3} \rfloor, \lfloor \frac{5}{3} \rfloor\) } \(=\) { \(0, 0, 1\) } — Nhóm đầu tiên có giá trị 2: Chỉ có nhóm {\(1, 2\)}
Ngày 4: \(x[d] = \) { \( \lfloor \frac{1}{4} \rfloor, \lfloor \frac{2}{4} \rfloor, \lfloor \frac{5}{4} \rfloor\) } \(=\) { \(0, 0, 1\) }
Ngày 5: \(x[d] = \) { \( \lfloor \frac{1}{5} \rfloor, \lfloor \frac{2}{5} \rfloor, \lfloor \frac{5}{5} \rfloor\) } \(=\) { \(0, 0, 1\) }
Ngày 6: \(x[d] = \) { \( \lfloor \frac{1}{6} \rfloor, \lfloor \frac{2}{6} \rfloor, \lfloor \frac{5}{6} \rfloor\) } \(=\) { \(0, 0, 0\) } — Nhóm đầu tiên có giá trị 3: Chỉ có nhóm {\(1, 2, 5\)}

Input 2:

3
1 1 5

Output 2:

1
1
6
Giải thích
Ngày 1: \(x[d] = \) { \( \lfloor \frac{1}{1} \rfloor, \lfloor \frac{1}{1} \rfloor, \lfloor \frac{5}{1} \rfloor\) } \(=\) { \(1, 1, 5\) } — Nhóm đầu tiên có giá trị 1: Một trong các nhóm {\(1\)} {\(1\)} {\(5\)}
Ngày 2: \(x[d] = \) { \( \lfloor \frac{1}{2} \rfloor, \lfloor \frac{1}{2} \rfloor, \lfloor \frac{5}{2} \rfloor\) } \(=\) { \(0, 0, 2\) } — Nhóm đầu tiên có giá trị 2: Chỉ có nhóm {\(1, 1\)}
Ngày 3: \(x[d] = \) { \( \lfloor \frac{1}{3} \rfloor, \lfloor \frac{1}{3} \rfloor, \lfloor \frac{5}{3} \rfloor\) } \(=\) { \(0, 0, 1\) }
Ngày 4: \(x[d] = \) { \( \lfloor \frac{1}{4} \rfloor, \lfloor \frac{1}{4} \rfloor, \lfloor \frac{5}{4} \rfloor\) } \(=\) { \(0, 0, 1\) }
Ngày 5: \(x[d] = \) { \( \lfloor \frac{1}{5} \rfloor, \lfloor \frac{1}{5} \rfloor, \lfloor \frac{5}{5} \rfloor\) } \(=\) { \(0, 0, 1\) }
Ngày 6: \(x[d] = \) { \( \lfloor \frac{1}{6} \rfloor, \lfloor \frac{1}{6} \rfloor, \lfloor \frac{5}{6} \rfloor\) } \(=\) { \(0, 0, 0\) } — Nhóm đầu tiên có giá trị 3: Chỉ có nhóm {\(1, 2, 5\)}

Input 3:

3
2 2 2

Output 3:

-1
-1
2
Giải thích
Ngày 1: \(x[d] = \) { \( \lfloor \frac{2}{1} \rfloor, \lfloor \frac{2}{1} \rfloor, \lfloor \frac{2}{1} \rfloor\) } \(=\) { \(2, 2, 2\) } — Nhóm đầu tiên có giá trị 3: Chỉ có nhóm {\(2, 2, 2\)}
Ngày 2: \(x[d] = \) { \( \lfloor \frac{2}{2} \rfloor, \lfloor \frac{2}{2} \rfloor, \lfloor \frac{2}{2} \rfloor\) } \(=\) { \(0, 0, 0\) }
Ngày 3: \(x[d] = \) { \( \lfloor \frac{2}{3} \rfloor, \lfloor \frac{2}{3} \rfloor, \lfloor \frac{2}{3} \rfloor\) } \(=\) { \(0, 0, 0\) }
Ngày 3 \(\leq k \rightarrow \infty\): \(x[d] = \) { \( \lfloor \frac{2}{k} \rfloor, \lfloor \frac{2}{k} \rfloor, \lfloor \frac{2}{k} \rfloor\) } \(=\) { \(0, 0, 0\) } — Không có nhóm có giá trị 1 hay 2



















Vietnamese Statement ( Ở trên ): Giao lưu
English Statement: Socialise

There are \(N\) buildings with \(a_1, a_2, \dots, a_n\) metters height. These days are hard, the heavy raining weather still not ended yet. In day \(d\), every building with height \(h\) only have \(x_d = \lfloor \frac{h}{d} \rfloor\) height left of good space to use, while others are sunk underwater. Every building having the same value \(x_d\) on day \(d\) will group together (including \(x_d = 0\) which sunk completely underwater) in a way that no other building with same value \(x_d\) in another group.

Queries: In each size \(s\) from \(1\) to \(n\), what is the earliest day \(d\) that have at least one group of size \(s\)

Input:

  • First line with positive integer \(N\)
  • Second line with \(N\) non-negative height \(a_1, a_2, \dots, a_n\)

Output:

  • Output \(n\) lines, the line \(s-th\) should consist the earliest day that have a group of size \(s\). If there is no such group exists then output \(-1\).

Constraint:

  • Subtaks 1: \(n \leq 100\) and \(a_i \leq 2.10^5\)
  • Subtaks 2: \(n \leq 300\) and \(a_i \leq 3.10^6\)
  • Subtaks 3: \(n \leq 300\) and \(a_i \leq 5.10^7\)

Input 1:

3
1 2 5

Output 1:

1
3
6
Explanation
Day 1: \(x[d] = \) { \( \lfloor \frac{1}{1} \rfloor, \lfloor \frac{2}{1} \rfloor, \lfloor \frac{5}{1} \rfloor\) } \(=\) { \(1, 2, 5\) } — First group of size 1: Any of {\(1\)} {\(2\)} {\(5\)}
Day 2: \(x[d] = \) { \( \lfloor \frac{1}{2} \rfloor, \lfloor \frac{2}{2} \rfloor, \lfloor \frac{5}{2} \rfloor\) } \(=\) { \(0, 1, 2\) }
Day 3: \(x[d] = \) { \( \lfloor \frac{1}{3} \rfloor, \lfloor \frac{2}{3} \rfloor, \lfloor \frac{5}{3} \rfloor\) } \(=\) { \(0, 0, 1\) } — First group of size 2: Only {\(1, 2\)}
Day 4: \(x[d] = \) { \( \lfloor \frac{1}{4} \rfloor, \lfloor \frac{2}{4} \rfloor, \lfloor \frac{5}{4} \rfloor\) } \(=\) { \(0, 0, 1\) }
Day 5: \(x[d] = \) { \( \lfloor \frac{1}{5} \rfloor, \lfloor \frac{2}{5} \rfloor, \lfloor \frac{5}{5} \rfloor\) } \(=\) { \(0, 0, 1\) }
Day 6: \(x[d] = \) { \( \lfloor \frac{1}{6} \rfloor, \lfloor \frac{2}{6} \rfloor, \lfloor \frac{5}{6} \rfloor\) } \(=\) { \(0, 0, 0\) } — First group of size 3: Only {\(1, 2, 5\)}

Input 2:

3
1 1 5

Output 2:

1
1
6
Explanation
Day 1: \(x[d] = \) { \( \lfloor \frac{1}{1} \rfloor, \lfloor \frac{1}{1} \rfloor, \lfloor \frac{5}{1} \rfloor\) } \(=\) { \(1, 1, 5\) } — First group of size 1: Any of {\(1\)} {\(1\)} {\(5\)}
Day 2: \(x[d] = \) { \( \lfloor \frac{1}{2} \rfloor, \lfloor \frac{1}{2} \rfloor, \lfloor \frac{5}{2} \rfloor\) } \(=\) { \(0, 0, 2\) } — First group of size 2: Only {\(1, 1\)}
Day 3: \(x[d] = \) { \( \lfloor \frac{1}{3} \rfloor, \lfloor \frac{1}{3} \rfloor, \lfloor \frac{5}{3} \rfloor\) } \(=\) { \(0, 0, 1\) }
Day 4: \(x[d] = \) { \( \lfloor \frac{1}{4} \rfloor, \lfloor \frac{1}{4} \rfloor, \lfloor \frac{5}{4} \rfloor\) } \(=\) { \(0, 0, 1\) }
Day 5: \(x[d] = \) { \( \lfloor \frac{1}{5} \rfloor, \lfloor \frac{1}{5} \rfloor, \lfloor \frac{5}{5} \rfloor\) } \(=\) { \(0, 0, 1\) }
Day 6: \(x[d] = \) { \( \lfloor \frac{1}{6} \rfloor, \lfloor \frac{1}{6} \rfloor, \lfloor \frac{5}{6} \rfloor\) } \(=\) { \(0, 0, 0\) } — First group of size 3: Only {\(1, 2, 5\)}

Input 3:

3
2 2 2

Output 3:

-1
-1
2
Explanation
Day 1: \(x[d] = \) { \( \lfloor \frac{2}{1} \rfloor, \lfloor \frac{2}{1} \rfloor, \lfloor \frac{2}{1} \rfloor\) } \(=\) { \(2, 2, 2\) } — First group of size 3: Only {\(2, 2, 2\)}
Day 2: \(x[d] = \) { \( \lfloor \frac{2}{2} \rfloor, \lfloor \frac{2}{2} \rfloor, \lfloor \frac{2}{2} \rfloor\) } \(=\) { \(0, 0, 0\) }
Day 3: \(x[d] = \) { \( \lfloor \frac{2}{3} \rfloor, \lfloor \frac{2}{3} \rfloor, \lfloor \frac{2}{3} \rfloor\) } \(=\) { \(0, 0, 0\) }
Day 3 \(\leq k \rightarrow \infty\): \(x[d] = \) { \( \lfloor \frac{2}{k} \rfloor, \lfloor \frac{2}{k} \rfloor, \lfloor \frac{2}{k} \rfloor\) } \(=\) { \(0, 0, 0\) } — There are no group of size 1 and 2

Comments

There are no comments at the moment.