Форум программистов, компьютерный форум, киберфорум
eaa
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск  

Решение вступительных заданий schol.hh.ru 2023

Запись от eaa размещена 03.09.2023 в 13:10
Показов 10751 Комментарии 3

Задача 1. Офисные печеньки

Ограничение времени, с 1
Ограничение памяти, МБ 64

Разработчик Фёдор очень любит печеньки в офисе, и он точно знает все N мест, где их можно найти, а также точное количество печенек Сn в каждом месте. Сегодня Фёдор особенно голоден, он закончил большую задачу, и решает выделить себе M часов на то, чтобы съесть все печеньки в офисе.

Фёдор рассчитал минимальное количество печенек K, которое ему нужно съедать в течение часа так, чтобы в итоге успеть съесть все печеньки в офисе за выделенное время или раньше.

В каждый час, он может посетить одно любое место с печеньками и съесть K печенек в этом месте, он потратит на это целый час, даже если в этом месте осталось меньше, чем K печенек, потому что будет обсуждать с коллегами задачи и планы. Места без печенек Фёдор может не посещать.

Коллеги, из уважения к Фёдору, никогда не трогают его любимые печеньки


Входные данные (поступают в стандартный поток ввода)
Первая строка - целые числа N и M через пробел (1≤N≤100 000, 1≤M≤200 000)

Далее N строк, на каждой из которых одно целое число Cn (0≤Cn≤10 000)

Все входные данные наших тестов всегда соблюдают указанные параметры, дополнительные проверки не требуются


Выходные данные (ожидаются в стандартном потоке вывода)
Одно целое число, минимально возможное K. Либо 0, если в офисе нет печенек, или если Фёдор не успеет съесть все печеньки за выделенное время.

Пример 1
Ввод:
3 6
4
4
4

Вывод:
2
Простой пример для ознакомления с входными и выходными данными

Пример 2
Ввод:
3 6
4
4
5

Вывод:
3
Здесь похожая ситуация, но съедая по 2 печеньки, Фёдор не успеет съесть последнюю

Пример 3
Ввод:
3 3
6
6
8

Вывод:
8
Граничная ситуация при N = M

Решение: (Бинарный поиск по ответу)
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def solve(n, m, arr):
    if m < n or n == 0:
        return 0
    lo = 1
    hi = max(arr)
    while lo < hi:
        mid = (lo + hi) // 2
        if sum((c + mid - 1) // mid for c in arr) <= m:
            hi = mid
        else:
            lo = mid + 1
    return lo
 
 
n, m = map(int, input().split())
cookies = [int(input()) for _ in range(n)]
cookies = [x for x in cookies if x > 0]
n = len(cookies)
print(solve(n, m, cookies))
Задача 2. Лабиринт

Ограничение времени, с 1
Ограничение памяти для Python, МБ 64

Вы очнулись в определённой ячейке (x1,y1) лабиринта, с его картой в руке. Карта показывает, что лабиринт представляет собой окружённый сплошной стеной прямоугольник высотой N и шириной M, состоящий из ячеек, каждая ячейка самого лабиринта – это проход 0 или стена 1. Перемещаться по лабиринту можно по горизонтали (меняя координату x) либо по вертикали (меняя координату y) на одну ячейку, перемещаться по диагонали (меняя за один шаг обе координаты) нельзя.

На карте отмечен выход, и он находится в ячейке с координатами (x2,y2).

Ваша задача – найти длину кратчайшего пути из ячейки пробуждения в ячейку выхода. В случае, если такого пути нет – нужно вывести 0


Входные данные (поступают в стандартный поток ввода)
Первая строка - целые числа N и M через пробел (2≤N≤500, 2≤M≤500)

Вторая строка – целые числа x1 и y1 через пробел (0≤x1≤499, 0≤y1≤499) – координаты точки пробуждения

Третья строка – целые числа x2 и y2 через пробел (0≤x2≤499, 0≤y2≤499) – координаты точки выхода

Далее N строк, на каждой из которых M чисел 0 или 1 через пробел

Нумерации осей в передаваемых значениях следуют слева направо для X и с первой полученной строки до последней для Y.
По координатам (x1,y1) и (x2,y2) всегда будут проходы. Координаты точки входа и выхода не совпадают.

Все входные данные наших тестов всегда соблюдают указанные параметры, дополнительные проверки не требуются


Выходные данные (ожидаются в стандартном потоке вывода)
Одно целое число, длина кратчайшего пути из точки (x1,y1) в точку (x2,y2), или 0,
если из одной точки нельзя попасть в другую

Пример 1
Ввод:
2 3
0 0
2 1
0 0 0
0 0 0

Вывод:
3
Пример без стен для понимания структуры входных данных

Пример 2
Ввод:
3 3
0 0
2 0
0 1 0
0 1 0
0 0 0

Вывод:
6
Придётся обойти стену

Пример 3
Ввод:
3 3
0 0
2 0
0 1 0
0 1 0
0 1 0

Вывод:
0
А здесь обойти не получится, выход недостижим

Решение: (BFS- поиск в ширину)
Python
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
from collections import deque
 
n, m = map(int, input().split())
y1, x1 = map(int, input().split())
y2, x2 = map(int, input().split())
laboratory = [[*map(int, input().split())] for _ in range(n)]
 
q = deque()
dist = [[-1] * m for _ in range(n)]
q.append((x1, y1))
dist[x1][y1] = 0
 
while q:
    tx, ty = q.popleft()
    if tx == x2 and ty == y2:
        print(dist[x2][y2])
        break
    for dx, dy in [(0, 1), (1, 0), (0, -1,), (-1, 0)]:
        xn = tx + dx
        yn = ty + dy
        if (0 <= xn < n) and (0 <= yn < m) and (laboratory[xn][yn] == 0) and (dist[xn][yn] == -1):
            dist[xn][yn] = dist[tx][ty] + 1
            q.append((xn, yn))
else:
    print(0)
Размещено в Без категории
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Всего комментариев 3
Комментарии
  1. Старый комментарий
    Аватар для AlexProgramm
    Интересные задания
    Запись от AlexProgramm размещена 09.09.2023 в 08:35 AlexProgramm вне форума
  2. Старый комментарий
    Аватар для AlexProgramm
    JAVA

    Java
    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
    93
    
    package forum.forumjava27;
     
    import java.io.BufferedReader;
    import java.io.IOException;
    import java.io.InputStreamReader;
    import java.util.Scanner;
    import static javax.swing.text.html.HTML.Attribute.N;
     
     
    public class ForumJava27 {
     
        public static void main(String[] args) throws IOException {
            
            int n, m, sumAll = 0;
            
            System.out.println("Введите N и M через пробел: ");
            BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
            String str = reader.readLine();
            //reader.close(); 
            String[] splitStr = str.split(" ");
            if (splitStr.length > 2) {
                System.out.println("Ошибка!");
                return;
            }
            n = Integer.parseInt(splitStr[0]);
            m = Integer.parseInt(splitStr[1]);
            if (n < 1 || n > 100000 || m < 1 || m > 200000) {
                System.out.println("Ошибка!");
                return;
            }
            System.out.println("Места с печеньками: " + n + ". Время: " + m);
            System.out.println();
            System.out.println("Введите точное количество печенек в " + n + " местах : ");
            //Scanner sc = new Scanner(System.in);
            BufferedReader stcol = new BufferedReader(new InputStreamReader(System.in));
            
            //создаем целочисленный массив из количества мест, со значениями по количеству печенек
            int[] col = new int[n];
            for (int i = 0; i < col.length; i++) {
                col[i] = Integer.parseInt( stcol.readLine());
                if (col[i] < 0 || col[i] > 10000) {
                    System.out.println("Ошибка!");
                    return;
                }
                
            }
            stcol.close();
            reader.close();
            
            //выводим введенные данные на экран
            System.out.println(n + " " + m);
            for (int i = 0; i < n; i++) {
                System.out.println(col[i]);
                sumAll = sumAll + col[i];
            }
            
            //p- печеньки, h - часы, к - минимальное кол-во печенек, j - место для печенек
            // sumAll - общее колич печенек
            int j = 0, p, h;
            p = col[j];
            h = m;
            //начинаем с 1 печенек, если циклы не пройдут, то будем увеличивать к
            for (int k = 1; k <= sumAll; k++) {
                h = m;
                //идем по каждому месту с печеньками
                for (j = 0; j < col.length; j++) {
                    p = col[j];
                    //идем по количеству печенек в одном каждом месте
                    for(int i = 1; i <= col[j]; i++) {
                        p = p - k; 
                        h = h - 1; 
                        //если заканчиватся печеньки или часы, то выходим из цикла
                        if (p <= 0 || h <= 0)
                            break;
                    }
                    //если заканчиваются часы, то значит это минимальное количество печенек не хватит, К нужно больше 
                    if (h <= 0)
                        break;
                    
                    // если не вышли, значит возвращаемся к увеличению j , тоесть переходим к следующему месту с печеньками
                }
                
                //если выполняются условия, то мы нашли МИН К
                if (h >= 0 && j == (col.length - 1) && p <= 0) {
                    System.out.println("min = " + k);
                    break;
                }
                    
            }
            
            System.out.println("Hello World!");
        }
    }
    Введите N и M через пробел:
    3 6
    Места с печеньками: 3. Время: 6

    Введите точное количество печенек в 3 местах :
    4
    4
    5
    3 6
    4
    4
    5
    min = 3
    Hello World!
    Запись от AlexProgramm размещена 24.09.2023 в 11:05 AlexProgramm вне форума
  3. Старый комментарий
    Аватар для AlexProgramm
    Не возьмут меня в школу HH
    длинный код, и думал неск дней
    Запись от AlexProgramm размещена 24.09.2023 в 11:07 AlexProgramm вне форума
 
Новые блоги и статьи
мат медиц модель 30. презентация проекта
anaschu 27.08.2026
хоп хоп хоп хидахоп, а я кладую))
Как у меня протекала болезнь
zorxor 27.08.2026
Здравствуйте, друзья! Эта запись блога предназначена именно для вас - для моих дорогих друзей, которые знали меня лично. Чтобы ответить на вопрос - а что же со мной произошло на самом деле? Я учился. . .
Нашел вот забавное видео о измерениях. Лучшее что я видел на эту тему
kumehtar 26.08.2026
ILETXiw9bMQ Основная суть и тезисы по измерениям: 0D (Нулевое измерение): точка, не имеющая длины, ширины, высоты или объема. Объект не может перемещаться в 0D. 1D (Первое измерение):. . .
[EasyBuilder Pro] Памятка по разработке для панелей Weintek
ФедосеевПавел 26.08.2026
Памятка по разработке для панелей Weintek ВВЕДЕНИЕ Ранее, при реализации проектов основное внимание уделял разработке управляющей программы для контроллера, а панели оператора доставалось время. . .
Модель по догадкам
anaschu 25.08.2026
Прошло две недели. Я уже рассказывал, как разговаривал с сотрудниками у сортировки и как понял, что главная ветка — не про приёмку, а про отбор. Но тогда я думал, что понял механику. На этой неделе я. . .
Запись в регистр сведений независимо от заполненности табличной части
Maks 25.08.2026
Реализация из решения ниже выполнена на нетиповом документе с несколькими табличными частями, разработанного в КА2. Задача: Обеспечить запись документа в регистр сведений независимо от. . .
Ноутбук Альфария
kumehtar 24.08.2026
Встретился тут в сети ноутбук Альфария, примарха Альфа-Легиона. Хотя возможно, это ноутбук Омегона, разумеется. Ну как вам?
Мастера простых решений
DevAlt 23.08.2026
В сишарп стэках winforms, да и wpf существует сложная система связывания источниках данных и элементов формы(текстовые поля и метки), опирается все это на технологию событий и мета. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru