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

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

Запись от eaa размещена 03.09.2023 в 13:10
Показов 10622 Комментарии 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 вне форума
 
Новые блоги и статьи
[golang] Двоичная куча, min-heap
alhaos 20.05.2026
Двоичная куча Двоичная куча — структура данных, которая всегда держит самый важный элемент наготове. Представьте очередь к хилеру в игре, и очередь из игроков в приоритете те у кого меньше. . .
[golang] Breadth-First Search
alhaos 19.05.2026
BFS (Breadth-First Search) — это базовый алгоритм обхода графа в ширину, который поуровнево исследует все связанные вершины. Он начинает с выбранной точки и проверяет всех соседей, прежде чем. . .
[golang] Алгоритм «Хак Госпера»
alhaos 17.05.2026
Алгоритм «Хак Госпера» Хак Госпера (Gosper's Hack) — алгоритм нахождения следующего по величине числа с тем же количеством установленных бит. Придуман Биллом Госпером в 1970-х, опубликован в. . .
Рисование бинарного древа до 6-го колена на js, svg.
russiannick 17.05.2026
<svg width="335" height="240" viewBox="0 0 335 240" fill="#e5e1bb"> <style> <!]> </ style> <g id="bush"> </ g> </ svg> function fn(){ let rost;/ / высота древа let xx=165,yy=210,w=256;
FSharp: interface of module
DevAlt 16.05.2026
Интерфейс модуля F# позволяет управлять доступностью членов, содержащихся в реализации модуля. По-умолчанию все члены модуля доступны: module Foo let x = 10 let boo () = printfn "boo" . . .
Хитросплетение родственных связей пантеона греческих богов.
russiannick 14.05.2026
Однооконник, позволяющий узреть и изучить отдельных героев древней Греции. <!DOCTYPE html> <html lang="ru"> <head> <meta charset="UTF-8"> <meta http-equiv="X-UA-Compatible". . .
[golang] Угол между стрелками часов
alhaos 12.05.2026
По заданным значениям часа и минуты необходимо определить значение меньшего угла между стрелками аналогового циферблата часов. import "math" func angleClock(hour int, minutes int) float64 { . . .
Debian 13: Установка Lazarus QT5
ВитГо 09.05.2026
Эта инструкция моя компиляция инструкций volvo https:/ / www. cyberforum. ru/ blogs/ 203668/ 10753. html и его же старой инструкции по установке Lazarus с gtk2. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru