Skip to content
TheChatArchiveThe Chat Archive
gpt-3.5-turbo-0613· OpenAIAi2 WildChat-4.8M (AI2)

Тимур — поставщик продуктов в рестораны. Всего есть n ресторанов, в c из которых Тимур…

  1. User

    Тимур — поставщик продуктов в рестораны. Всего есть n ресторанов, в c из которых Тимур уже поставляет продукты. Также m пар ресторанов являются соседями друг для друга, при этом ресторан не может быть соседом сам себе и никакие два ресторана не могут быть соседями дважды. Ресторан нанимает Тимура как поставщика, если хотя бы в k соседей этого ресторана Тимур уже поставляет продукты. Напиши программу на java, которая узнает, сколько ресторанов наймут его по итогу.

    Формат входных данных Первая строка содержит три целых числа n, m, k (1 =< k =< n =< 2·10^5, 1 =< m =< 2·10^5), обозначающие количество ресторанов, количество пар соседей и количество соседей, необходимое для того, чтобы ресторан нанял Тимура, соответственно. В следующих m строчках содержится описание пар соседних ресторанов. Каждая строка содержит два различных целых числа — номера двух ресторанов, соседних друг другу. В следующей строке содержится целое число c (0 =< c =< n), обозначающее количество ресторанов, в которые Тимур с самого начала поставляет продукты. В следующей строке содержится c различных целых чисел от 1 до n — номера ресторанов, в которые Тимур уже поставляет продукты.

    Формат выходных данных В первой строке выведите целое число a — количество ресторанов, которые однажды наймут Тимура как поставщика. Во второй строке выведите a целых чисел — номера всех ресторанов, в которые Тимур будет поставлять продукты, в любом порядке.

  2. Assistant

    В данной задаче можно использовать алгоритм обхода графа, так как рестораны и их соседи образуют граф.

    Алгоритм решения задачи:

    1. Создать массив размером n, в котором будем хранить информацию о том, поставляет ли Тимур продукты в данный ресторан.
    2. Пройтись по списку ресторанов, в которые Тимур уже поставляет продукты, и пометить соответствующие элементы массива как true (Тимур уже поставляет продукты в эти рестораны).
    3. Пройтись по списку пар соседних ресторанов и пометить элементы массива соответствующих ресторанов как true, если соседний ресторан уже помечен как true и имеет необходимое количество соседей, получающих продукты от Тимура.
    4. Подсчитать количество ресторанов, в которые Тимур будет поставлять продукты, и создать новый массив для их хранения.
    5. Пройтись по массиву и записать номера ресторанов, в которые Тимур будет поставлять продукты, в новый массив.
    6. Вывести количество ресторанов и список номеров ресторанов, в которые Тимур будет поставлять продукты.

    Пример реализации на Java:

    import java.util.*;

    public class TimurRestaurant { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int n = scanner.nextInt(); int m = scanner.nextInt(); int k = scanner.nextInt();

        List<Integer>[] neighbors = new ArrayList[n+1]; // массив списков соседей для каждого ресторана
        for (int i = 1; i <= n; i++) {
            neighbors[i] = new ArrayList<>();
        }
        
        for (int i = 0; i < m; i++) {
            int a = scanner.nextInt();
            int b = scanner.nextInt();
            neighbors[a].add(b);
            neighbors[b].add(a);
        }
        
        int c = scanner.nextInt();
        boolean[] isSupplier = new boolean[n+1]; // массив для хранения информации о том, поставляет ли Тимур продукты в данный ресторан
        for (int i = 0; i < c; i++) {
            int restaurant = scanner.nextInt();
            isSupplier[restaurant] = true;
        }
        
        for (int i = 1; i <= n; i++) {
            if (isSupplier[i]) { // если Тимур уже поставляет продукты в данный ресторан
                for (int neighbor : neighbors[i]) {
                    if (!isSupplier[neighbor]) { // если соседний ресторан еще не помечен как true
                        int neighborsWithSupplier = 0; // количество соседей, получающих продукты от Тимура
                        for (int nighborNeighbor : neighbors[neighbor]) {
                            if (isSupplier[nighborNeighbor]) {
                                neighborsWithSupplier++;
                            }
                        }
                        if (neighborsWithSupplier >= k) {
                            isSupplier[neighbor] = true; // помечаем ресторан как тот, в котором Тимур будет поставлять продукты
                        }
                    }
                }
            }
        }
        
        int supplierCount = 0; // количество ресторанов, в которые Тимур будет поставлять продукты
        List<Integer> supplierRestaurants = new ArrayList<>(); // список ресторанов, в которые Тимур будет поставлять продукты
        for (int i = 1; i <= n; i++) {
            if (isSupplier[i]) {
                supplierCount++;
                supplierRestaurants.add(i);
            }
        }
        
        System.out.println(supplierCount);
        for (int restaurant : supplierRestaurants) {
            System.out.print(restaurant + " ");
        }
    }
    

    }