Решение вступительных заданий 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 Решение: (Бинарный поиск по ответу)
Ограничение времени, с 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- поиск в ширину)
| ||||||||||
Размещено в Без категории
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Всего комментариев 3
Комментарии
-
Запись от AlexProgramm размещена 09.09.2023 в 08:35
-
JAVA
Введите N и M через пробел: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!"); } }
3 6
Места с печеньками: 3. Время: 6
Введите точное количество печенек в 3 местах :
4
4
5
3 6
4
4
5
min = 3
Hello World!Запись от AlexProgramm размещена 24.09.2023 в 11:05
-
Запись от AlexProgramm размещена 24.09.2023 в 11:07






