logoChat01.ai

Разработайте систему стимулирования чтения электро...

تم الإنشاء في: ٣١ أكتوبر ٢٠٢٥

تمت الإجابة باستخدام GPT-5 Thinking بواسطة Chat01

سؤال

Разработайте систему стимулирования чтения электронных книг. Для простоты будем считать, что книга всего одна, но её одновременно читают много людей. Нужно следить за прогрессом чтения у всех пользователей и выводить мотивирующие уведомления. А именно, программа должна обрабатывать следующие события:
READ user page — сохранить факт того, что пользователь под номером user дочитал книгу до страницы page. Если ранее такой пользователь не встречался, нужно его добавить. Гарантируется, что в рамках одного пользователя номера страниц в соответствующих ему событиях возрастают.
CHEER user — сообщить пользователю user, какая доля существующих пользователей, не считая его самого, прочитала меньшую часть книги, чем он. Если этот пользователь на данный момент единственный, доля считается равной 1. Если для данного пользователя пока не было ни одного события READ, доля считается равной 0, а сам пользователь не учитывается при вычислении долей для других пользователей до тех пор, пока для него не случится событие READ.
Формат входных данных
В первой строке вводится количество запросов Q — натуральное число, не превосходящее 10⁶. В следующих Q строках в соответствии с описанным выше форматом вводятся запросы. Гарантируется, что все вводимые числа целые и положительные, при этом номера пользователей не превосходят 10⁵, а номера страниц не превосходят 1000.
Пример ввода:
12
CHEER 5
READ 1 10
CHEER 1
READ 2 5
READ 3 7
CHEER 2
CHEER 3
READ 3 10
CHEER 3
READ 3 11
CHEER 3
CHEER 1
Формат выходных данных
Для каждого запроса CHEER user выведите единственное вещественное число от 0 до 1 — долю пользователей, прочитавших меньше страниц, чем user. Для вывода числа на экран используйте setprecision(6).
Пример вывода, соответствующий примеру ввода:
0
1
0
0.5
0.5
1
0.5
Пользователь 5 не учитывается при вычислении долей, потому что для него не произошло ни одного события READ. Пользователь 1 изначально был единственным, но в конце его обогнал третий, но не обогнал второй, поэтому он оказался продуктивнее 50% пользователей. Пользователь 3 изначально обгонял только второго и потому получал долю 50%, но в конце обогнал первого и получил долю 100%.
Ограничения
Четыре секунды на выполнение всех запросов. Все описанные в условии гарантии действительно справедливы для всех тестов, на которых будет запускаться ваша программа. Проверять корректность ввода не нужно. Гарантируется, что все вводимые числа целые и положительные. При этом номера пользователей не превосходят 10⁵, а номера страниц не превосходят 1000. Общее количество запросов не превосходит 10⁶. Храните два вектора. В первом по индексу n будет храниться номер страницы, до которой дочитал пользователь id, равным n. Во втором по каждому индексу m будет храниться количество пользователей, дочитавших как минимум до страницы m.

الفكرة

Designing a solution

I need to create an algorithm (likely in C++) to track user progress with two arrays: user_progress[id] and page_achievers[page]. I must make sure to count the number of users who have read at least a certain number of pages, while considering performance with possible edge cases. I'll increment counts across pages as we process reads, ensuring the solution handles input sizes up to 1e6 efficiently.

Optimizing with a Fenwick tree

The user-specific pages are increasing, so each user can increment their total at most Pmax (<=1000) times. With 1e5 users, that could mean up to 1e8 operations, which is a bit heavy but probably manageable in C++ in under 4 seconds. A more efficient approach would be to use a Fenwick tree for prefix sum updates, optimizing the range updates.

Understanding second vector and CHEER

The second vector tracks the number of users who have read at least up to page "m". When a user reads a new page, I need to update the counts for all pages between their old and new progress. For the CHEER query, if the user hasn’t read anything, output 0; otherwise, count how many active readers have read fewer pages than the user's progress. This is derived from the counts_by_page array.

Calculating ratio and precision handling

The count[p] tracks users with pages ≥ p, while N_active equals count[1]. The other_count is calculated as N_active - count[p], and the desired ratio is the result of other_count / (N_active - 1). To deal with precision, I’ll output with six decimal places using setprecision(6). I’ll double-check sample outputs to ensure format aligns.

Implementing C++ solution

The approach involves managing two vectors: one for tracking the last read page per user and another for managing the count of readers at each page level. For "READ," we update the counts from the previous page to the new one. For "CHEER," we calculate the ratio of active readers with fewer pages completed than the user's current progress. We’ll output with precision set to 6 digits using setprecision(6). Fast I/O will be enabled to handle up to 1e6 entries efficiently.

Thought for 41s

الإجابة

Ниже — простое и очень быстрое решение с двумя массивами, как просят в условии.

Идея

  • last_page[id] — до какой страницы дочитал пользователь id (0, если ещё не читал).
  • ge[m] — сколько пользователей дочитали как минимум до страницы m.
  • Обработка READ u p: пусть раньше было old = last_page[u]. Тогда для всех m от old+1 до p увеличиваем ge[m] на 1 и записываем last_page[u] = p.
    Так как по каждому пользователю страницы только растут, суммарно таких инкрементов за всю работу не больше (#пользователей) * 1000, что укладывается в лимиты.
  • Обработка CHEER u:
    • если last_page[u] == 0 → ответ 0;
    • иначе, пусть активных читателей active = ge[1].
      Если active == 1 → ответ 1;
      иначе у пользователя страница p = last_page[u], тогда
      пользователей, прочитавших меньше, чем u: less = active - ge[p],
      доля: less / (active - 1).

Сложность

  • READ: амортизированно O(Δp) с суммой Δp ≤ 1000 на пользователя → суммарно ≤ 1e8 простых инкрементов.
  • CHEER: O(1).
  • Память: O(10^5 + 1000).

Реализация (C++17)

cpp
#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    const int MAX_USER = 100000;
    const int MAX_PAGE = 1000;

    int Q;
    if (!(cin >> Q)) return 0;

    vector<int> last_page(MAX_USER + 1, 0);     // last_page[id]
    vector<int> ge(MAX_PAGE + 2, 0);            // ge[m] = count(read >= m)

    cout << setprecision(6); // как в условии (без fixed — как в примере)

    for (int qi = 0; qi < Q; ++qi) {
        string cmd;
        cin >> cmd;
        if (cmd == "READ") {
            int u, p;
            cin >> u >> p;
            int old = last_page[u];
            if (p > old) {
                // теперь этот пользователь считается дочитавшим до всех m в [old+1, p]
                for (int m = old + 1; m <= p; ++m) {
                    ++ge[m];
                }
                last_page[u] = p;
            }
        } else if (cmd == "CHEER") {
            int u;
            cin >> u;

            if (last_page[u] == 0) {
                cout << 0 << '\n';               // ещё не читал
                continue;
            }

            int active = ge[1];                  // все, кто прочитал >= 1 страницы
            if (active == 1) {
                cout << 1 << '\n';               // единственный активный читатель
                continue;
            }

            int p = last_page[u];
            int less = active - ge[p];           // у кого строго меньше страниц
            double ans = static_cast<double>(less) / static_cast<double>(active - 1);
            cout << ans << '\n';
        }
    }
    return 0;
}

Эта программа полностью соответствует требованию «хранить два вектора» и проходит по времени при заданных ограничениях.

مشاركة هذا السؤال والجواب