Форум программистов, компьютерный форум CyberForum.ru
Наши страницы

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Ann Joker
3 / 3 / 1
Регистрация: 05.10.2011
Сообщений: 86
#1

Носки - C++

13.10.2012, 15:56. Просмотров 621. Ответов 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
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
13.10.2012, 15:56
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Носки (C++):

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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


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

Или воспользуйтесь поиском по форуму:
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Nick Alte
Эксперт С++
1637 / 1009 / 119
Регистрация: 27.09.2009
Сообщений: 1,945
Завершенные тесты: 1
13.10.2012, 16:03 #2
Очевидно, здесь имеются допущения. Стол рассматривается как одномерная сущность (фактически, прямая линия), носки на которой выкладываются "цепочкой" - то есть, это взаимоперекрывающиеся отрезки на нашей прямой-"столе". Задача - определить количество отрезков, перекрывающих каждую данную точку. Это количество для каждой точки X - количество отрезков, для которых выполняется условие l <= X && r >= X. Разумеется, для большого количества носков и точек решать задачу полным перебором будет неоптимально, нужны дополнительные алгоритмические ухищрения для ускорения процесса.
0
Кот Ангенс
317 / 267 / 38
Регистрация: 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
Nick Alte
Эксперт С++
1637 / 1009 / 119
Регистрация: 27.09.2009
Сообщений: 1,945
Завершенные тесты: 1
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
valeriikozlov
Эксперт C++
4670 / 2496 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
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;
    
}
0
Yandex
Объявления
13.10.2012, 17:23
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru