Question

Написать программу на С++ Август и Беатриса играют в игру. Август загадал натуральное число от 1 до n. Беатриса пытается угадать это число, для этого она называет некоторые множества натуральных чисел. Август отвечает Беатрисе YES, если среди названных ей чисел есть задуманное или NO в противном случае. После нескольких заданных вопросов Беатриса запуталась в том, какие вопросы она задавала и какие ответы получила и просит вас помочь ей определить, какие числа мог задумать Август. В первой строке задано n - максимальное число, которое мог загадать Август. Далее каждая строка содержит вопрос Беатрисы (множество чисел, разделенных пробелом) и ответ Августа на этот вопрос. Вы должны вывести через пробел, в порядке возрастания, все числа, которые мог задумать Август.

Answer 1

#include <iostream>

#include <set>

#include <sstream>

#include <algorithm>

using namespace std;

int main(){

   int n, num;

   string line;

   cout << "n = "; cin >> n;

   

   set <int> yes;

   set <int> no;

   stringstream ss;

   

   while(1) {

       ss.clear();

       getline(cin, line);

       if(line != "HELP" && line != "YES" && line != "NO") {

           ss << line;

           continue;

       }

       if(line == "HELP") break;

       if(line == "YES") {

           while(ss >> num) {

               yes.insert(num);

           }

           continue;

       }

       if(line == "NO") {

           while(ss >> num) {

               no.insert(num);

           }

           continue;

       }

   }

   set <int> result;

   set_difference(yes.begin(), yes.end(), no.begin(), no.end(), inserter(result, result.begin()));

   for(auto it = result.begin(); it != result.end(); it++) {

       cout << *it << " ";

   }

   return 0;

}

Дайте "лучший ответ" если решение правильное, пожалуйста, у меня уже 1000 из 500 баллов но не могу набрать 5 лучших ответов

Answer 2

Для решения этой задачи можно использовать массив булевых значений, чтобы отмечать, какие числа могли быть задуманы Августом. Изначально предполагаем, что все числа от 1 до n могут быть задуманы. Затем, после обработки ответов на вопросы Беатрисы, будем исключать числа, которые не могут быть задуманы.

Вот C++ программа для этой задачи:

cppCopy code
#include <iostream>
#include <vector>

using namespace std;

int main() {
    int n;
    cin >> n;

    vector<bool> possible(n, true); // Изначально все числа могут быть задуманы

    while (true) {
        string question;
        cin >> question;

        if (question == "HELP") {
            break; // Завершаем ввод вопросов
        }

        vector<bool> isPresent(n, false); // Создаем массив для текущего вопроса

        int num;
        while (cin >> num) {
            if (num == 0) {
                break; // Завершаем ввод чисел для текущего вопроса
            }
            isPresent[num - 1] = true; // Помечаем числа, которые есть в текущем вопросе
        }

        string answer;
        cin >> answer;

        if (answer == "YES") {
            // Если ответ "YES", то оставляем только те числа, которые есть в вопросе
            for (int i = 0; i < n; ++i) {
                if (!isPresent[i]) {
                    possible[i] = false;
                }
            }
        } else {
            // Если ответ "NO", то исключаем все числа, которые есть в вопросе
            for (int i = 0; i < n; ++i) {
                if (isPresent[i]) {
                    possible[i] = false;
                }
            }
        }
    }

    // Выводим числа, которые могли быть задуманы
    for (int i = 0; i < n; ++i) {
        if (possible[i]) {
            cout << i + 1 << " ";
        }
    }
    cout << endl;

    return 0;
}

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