3 / 3 / 0
Регистрация: 05.10.2011
Сообщений: 86
1

Носки

13.10.2012, 15:56. Показов 12212. Ответов 4
Метки нет (Все метки)

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 чисел – толщину носкового покрытия в каждой точке.
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
13.10.2012, 15:56
Ответы с готовыми решениями:

Определить максимальное количество дней, в которые Даниил сможет носить разноцветные носки
Добрый день. Нужна помощь в решении задачи. У Даниила есть a красных и b зеленых носков. Даниил...

Олимпиада (носки и шахматы)
Два интересных, но сложных для меня задания. 1. В одной военной части было принято революционное...

Нужно ли под кроссовки обувать носки?
Всем доброго времени суток. Так получилось, что я остановил свой выбор на кроссовках и джинсах....

как заставить мужчину убирать грязные носки?
Встречный вопрос: как заставить мужчину убирать грязные носки? :D

4
Эксперт С++
1674 / 1046 / 174
Регистрация: 27.09.2009
Сообщений: 1,945
13.10.2012, 16:03 2
Очевидно, здесь имеются допущения. Стол рассматривается как одномерная сущность (фактически, прямая линия), носки на которой выкладываются "цепочкой" - то есть, это взаимоперекрывающиеся отрезки на нашей прямой-"столе". Задача - определить количество отрезков, перекрывающих каждую данную точку. Это количество для каждой точки X - количество отрезков, для которых выполняется условие l <= X && r >= X. Разумеется, для большого количества носков и точек решать задачу полным перебором будет неоптимально, нужны дополнительные алгоритмические ухищрения для ускорения процесса.
0
320 / 270 / 128
Регистрация: 24.05.2012
Сообщений: 629
13.10.2012, 16:33 3
Если есть много памяти, можно попытаться сделать так:
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;
}
Однако подозреваю, что все равно пролетит по времени, если длина носков будет соизмерима с длиной стола.
0
Эксперт С++
1674 / 1046 / 174
Регистрация: 27.09.2009
Сообщений: 1,945
13.10.2012, 17:05 4
Цитата Сообщение от Кот Ангенс Посмотреть сообщение
C++
1
2
short l, m, n;
cin >> l >> m >> n;
Не пойдёт - у M лимит до 100 000, в short не влезет, даже в unsigned short. Ну и в задании указан порядок L, N, M, а не как тут написано.
0
Эксперт С++
4727 / 2548 / 757
Регистрация: 18.08.2009
Сообщений: 4,568
13.10.2012, 17:23 5
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;
    
}
2
13.10.2012, 17:23
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
13.10.2012, 17:23
Помогаю со студенческими работами здесь

Расчитать дату окончания срока носки одежды
1 Нужна формула которая бы рассчитывала дату окончания срока носки 2 При условии что у...

Выделить цветом окончание срока носки спецодежды
Прошу Вашей помощи, необходимо выделить цветом окончание срока носки спец одежды, но сроки на...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
5
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2024, CyberForum.ru