Задачка про жюри

@Alibaba343 · Регистрация: 09.09.2023

Студворк — интернет-сервис помощи студентам

Всего в жюри n судей, для каждого судьи определён авторитет ai. Когда в жюри приносят дискету с очередным решением, каждый член жюри читает исходный код и голосует “OK”, если он считает, что решение верно, и “WA”, если он считает, что решение неверно. Если после того, как все члены жюри проголосовали, сумма авторитетов судей, считающих, что решение верно, больше или равна p, решение получает вердикт “Accepted”, иначе оно получает вердикт “Rejected”.

Некоторые члены жюри считают, что система оценки слишком сложна для них, так что они предложили присвоить судьям более «красивые» значения авторитетов bi и изменить лимит на q. По их мнению, система оценок останется эквивалентной, а считать баллы будет проще.

Министерство образования Берляндской области поручило Вам проверить, действительно ли новая и старая системы эквивалентны, то есть верно ли, что для каждого возможного распределения голосов итоговый вердикт не поменяется. Если системы не эквивалентны, приведите пример распределения голосов, который приводит к разным вердиктам в новой и старой системах.

Формат входных данных
В первой строке дано число n (1≤n≤100).

Во второй строке даны числа p ,a1, a2,⋯, an(1≤p, ai≤10^6).

В третьей строке даны числа q,b1,b2,⋯,b (1≤q, bi≤10^6).

Формат результата
Выведите «YES», если замена возможна. Иначе в первой строке выведите «NO», а во второй — описание контрпримера в виде битовой строки длины
n. i-ый бит этой строки должен быть равен 1, если i-ый судья считает, что решение верно, и 0, если он считает, что решение неверно.

Если контрпримеров несколько, выведите любой из них.

Примеры
Входные данные
3
8 4 5 6
2 1 1 1
Результат работы
YES
Входные данные
3
6 4 5 6
2 1 1 1
Результат работы
NO
001

@igorrr37 · 09.09.2023, 15:48

перебором и долго
Ввод переделай

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
#include <vector>
#include <algorithm>
#include <iostream>
#include <random>
#include <ctime>
#include <numeric>
#include <functional>
#include <ranges>
namespace rng = std::ranges;
 
std::vector<int> va, vb, vres;
int n, p, q, sa, sb, icur, nmin;
 
void f(int cnt)
{
    if (cnt == n)
    {
 
    }
    else
    {
        for (int i = icur; i < n && i <= n - nmin + cnt; ++i)
        {
            sa += va[i];
            sb += vb[i];
            vres.push_back(i);
            if ((sa >= p && sb < q) || (sa < p && sb >= q))
            {
                throw 1;
            }
            if (sa < p) // ограничение сверху
            {
                icur = i + 1;
                f(cnt + 1);
            }
            vres.pop_back();
            sa -= va[i];
            sb -= vb[i];
        }
    }
}
 
int main()
{
    p = 3, q = 3; // ввод p, q, n
 
    va = { 1,1,1,3,3 }; // ввод вектора a
    vb = { 1,3,1,3,1 }; // ввод вектора b
 
    // /* убрать
    n = va.size();
    n = 100;
    va.resize(n);
    vb.resize(n);
    std::mt19937 eng{ (unsigned)time(nullptr) };
    std::uniform_int_distribution uid{ 1, 1 };
    std::generate_n(va.begin(), n, [&]() { return uid(eng); });
    std::generate_n(vb.begin(), n, [&]() { return uid(eng); });
    // */
 
    std::cout << p << "\n";
    rng::copy(va, std::ostream_iterator<int>{std::cout, " "});
    std::cout << "\n\n" << q << "\n";
    rng::copy(vb, std::ostream_iterator<int>{std::cout, " "});
    std::cout << "\n\n";
 
    auto vaa = va, vbb = vb;
    rng::sort(vaa, std::greater{});
    rng::sort(vbb, std::greater{});
    int saa{}, sbb{};
    nmin = va.size() + 1; // ограничение снизу
    for (int i = 0; i < vaa.size(); ++i)
    {
        saa += vaa[i];
        sbb += vbb[i];
        if (saa >= p || sbb >= q)
        {
            nmin = i + 1;
            break;
        }
    }
 
    try { f(0); }
    catch (...) {}
    // если vres не пуст то NO (контрпример находится в векторе vres)
    rng::copy(vres, std::ostream_iterator<int>{ std::cout, " " });
    std::cout << "\n";
}

@Alibaba343 · 10.09.2023, 10:25 **[ТС]**

Спасибо большое за решение! Программа почти все тесты прошла. Алгоритм быстрый, но, кажется, на последнем тесте в бесконечную рекурсию свалился. По времени не прошло

@igorrr37 · 10.09.2023, 12:37

Сообщение от Alibaba343

Алгоритм быстрый

он не быстрый, но на некоторых входных данных может работать быстро за счёт отсечений

Сообщение от Alibaba343

последнем тесте в бесконечную рекурсию свалился

да. Например при: n=100, p=q=50, ai=bi=1 будет бесконечная рекурсия. Можно попробовать отсекать подобные случаи

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
#include <vector>
#include <algorithm>
#include <iostream>
#include <random>
#include <ctime>
#include <numeric>
#include <functional>
#include <ranges>
#include <cmath>
namespace rng = std::ranges;
 
std::vector<int> va, vb, vres;
int n, p, q, sa, sb, icur, nmin;
 
void f(int cnt)
{
    for (int i = icur; i < n && i <= n - nmin + cnt; ++i)
    {
        sa += va[i];
        sb += vb[i];
        vres.push_back(i);
        if ((sa >= p && sb < q) || (sa < p && sb >= q))
        {
            throw 1;
        }
        if (sa < p) // отсечение сверху
        {
            icur = i + 1;
            f(cnt + 1);
        }
        vres.pop_back();
        sa -= va[i];
        sb -= vb[i];
    }
}
 
int main()
{
    p = 30, q = 30; // ввод p, q, n
 
    va = { 1,1,1,3,3 }; // ввод вектора a
    vb = { 1,3,1,3,1 }; // ввод вектора b
 
    // /* убрать
    n = va.size();
    n = 100;
    va.resize(n);
    vb.resize(n);
    std::mt19937 eng{ (unsigned)time(nullptr) };
    std::uniform_int_distribution uida{ 1, 1 };
    std::generate_n(va.begin(), n, [&]() { return uida(eng); });
    std::uniform_int_distribution uidb{ 1, 1 };
    std::generate_n(vb.begin(), n, [&]() { return uidb(eng); });
    // */
 
    std::cout << p << "\n";
    rng::copy(va, std::ostream_iterator<int>{std::cout, " "});
    std::cout << "\n\n" << q << "\n";
    rng::copy(vb, std::ostream_iterator<int>{std::cout, " "});
    std::cout << "\n\n";
 
    auto vaa = va, vbb = vb;
    rng::sort(vaa, std::greater{});
    rng::sort(vbb, std::greater{});
    int saa{}, sbb{};
    nmin = va.size() + 1; // отсечение снизу
    for (int i = 0; i < vaa.size(); ++i)
    {
        saa += vaa[i];
        sbb += vbb[i];
        if (saa >= p || sbb >= q)
        {
            nmin = i + 1;
            break;
        }
    }
    // отсечение по эквивалентности
    double qt = (double)q / vb[0];
    int qtl = std::floor(qt), qtg = std::ceil(qt);
    bool bEcv = qtl < qtg ? va[0] * qtl < p && va[0] * qtg >= p : va[0] * qtg >= p;
    bEcv = bEcv
        && rng::all_of(va, [](int val) { return val == va[0]; }) 
        && rng::all_of(vb, [](int val) { return val == vb[0]; });
    if (!bEcv)
    {
        try { f(0); }
        catch (...) {}
    }
    // если vres не пуст то NO (контрпример находится в векторе vres)
    rng::copy(vres, std::ostream_iterator<int>{ std::cout, " " });
    std::cout << "\n";
}

@Alibaba343 · 10.09.2023, 18:12 **[ТС]**

Все равно бесконечная рекурсия

Новые блоги и статьи Все статьи Все блоги /
Знаешь почему 90% людей редко бывают счастливыми? kumehtar 14.04.2026 Потому что они ждут. Ждут выходных, ждут отпуска, ждут удачного момента. . . а удачный момент так и не приходит.	Фиксация колонок в отчете СКД Maks 14.04.2026 Фиксация колонок в СКД отчета типа Таблица. Задача: зафиксировать три левых колонки в отчете. Процедура ПриКомпоновкеРезультата(ДокументРезультат, ДанныеРасшифровки, СтандартнаяОбработка) / / . . .	Настройки VS Code Loafer 13.04.2026 { "cmake. configureOnOpen": false, "diffEditor. ignoreTrimWhitespace": true, "editor. guides. bracketPairs": "active", "extensions. ignoreRecommendations": true, . . .	Оптимизация кода на разграничение прав доступа к элементам формы Maks 13.04.2026 Алгоритм из решения ниже реализован на нетиповом документе, разработанного в конфигурации КА2. Задачи, как таковой, поставлено не было, проделанное ниже исключительно моя инициатива. Было так:. . .
Контроль заполнения и очистка дат в зависимости от значения перечислений Maks 12.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "ПланированиеПерсонала", разработанного в конфигурации КА2. Задача: реализовать контроль корректности заполнения дат назначения. . .	Архитектура слоя интернета для сервера-слоя. Hrethgir 11.04.2026 В продолжение https:/ / www. cyberforum. ru/ blogs/ 223907/ 10860. html Знаешь что я подумал? Раз мы все источники пишем в голове ветки, то ничего не мешает добавить в голову такой источник, который сам. . .	Подстановка значения реквизита справочника в табличную часть документа Maks 10.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "ПланированиеПерсонала", разработанного в конфигурации КА2. Задача: при выборе сотрудника (справочник Сотрудники) в ТЧ документа. . .	Очистка реквизитов документа при копировании Maks 09.04.2026 Алгоритм из решения ниже применим как для типовых, так и для нетиповых документов на самых различных конфигурациях. Задача: при копировании документа очищать определенные реквизиты и табличную. . .

@Alibaba343 0 / 0 / 0 Регистрация: 09.09.2023 Сообщений: 3

	Задачка про жюри 09.09.2023, 10:20. Показов 1286. Ответов 4 Метки олимпиадная задача, олимпиадное программирование (Все метки) Всего в жюри n судей, для каждого судьи определён авторитет ai. Когда в жюри приносят дискету с очередным решением, каждый член жюри читает исходный код и голосует “OK”, если он считает, что решение верно, и “WA”, если он считает, что решение неверно. Если после того, как все члены жюри проголосовали, сумма авторитетов судей, считающих, что решение верно, больше или равна p, решение получает вердикт “Accepted”, иначе оно получает вердикт “Rejected”. Некоторые члены жюри считают, что система оценки слишком сложна для них, так что они предложили присвоить судьям более «красивые» значения авторитетов bi и изменить лимит на q. По их мнению, система оценок останется эквивалентной, а считать баллы будет проще. Министерство образования Берляндской области поручило Вам проверить, действительно ли новая и старая системы эквивалентны, то есть верно ли, что для каждого возможного распределения голосов итоговый вердикт не поменяется. Если системы не эквивалентны, приведите пример распределения голосов, который приводит к разным вердиктам в новой и старой системах. Формат входных данных В первой строке дано число n (1≤n≤100). Во второй строке даны числа p ,a1, a2,⋯, an(1≤p, ai≤10^6). В третьей строке даны числа q,b1,b2,⋯,b (1≤q, bi≤10^6). Формат результата Выведите «YES», если замена возможна. Иначе в первой строке выведите «NO», а во второй — описание контрпримера в виде битовой строки длины n. i-ый бит этой строки должен быть равен 1, если i-ый судья считает, что решение верно, и 0, если он считает, что решение неверно. Если контрпримеров несколько, выведите любой из них. Примеры Входные данные 3 8 4 5 6 2 1 1 1 Результат работы YES Входные данные 3 6 4 5 6 2 1 1 1 Результат работы NO 001 0

@Alibaba343 0 / 0 / 0 Регистрация: 09.09.2023 Сообщений: 3
	10.09.2023, 10:25 [ТС]
	Спасибо большое за решение! Программа почти все тесты прошла. Алгоритм быстрый, но, кажется, на последнем тесте в бесконечную рекурсию свалился. По времени не прошло 0

@Alibaba343 0 / 0 / 0 Регистрация: 09.09.2023 Сообщений: 3
	10.09.2023, 18:12 [ТС]
	Все равно бесконечная рекурсия 0