Аватар для durt
5 / 5 / 0
Регистрация: 30.08.2022
Сообщений: 21

Задача на теорию вероятностей

26.05.2023, 18:17. Показов 1022. Ответов 1
Метки нет (Все метки)

Author24 — интернет-сервис помощи студентам
Здравствуйте, помогите, пожалуйста, с решением задачи "Чёрные и белые".

Рассмотрим игру. В ряд лежат n шариков двух цветов: черные и белые. Позиции в ряду пронумерованы от 1 до n. Вам известно только общее количество шариков (n); точное их расположение и даже количество белых шариков неизвестно.

Вы можете делать запросы вида v u, где 1 ≤ v, u ≤ n. Если на позиции v находится чёрный шарик, а на позиции u — белый, то эти шарики поменяют местами (иначе не произойдёт ничего). При этом вам не сообщают, поменяли шарики местами или нет.
После некоторого (возможно, нулевого) числа таких запросов вы должны сделать «утверждение». «Утверждение» — это тоже две позиции v, u. Вам нужно угадать две такие позиции в ряду, что там лежат шарики одного и того же цвета.

Ваша задача — выдать последовательность запросов, за которой следует ровно одно «утверждение».
В одном тесте может быть много игр. Более того, во всех тестах, кроме первого, ровно 99 игр, причём в первой игре n = 2, во второй игре n = 3 и т. д.. В последней игре n = 100.

Первый тест совпадает с примером из условия. На нём проверяется только формат вывода.
На всех тестах, начиная со второго, чтобы пройти тест, ваша программа должна угадать хотя бы в 80 играх из 99.
Обратите внимание, что, хоть ваша программа и не должна выигрывать все 99 игр, мы не гарантируем, что тесты случайные.

Мой код проходит только до 70 теста
В нём происходит пузырьковая сортировка и в зависимости от рандома мы выбираем ответить, что у нас или 2 белых шара, или 2 чёрных. (это не всегда угадывается, похоже 50/50, а тут надо 80 из 99...)

Ссылка на задачу: https://acm.timus.ru/problem.aspx?space=1&num=2063

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <bits/stdc++.h>
 
using namespace std;
 
int main() {
    mt19937 rnd(time(NULL));
    int n = 2;
    int t; cin >> t;
    while (t--) {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n - i; j++) {
                cout << "? " << j << ' ' << j + 1 << endl;
            }
        }
        if (rnd() % 2) {
            cout << "! " << 1 << ' ' << 2 << endl;
        } else {
            cout << "! " << n - 1 << ' ' << n << endl;
        }
        n++;
    }
}
0
IT_Exp
Эксперт
34794 / 4073 / 2104
Регистрация: 17.06.2006
Сообщений: 32,602
Блог
26.05.2023, 18:17
Ответы с готовыми решениями:

Задача на программирование и теорию вероятностей
Требуется написать фрагмент тела функции, который присваивает переменным a, b и c такие случайные целые значения, которые удовлетворяют...

Задача на теорию графов
Светофорчики В подземелье M тоннелей и N перекрестков, каждый тоннель соединяет какие-то два перекрестка. Мышиный король решил поставить...

Задача на теорию чисел
Торт от Толи Толя на день рождения собирается угостить друзей тортом. Известно, что на дне рождения может быть либо N, либо M человек,...

1
 Аватар для durt
5 / 5 / 0
Регистрация: 30.08.2022
Сообщений: 21
27.05.2023, 10:19  [ТС]
Всем спасибо, решил. Необходимо выбирать в качестве ответа шары (n / 2) и (n / 2 + 1).
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
BasicMan
Эксперт
29316 / 5623 / 2384
Регистрация: 17.02.2009
Сообщений: 30,364
Блог
27.05.2023, 10:19
Помогаю со студенческими работами здесь

Задача на теорию автоматов
Условие во вложение. Не совсем понимаю алгоритм. Есть какие-нибудь идеи?

Задача на теорию вероятностей
в группе 15 свидетелей, 10 из которых не лгут. На удачу было отобрано 5 свидетелей. Найдите вероятность того,что среди выбранных не лгут...

3 задача на теорию вероятностей
Задана функция распределения случайно величины X: 0, x ≤ -a; F(x) = *знак системы* A +...

2 задача на теорию вероятностей
При стрельбе отклонение от цели в среднем равно нулю. Известно, что с вероятностью 0,95 отклонение по модулю не превосходит 5 см. Найти...

Задача на python и теорию вероятностей
У вас есть n монет. Если подбросить j- ю монету с вероятностью p(i) выпадет орел, а с вероятностью (1-p(i)) решка. Проведем эксперимент....


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
2
Ответ Создать тему
Опции темы

Новые блоги и статьи
Вопросы на собеседованиях по микросервисам
ArchitectMsa 27.03.2025
Работодатели ищут не просто разработчиков, знающих базовые концепции, а специалистов, разбирающихся в тонкостях масштабирования, отказоустойчивости и производительности. Сейчас на первый план выходят. . .
Взаимодействие Python с REST API
py-thonny 27.03.2025
REST API - это архитектурный стиль взаимодействия компонентов распределённого приложения в сети. Python располагает функциональным набором инструментов для работы с REST API и основная библиотека для. . .
sshd restrictions, ssh access limitations
jigi33 26.03.2025
sshd restrictions | ssh access limitations рестрикции доступа на сервер sshd статья: https:/ / www. golinuxcloud. com/ restrict-allow-ssh-certain-users-groups-rhel
Компиляция C++ с Clang API
NullReferenced 24.03.2025
Компиляторы обычно воспринимаются как черные ящики, которые превращают исходный код в исполняемые файлы. Мы запускаем компилятор командой в терминале, и вуаля — получаем бинарник. Но что если нужно. . .
Многопоточное программировани­е в C#: Класс Thread
UnmanagedCoder 24.03.2025
Когда запускается приложение на компьютере, операционная система создаёт для него процесс - виртуальное адресное пространство. В C# этот процесс изначально получает один поток выполнения — главный. . .
SwiftUI Data Flow: Передача данных между представлениями
mobDevWorks 23.03.2025
При первом знакомстве со SwiftUI кажется, что фреймворк предлагает избыточное количество механизмов для передачи данных: @State, @Binding, @StateObject, @ObservedObject, @EnvironmentObject и другие. . . .
Моки в Java: Сравниваем Mockito, EasyMock, JMockit
Javaican 23.03.2025
Как протестировать класс, который зависит от других сложных компонентов, таких как базы данных, веб-сервисы или другие классы, с которыми и так непросто работать в тестовом окружении? Для этого и. . .
Архитектурные паттерны микросервисов: ТОП-10 шаблонов
ArchitectMsa 22.03.2025
Популярность микросервисной архитектуры объясняется множеством важных преимуществ. К примеру, она позволяет командам разработчиков работать независимо друг от друга, используя различные технологии и. . .
Оптимизация рендеринга в Unity: Сортировка миллиона спрайтов
GameUnited 22.03.2025
Помните, когда наличие сотни спрайтов в игре приводило к существенному падению производительности? Время таких ограничений уходит в прошлое. Сегодня геймдев сталкивается с задачами совершенно иного. . .
Образование и практика
Igor3D 21.03.2025
Добрый день А вот каково качество/ эффективность ВУЗовского образования? Аналитическая геометрия изучается в первом семестре и считается довольно легким курсом, что вполне справедливо. Ну хорошо,. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2025, CyberForum.ru