Решение задачи Юные следопыты с Codeforces

С пояснением   Просмотров: 1325

Отряд юных следопытов отправился в учебную экспедицию навстречу своим первым приключениям. И возглавляет их старший следопыт Рассел. Вот герои зашли в лес, разбили лагерь и дальше решили разделиться на группы, чтобы исследовать как можно больше интересных мест. Рассел должен был выбрать состав групп, но столкнулся с одной проблемой...

Код 

#include <bits/stdc++.h>

using namespace std;

int main() {
    int t;
    cin >> t;
    
    while (t--) {
        int n;
        cin >> n;
        vector <int> a(n);
        for (int i = 0; i < n; i++) {
            cin >> a[i];
        }
        sort(a.begin(), a.end());
        int ans = 0, cur = 0;
        for (int i = 0; i < n; i++) {
            if (++cur == a[i]) {
                ans++;
                cur = 0;
            }
        }
        cout << ans << '\n';
    }
    return 0;
}

         

Администратор Photo Автор: Администратор


Пояснение к задаче

Попробуем вычислить последовательность при фиксированном a1=1: 1,2,6,42,50,50,50,…
Нам повезло, и минимальная цифра стала равной 0, после чего элемент перестал изменяться, так как мы прибавляем к нему 0.

На самом деле это не везение, и такое будет происходить всегда. Заметим, что мы каждый раз прибавляем не более 9⋅9=81, поэтому разность между двумя соседними числами в последовательности не превышает 81. Пусть мы никогда не получим минимальную цифру, равную 0. Тогда последовательность будет бесконечно возрастать. Рассмотрим X=1000(⌊
a1
1000

⌋+1). На отрезке [X;X+99] все числа имеют 0 в разряде сотен, поэтому никакой элемент этого отрезка не может быть членом нашей последовательности. Но в нашей последовательности есть числа больше X. Возьмем минимальное из них, оно не меньше X+100. Тогда предыдущее число в последовательности не меньше (X+100)−81=X+19. Оно больше X, но меньше минимального из таких чисел. Противоречие.

На самом деле мы показали, что в последовательности нет чисел больше X+100, а значит мы встретим число с нулевой цифрой среди первых 1001 элементов.

Это значит, что мы можем просто строить последовательность, пока не встретим элемент с нулевой цифрой, после чего этот элемент будет повторяться бесконечно.

В реальности максимальный номер первого элемента с нулевой цифрой — 54, минимальное a1 для такой последовательности равно 28217.


Комментарии

Чтобы написать комментарии вам нужно войти в систему или зарегистрироваться



info@mycod.net   Карта сайта   Правообладателям
Заявка на расчет
×

или напишите нам прямо сейчас:

Написать в MAX
Написать в Telegram
Написать в WhatsApp