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

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

26.05.2023, 18:17. Показов 1007. Ответов 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
26.05.2023, 18:17
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  [ТС] 2
Всем спасибо, решил. Необходимо выбирать в качестве ответа шары (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
Ответ Создать тему

Редактор формул (кликните на картинку в правом углу, чтобы закрыть)
Опции темы

Новые блоги и статьи
Контейнер std::map в C++
bytestream 09.02.2025
Контейнер std::map в C++ - один из наиболее мощных инструментов стандартной библиотеки, предназначенный для хранения пар ключ-значение. Каждый элемент в map состоит из уникального ключа и связанного. . .
Как в Python сделать вывод с print без перевода строки и пробела
hw_wired 09.02.2025
Функция print в Python обеспечивает гибкие возможности для вывода информации в консоль. При стандартном использовании эта функция автоматически добавляет символ перевода строки в конце выводимого. . .
Как в Python проверить, что у объекта есть атрибут
hw_wired 09.02.2025
В Python существует несколько встроенных способов проверки наличия атрибутов у объектов. Наиболее распространенным является использование функции hasattr(), которая позволяет безопасно определить. . .
Как удалить экспортированну­ю переменную окружения в Linux
hw_wired 09.02.2025
В Linux работа с переменными окружения - важная часть системного администрирования и разработки. Экспортированные переменные окружения отличаются от обычных локальных переменных тем, что они доступны. . .
Ошибка Error: error:0308010C:­digital envelope routines::unsup­ported
hw_wired 09.02.2025
Ошибка "error:0308010C:digital envelope routines::unsupported" чаще всего появляется при работе с Node. js приложениями и связана с изменениями в системе безопасности криптографических алгоритмов. . . .
В чем отличие между .prop() и .attr()
hw_wired 09.02.2025
В jQuery методы . prop() и . attr() часто вызывают путаницу, поскольку на первый взгляд предназначены для похожих целей. Однако между ними существуют принципиальные различия в работе с DOM-элементами и. . .
В чем отличие SCSS и SASS
hw_wired 09.02.2025
SCSS и SASS появились как решение проблем, связанных с ограничениями обычного CSS при разработке крупных веб-проектов. Традиционный CSS, несмотря на свою простоту, не предоставлял разработчикам. . .
Как найти дубликаты в таблице базы данных
hw_wired 09.02.2025
Дублирование записей в таблицах баз данных может возникать по разным причинам: ошибки при вводе данных, некорректная работа систем импорта, слияние данных из разных источников или неправильная. . .
Как удалить дубликаты из массива в JavaScript
hw_wired 09.02.2025
Самый простой и современный способ удаления дубликатов в JavaScript - использование структуры данных Set в сочетании с Array. from. Set автоматически хранит только уникальные значения, а Array. from. . .
Go Protobuf: новый Opaque API
hw_wired 09.02.2025
Protocol Buffers (protobuf) давно зарекомендовал себя как эффективный формат сериализации данных, широко используемый в микросервисных архитектурах и распределенных системах. Однако существующая. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2025, CyberForum.ru