Замерить толщину покрытия стола носками

@Ann Joker · Регистрация: 05.10.2011

Author24 — интернет-сервис помощи студентам

Задание с одного сайта по дистанционному обучению. Помогите разобраться, что именно тут нужно делать. Не могу понять саму суть задачи..

Имеется стол длины L. На столе разложено N носков так, что никакой носок не вылезает за границы стола. Далее имеется умный мальчик Васёк, который хочет (сугубо в корыстных целях) замерить толщину покрытия стола носками в M точках.
Формат входного файла
Во входном файле даны сначала L, N, M (1 ≤ L ≤ 10000, 1 ≤ N ≤ 10000, 1 ≤ M ≤ 100000).
Далее идут N пар чисел l ≤ r от 1 до L – левые и правые концы носков.
Затем идут M чисел от 1 до L интересующие Васька точки.

Формат выходного файла
Выведите M чисел – толщину носкового покрытия в каждой точке.

@Nick Alte · 13.10.2012, 16:03

Очевидно, здесь имеются допущения. Стол рассматривается как одномерная сущность (фактически, прямая линия), носки на которой выкладываются "цепочкой" - то есть, это взаимоперекрывающиеся отрезки на нашей прямой-"столе". Задача - определить количество отрезков, перекрывающих каждую данную точку. Это количество для каждой точки X - количество отрезков, для которых выполняется условие l <= X && r >= X. Разумеется, для большого количества носков и точек решать задачу полным перебором будет неоптимально, нужны дополнительные алгоритмические ухищрения для ускорения процесса.

@Кот Ангенс · 13.10.2012, 16:33

Если есть много памяти, можно попытаться сделать так:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream>
 
using namespace std;
 
int main() {
    short l, m, n;
    cin >> l >> m >> n;
    int* table = new int[l];
    while (l--)
        table[l] = 0;
    short start, end;
    while (n--) {
        cin >> start >> end;
        start--;
        while (start < end)
            table[start++]++;
    }
    while (m--) {
        cin >> start;
        cout << table[start - 1] << endl;
    }
    delete[ ] table;
}

Однако подозреваю, что все равно пролетит по времени, если длина носков будет соизмерима с длиной стола.

@Nick Alte · 13.10.2012, 17:05

Сообщение от Кот Ангенс

C++
1
2
short l, m, n;
cin >> l >> m >> n;

Не пойдёт - у M лимит до 100 000, в short не влезет, даже в unsigned short. Ну и в задании указан порядок L, N, M, а не как тут написано.

valeriikozlov · 13.10.2012, 17:23

C++
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
#include <iostream>
 
using namespace std;
 
int main() {
    int l, m, n;
    cin >> l >> n >> m;
    int table[10001]={0};
    int start, end, i, t=0;
    while (n--) {
        cin >> start >> end;
        table[start-1]++;
        table[end]--;        
    }
    for(i=0; i<10001; i++)
    {
        t+=table[i];
        table[i]=t;
    }
    for(i=0; i<m; i++)
    {
        cin>>t;
        cout<<table[t-1]<<endl;
    }
    return 0;
    
}

Новые блоги и статьи Все статьи Все блоги /
Python NumPy: Лучшие практики и примеры py-thonny 17.03.2025 NumPy (Numerical Python) — одна из ключевых библиотек для научных вычислений в Python. Она превращает Python из просто удобного языка общего назначения в среду для проведения сложных математических. . .	Java Micronaut в Docker: контейнеризация с Maven и Jib Javaican 16.03.2025 Когда речь заходит о микросервисной архитектуре на Java, фреймворк Micronaut выделяется среди конкурентов. Он создан с учётом особенностей облачных сред и контейнеров, что делает его идеальным. . .	Управление зависимостями в Java: Сравнение Spring, Guice и Dagger 2 Javaican 16.03.2025 Инъекция зависимостей (Dependency Injection, DI) — один из фундаментальных паттернов проектирования, который радикально меняет подход к созданию гибких и тестируемых Java-приложений. Суть этого. . .	Apache Airflow для оркестрации и автоматизации рабочих процессов Mr. Docker 16.03.2025 Управление сложными рабочими процессами — одна из главных головных болей инженеров данных и DevOps-специалистов. Представьте себе: каждый день нужно запускать десятки скриптов в определенной. . .	Оптимизация приложений Java для ARM Javaican 16.03.2025 ARM-архитектура переживает настоящий бум популярности в технологическом мире. Когда-то воспринимаемая исключительно как решение для мобильных устройств и встраиваемых систем, сегодня она штурмует. . .
Управление состоянием в Vue 3 с Pinia и Composition API Reangularity 16.03.2025 Когда я начал работать с Vue несколько лет назад, мне казалось достаточным использовать простую передачу данных через props и события между компонентами. Однако уже на среднем по сложности проекте. . .	Введение в DevSecOps: основные принципы и инструменты Mr. Docker 16.03.2025 DevSecOps - это подход к разработке программного обеспечения, который объединяет в себе принципы разработки (Dev), безопасности (Sec) и эксплуатации (Ops). Суть подхода заключается в том, чтобы. . .	GitHub Actions vs Jenkins: Сравнение инструментов CI/CD Mr. Docker 16.03.2025 В этой битве за эффективность и скорость выпуска программных продуктов ключевую роль играют специализированные инструменты. Два гиганта в этой области — GitHub Actions и Jenkins — предлагают разные. . .	Реактивное программирование с Kafka Stream и Spring WebFlux Javaican 16.03.2025 Реактивное программирование – это программная парадигма, ориентированная на потоки данных и распространение изменений. Она позволяет выражать статические или динамические потоки данных и. . .	Простая нейросеть на КуМир: Учебное пособие по созданию и обучению нейронных сетей EggHead 16.03.2025 Искусственные нейронные сети — удивительная технология, позволяющая компьютерам имитировать работу человеческого мозга. Если вы хотя бы немного интересуетесь современными технологиями, то наверняка. . .

@Ann Joker 3 / 3 / 0 Регистрация: 05.10.2011 Сообщений: 86
		1
	Замерить толщину покрытия стола носками 13.10.2012, 15:56. Показов 12855. Ответов 4 Метки нет (Все метки) Задание с одного сайта по дистанционному обучению. Помогите разобраться, что именно тут нужно делать. Не могу понять саму суть задачи.. Имеется стол длины L. На столе разложено N носков так, что никакой носок не вылезает за границы стола. Далее имеется умный мальчик Васёк, который хочет (сугубо в корыстных целях) замерить толщину покрытия стола носками в M точках. Формат входного файла Во входном файле даны сначала L, N, M (1 ≤ L ≤ 10000, 1 ≤ N ≤ 10000, 1 ≤ M ≤ 100000). Далее идут N пар чисел l ≤ r от 1 до L – левые и правые концы носков. Затем идут M чисел от 1 до L интересующие Васька точки. Формат выходного файла Выведите M чисел – толщину носкового покрытия в каждой точке. 0

@Nick Alte 1675 / 1047 / 174 Регистрация: 27.09.2009 Сообщений: 1,945
	13.10.2012, 16:03	2
	Очевидно, здесь имеются допущения. Стол рассматривается как одномерная сущность (фактически, прямая линия), носки на которой выкладываются "цепочкой" - то есть, это взаимоперекрывающиеся отрезки на нашей прямой-"столе". Задача - определить количество отрезков, перекрывающих каждую данную точку. Это количество для каждой точки X - количество отрезков, для которых выполняется условие l <= X && r >= X. Разумеется, для большого количества носков и точек решать задачу полным перебором будет неоптимально, нужны дополнительные алгоритмические ухищрения для ускорения процесса. 0

Опции темы