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

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

Войти
Регистрация
Восстановить пароль
 
snyp
4 / 4 / 4
Регистрация: 11.06.2013
Сообщений: 27
#1

Сортировка массива - олимпиадная задача - C++

17.06.2013, 16:52. Просмотров 392. Ответов 4
Метки нет (Все метки)

Помогите, пожалуйста, решить такую задачу:

Так как Т.В.С., М.И.М. и Г.Д.М. живут далеко от школы, то каждый день они вот
уже много лет как минимум два раза в день ездят на автобусах. В связи с этим у них
выработалась привычка составлять с помощью знаков арифметических действий и скобок
число 100 из номера билета. После того, как каждый из них приезжает домой, он достает
из карманов билеты, пишет на каждом из них текущую дату и складывает в шкаф. Их
родителям такое хранение билетов не нравится(зачем хранить мусор?), поэтому они
регулярно заставляют их выкидывать. Недавно один из участников первой команды
решил, перед тем, как выкинуть, отсортировать накопившиеся билеты по дате их
покупки. Но это оказалось не так легко, как казалось, потому что билетов было очень
много. Поэтому он обращается к вам за помощью.
Выходные данные:
В первой строке содержится число N – количество билетов(1<=N<=100000). Далее
записано N дат билетов, разделенных пробелами или символами перевода строки. Каждая
дата представляет собой четырехзначное число, первые две цифры которого означают
день покупки, а вторые две – ее месяц (например, 0309 – 3 сентября).
Выходные данные:
В каждой строке должны содержаться (по одному) отсортированные даты
приобретения билетов в том же формате, что и во входном файле.
Пример:
input
5 0203 0302
1512
0409 0101
output
0101
0302
0203
0409
1512

Задача из прошедшей олимпиады для школьников, дорешиваю, но никак на 100 баллов не тянет. Проверяющая система за нижеследующий код даёт 56 баллов из 100:
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
28
29
30
#include <iostream>
 
using namespace std;
 
int main(){
    int n, i, j, c, o;
    int w[100000];
    int a[100000];
    cin>>n;
    for (i=1; i<=n; i++)
        cin>>a[i];
    for (i=1; i<=n; i++)
        w[i] = (a[i]/100)+(a[i]%100)*100;
    for (i=1; i<=n; i++)
        for (j=i; j<=n; j++)
            if (w[i]>w[j])
            {
                c=a[i];
                a[i]=a[j];
                a[j]=c;
                o=w[i];
                w[i]=w[j];
                w[j]=o;
            }
    for (i=1; i<=n; i++)
        if (a[i]<1000)
            cout<<0<<a[i]<<endl;
        else cout<<a[i];
    return 0;
}
Быть может, вы сможете её откорректировать? Или предложите свой вариант?
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
17.06.2013, 16:52
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Сортировка массива - олимпиадная задача (C++):

Задача на дп (олимпиадная) - C++
Здравствуйте, имеется данная задача, основная проблема состоит в том, что мое решение никак не проходит по времени. Пробовал писать через...

Олимпиадная задача - C++
Алфавит мурмарианской системы счисления включает три цифры - 1, 2 и 3. Одна из популярных социальных сетей &quot;НаМурмаре&quot; при регистрации...

Олимпиадная задача - C++
#include &lt;cstdio&gt; #include &lt;cstdlib&gt; #include &lt;iostream&gt; using namespace std; int main() { unsigned int N; cout&lt;&lt;&quot;N=&quot;;...

Олимпиадная задача - C++
Вот наткнулся сегодня на такую задачу: Всем известно, что в позапрошлом веке ковбои занимались перегоном скота. Перегон скота всегда...

Олимпиадная задача - C++
Дошел до этой олимпиадной задачи и впал в ступор. Нагуглил, что можно решить с помощью матриц, либо с помощью графов, но какого-то...

Олимпиадная задача - C++
Есть такая задачка: В ряд выписаны числа, состоящие только из цифр 1, 3, 7: 1, 3, 7, 11, 13, 17, ... Необходимо по номеру N определить...

4
dr.curse
389 / 345 / 16
Регистрация: 11.10.2010
Сообщений: 1,907
17.06.2013, 17:00 #2
snyp, на первый взгляд проблема в сортировке она же квадратичная, поэтому при 100000 будет очень долго, могу предложить использовать другую сортировку например быструю
1
Thinker
Эксперт С++
4228 / 2202 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
17.06.2013, 17:21 #3
сортировка подсчетом вам поможет. заведите прямоугольную матрицу порядка 12 на 31 и вперед. сложность алгоритма будет линейной и по времени ОЧЕНЬ быстрой.
1
salam
171 / 152 / 16
Регистрация: 10.07.2012
Сообщений: 751
17.06.2013, 17:22 #4
во-первых, как вам правильно намекнули, пузырек не пройдет. используйте std::sort(). только учитывайте, что сравнение должно происходить в данном случае нестандартно. нужно сравнивать сначала месяц, потом число.
1
Thinker
Эксперт С++
4228 / 2202 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
17.06.2013, 18:03 #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
#include <iostream>
 
using namespace std;
 
int main(){
    int n, d, i, j, k;
    int count[12][31] = {0};
    cin >> n;
    for (i = 0; i < n; ++i)
    {
        cin >> d;
        ++count[d % 100 - 1][d / 100 - 1];
    }
    for (i = 0; i < 12; ++i)
       for (j = 0; j < 31; ++j)
         for (k = 0; k < count[i][j]; ++k)
         {
             d = (j + 1) * 100 + i + 1;
             if (d < 1000)
                cout << 0 << d << endl;
             else
                cout << d << endl;
         }
    return 0;
}
1
17.06.2013, 18:03
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
17.06.2013, 18:03
Привет! Вот еще темы с ответами:

C++. Олимпиадная задача - C++
Здравствуйте! Код не проходит какой-то тест, может алгоритм не правильный. И если не правильный, то как исправить? Помогите найти ошибку....

Олимпиадная задача - C++
Был в прошлом году на олимпиаде по программированию и там была такая задача: После запуска программы пользователь должен начать...

Олимпиадная задача. Деревни - C++
Всем привет.. задача такая: Деревни В тридесятом государстве есть N деревень. Некоторые пары деревень соединены дорогами. В целях...

Олимпиадная задача на числа - C++
Условие задачи: Задано 121 натуральне число : 1...121 .Разбить числа в 11 групп так,чтобы каждая группа вмещала 11 чисел,каждое число...


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

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

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