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

Решение задач из Russiancodecup (Первый квалификационный раунд) - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 11, средняя оценка - 4.73
Sudoki
124 / 64 / 1
Регистрация: 19.04.2010
Сообщений: 196
21.09.2011, 09:29     Решение задач из Russiancodecup (Первый квалификационный раунд) #1
http://russiancodecup.ru/contest/1
"A" Конкатенация строк
Во многих прикладных задачах необходимо осуществлять различные операции со строками. Две достаточно часто встречающиеся операции — это разворот строки и конкатенация двух или нескольких строк.
В результате разворота строки s получается строка sR, которая состоит из тех же символов, что и s, но идущих в обратном порядке. Например, в результате разворота строки “abcde” получается строка “edcba”. Далее в этой задаче вместо обозначения sR будет использоваться обозначение (s).
В результате конкатенации двух строк s и t получается строка st, в которой сначала записаны символы строки s, а затем — символы строки t. Аналогичным образом определяется конкатенация трех, четырех и большего числа строк. Например, при конкатенации строк “abc” и “cda” получается строка “abccda”
Ваша задача — определить результат конкатенации нескольких строк, часть из которых необходимо развернуть.
Формат входных данных
Входные данные состоят из единственной строки, которая содержит только строчные буквы латинского алфавита и круглые скобки. Ее длина не превышает 200 символов. Эта строка описывает конкатенацию нескольких строк, часть из которых необходимо развернуть.
В заданной строке правее каждой открывающей скобки есть закрывающая, левее каждой закрывающей есть открывающая, причем между соответствующими друг другу открывающей и закрывающей скобками других скобок нет и обязательно есть хотя бы одна буква.
Формат выходных данных Выведите результат конкатенации.
Примеры
Входные данные Выходные данные
russ(ai)(edocn)cup russiancodecup
Лучшие ответы (1)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
21.09.2011, 09:29     Решение задач из Russiancodecup (Первый квалификационный раунд)
Посмотрите здесь:

Решение задач С++ C++
C++ решение задач С++
Решение задач С++ C++
Решение задач C++
C++ Решение задач с Си++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Sudoki
124 / 64 / 1
Регистрация: 19.04.2010
Сообщений: 196
21.09.2011, 09:34  [ТС]     Решение задач из Russiancodecup (Первый квалификационный раунд) #2
Свое решение задачи
Вложения
Тип файла: txt c11.txt (1.2 Кб, 61 просмотров)
Евгений М.
21.09.2011, 10:04
  #3

Не по теме:

Почему такие темы создаются в "сях для чайников" (без обид), а не в отдельном разделе, где рассматривают олимпиадные задачи?
Просто смотреть этот раздел вообще не хочется из-за наплывов студентов, а сегодня случайно нашел в непрочитанных сообщениях.

fasked
Эксперт C++
 Аватар для fasked
4925 / 2505 / 180
Регистрация: 07.10.2009
Сообщений: 4,306
Записей в блоге: 1
21.09.2011, 12:27     Решение задач из Russiancodecup (Первый квалификационный раунд) #4
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
#include <string.h>
#include <stdio.h>
 
#define MAXSIZE 201
 
int main() {
    char in[MAXSIZE] = "russ(ai)(edocn)cup";
    char out[MAXSIZE] = "";
 
    int m, k, i = 0, j = 0, len = strlen(in);
 
    for (; i < len; ++i) {
        if (in[i] != '(') {
            out[j++] = in[i];
        }
        else {
            for (k = i + 1; in[k] != ')'; ++k);
            for (m = k-1; k != ++i; --m)
                out[j++] = in[m];
        }
    }
 
    printf("%s\n", out);
}
Первое, что пришло в голову.
Thinker
Эксперт C++
 Аватар для Thinker
4215 / 2189 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
21.09.2011, 12:45     Решение задач из Russiancodecup (Первый квалификационный раунд) #5
Цитата Сообщение от Евгений М. Посмотреть сообщение

Не по теме:

Почему такие темы создаются в "сях для чайников" (без обид), а не в отдельном разделе, где рассматривают олимпиадные задачи?
Просто смотреть этот раздел вообще не хочется из-за наплывов студентов, а сегодня случайно нашел в непрочитанных сообщениях.

Не по теме:

С одной стороны, Вы правы. А с другой, как быть тем, кого в раздел "C++ для экспертов" не пускают без заявки, вот и тусуемся здесь

Евгений М.
21.09.2011, 18:15
  #6

Не по теме:

Thinker, для этого есть раздел Алгоритмы.

Evg
Эксперт С++Автор FAQ
 Аватар для Evg
16833 / 5254 / 323
Регистрация: 30.03.2009
Сообщений: 14,145
Записей в блоге: 26
21.09.2011, 20:08     Решение задач из Russiancodecup (Первый квалификационный раунд) #7
Сообщение было отмечено автором темы, экспертом или модератором как ответ

Не по теме:

Цитата Сообщение от Thinker Посмотреть сообщение
С одной стороны, Вы правы. А с другой, как быть тем, кого в раздел "C++ для экспертов" не пускают без заявки, вот и тусуемся здесь
Для этого есть просто раздел "Си\Си++"



Добавлено через 3 минуты
Цитата Сообщение от Sudoki Посмотреть сообщение
Свое решение задачи
Цикл по "while(*p2 != 0)" является излишним, т.к. в условии чётко сказано "правее каждой открывающей скобки есть закрывающая". Так что можно было при нахождении левой скобки смело писать цикл поиска правой скобки без контроля выходя за границу строки

Добавлено через 4 минуты
Если нет ограничений по памяти, то я бы использовал вариант по типу того, что писал fasked. Этот вариант использует дополнительный буфер, но при этом он алгоритмически проще и, судя по всему, работает побыстрее. Правда с точки зрения скорости более обоснованным было бы НЕ инициализировать массив out, а после цикла просто прилепить нолик: out[j]='\0';

Добавлено через 7 минут
И ещё, вместо конструкций типа

C
1
2
3
j = 0;
for (...)
  out[j++] = ...;
с точки зрения скорости исполнения было бы лучше написать

C
1
2
3
char *pout = out;
for (...)
  *pout++ = ...;
т.к. в этом случае должна экономиться одна операция сложения (а если бы был массив int'ов, а не char'ов, то экономилась бы ещё и операция умножения на sizeof, который в этом случае был бы отличен от единицы). Теоретически продвинутые компиляторы в таких простых случаях должны уметь сами делать такую оптимизацию, но будут делать или нет - хз
Gepar
 Аватар для Gepar
1173 / 529 / 20
Регистрация: 01.07.2009
Сообщений: 3,512
21.09.2011, 21:14     Решение задач из Russiancodecup (Первый квалификационный раунд) #8
Какое условие хитрое, обычная конкатенация строк, а так замудрили.
fasked
Эксперт C++
 Аватар для fasked
4925 / 2505 / 180
Регистрация: 07.10.2009
Сообщений: 4,306
Записей в блоге: 1
21.09.2011, 21:56     Решение задач из Russiancodecup (Первый квалификационный раунд) #9
Цитата Сообщение от Evg Посмотреть сообщение
И ещё, вместо конструкций типа
Да само собой многое можно улучшить Но, алгоритмически, разницы не будет. Я хотел показать насколько более простой можно написать алгоритм, чем у ТС. Так как-то мудрено все же...
Однако, я не отмазываюсь, мог сразу написать правильно, но не написал. В следующий раз буду учитывать.

Куда интереснее было бы увидеть алгоритм без дополнительной памяти.
Evg
Эксперт С++Автор FAQ
 Аватар для Evg
16833 / 5254 / 323
Регистрация: 30.03.2009
Сообщений: 14,145
Записей в блоге: 26
21.09.2011, 23:40     Решение задач из Russiancodecup (Первый квалификационный раунд) #10
Цитата Сообщение от fasked Посмотреть сообщение
Да само собой многое можно улучшить
Ну тебе-то понятно, но другим не всегда очевидно. В первую очередь для дургих писал особенно для начинающих
Mr.X
Эксперт С++
 Аватар для Mr.X
2807 / 1583 / 248
Регистрация: 03.05.2010
Сообщений: 3,688
22.09.2011, 00:23     Решение задач из Russiancodecup (Первый квалификационный раунд) #11
Цитата Сообщение от fasked Посмотреть сообщение
Куда интереснее было бы увидеть алгоритм без дополнительной памяти.
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 <algorithm>
#include <iostream>
#include <string>
/////////////////////////////////////////////////////////////////////////////////////////
typedef std::string  T_str;
/////////////////////////////////////////////////////////////////////////////////////////
void concat(T_str&  s)
{   
    T_str::iterator  L;
    while( ( L = std::find(s.begin(), s.end(), '(') ) != s.end() )
    {       
        T_str::iterator  R = std::find(L, s.end(), ')');
        std::reverse(L, R + 1);
        s.erase(R);
        s.erase(L);
    }   
}
/////////////////////////////////////////////////////////////////////////////////////////
int main()
{
    std::locale::global(std::locale(""));
    std::cout << "Введите строку:"
              << std::endl;
    T_str  s;
    std::cin >> s;
    concat(s);
    std::cout << s
              << std::endl;
}
Евгений М.
1033 / 974 / 53
Регистрация: 28.02.2010
Сообщений: 2,817
Завершенные тесты: 2
22.09.2011, 07:40     Решение задач из Russiancodecup (Первый квалификационный раунд) #12
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
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
#include <stdio.h>
 
int main()
{
    int i = 0, // по этому индексу будем записывать
        j,     // по этому читать
        k,     // для разных вещей
        first, // левый символ в скобках
        last,  // правый символ в скобках
        nzeros =0; // сколько лишних символов
 
 
    char str[201]={0}, c;
    gets(str);
    
    // пока не закончилась строка
    for (j=0; str[j]!=0; j++)
    {
        if (str[j]=='(')
        {
            k = j;
            // начало выражения в скобках
            first = k + 1;
            // прикрутим до закрывающися скобки
            while (str[k]!=')') k++;
            // конец выражения в скобках
            last = k - 1;
            // меняем местами
            while (first<=last)
            {
                c = str[first];
                str[first] = str[last];
                str[last] = c;
                first++;
                last--;
            }
            // сколько в конце символов стереть
            nzeros+=2;
            // идем дальше
            continue;
        }
 
        if (str[j]==')')
            continue;
 
        str[i++]=str[j];
    }
 
    // стираем ненужные символы
    i = j;
    for (k=0; k<nzeros; k++)
    {
        i--;
        str[i]=0;
    }
    
    puts(str);
}
Sudoki
124 / 64 / 1
Регистрация: 19.04.2010
Сообщений: 196
22.09.2011, 08:23  [ТС]     Решение задач из Russiancodecup (Первый квалификационный раунд) #13
"B" Тарифы
В настоящее время практически каждый оператор сотовой связи имеет обширный набор тарифов, которые позволяют каждому человеку выбрать наиболее подходящий для себя. К сожалению, зачастую осуществить этот выбор вручную очень тяжело.
У одного из сотовых операторов каждый тариф характеризуется тремя числами: абонентная плата ci (задается в рублях), минимальная тарифицируемая единица времени ti (задается в секундах), стоимость минимальной тарифицируемой единицы времени pi (задается в копейках, в одном рубле 100 копеек). Суммарная стоимость вызовов за месяц складывается из абонентной платы и стоимостей каждого из исходящих вызовов. Стоимость вызова при использовании i-ого тарифа вычисляется следующим образом: пусть время разговора равно T секунд. Если T < ti, то стоимость вызова равна нулю. Иначе стоимость вызова равна произведению k на pi, где k — минимальное целое число, такое что k·ti ≥ T.
Задано описание тарифов и статистика исходящих вызовов абонента в течение месяца — их число m и длительности d1, ..., dm в секундах. Необходимо найти тариф, при котором суммарная стоимость этих вызовов была бы минимальной.
Формат входных данных
Первая строка содержит два целых числа n и m — соответственно количество тарифов и исходящих вызовов абонента (1 ≤ n, m ≤ 100). Каждая из последующих n строк описывает один тариф и содержит три целых числа: ci (0 ≤ ci ≤ 100), ti (1 ≤ ti ≤ 3600), pi (0 ≤ pi ≤ 1000).
Последняя строка содержит m целых чисел d1, ..., dm (1 ≤ di ≤ 3600 для всех i от 1 до m).
Формат выходных данных
Выведите одно число — номер тарифа, при использовании которого суммарная стоимость исходящих вызовов абонента за рассматриваемый месяц минимальна. Тарифы нумеруются целыми числами от 1 до n в том порядке, в котором они заданы во входном файле. Если таких тарифов несколько, выведите номер любого из них.
Примеры
Входные данные
2 1
100 60 100
51 10 100
600
Выходные данные
1

Добавлено через 1 минуту
Забыл как их можно добавить в первый пост
Евгений М.
1033 / 974 / 53
Регистрация: 28.02.2010
Сообщений: 2,817
Завершенные тесты: 2
22.09.2011, 08:28     Решение задач из Russiancodecup (Первый квалификационный раунд) #14
Цитата Сообщение от Sudoki Посмотреть сообщение
Забыл как их можно добавить в первый пост
У модератора попросить.
Evg
Эксперт С++Автор FAQ
 Аватар для Evg
16833 / 5254 / 323
Регистрация: 30.03.2009
Сообщений: 14,145
Записей в блоге: 26
22.09.2011, 08:39     Решение задач из Russiancodecup (Первый квалификационный раунд) #15
Евгений М., по поводу поста #12. Хвостовые символы незачем стирать. Достаточно поставить один единственный нолик и он будет обозначать конец строки. А что идёт после этого - уже пофигу. Считай как просто неиспользуемая в строке память и незачем лишние такты тратить на заполнение их нулями
xAtom
 Аватар для xAtom
910 / 735 / 60
Регистрация: 09.12.2010
Сообщений: 1,346
Записей в блоге: 1
22.09.2011, 15:54     Решение задач из Russiancodecup (Первый квалификационный раунд) #16
Мой вариант.
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
#include <stdio.h>
char*  nc_strrev(char* str);
 
int  main(void) {
   char str[255] = "russ(ai)(edocn)cup";      
   puts(nc_strrev(str));
 
   getchar();
   return 0;
}
 
char*  nc_strrev(char* str) {
   char* tmp = str;
   char* pa, *pb, *pc, ch;
   while(*str) {
        if( *str == '(' ) {
            for(pa = str, pb = str + 1; *pa; *pa++ = *pb++);
            for(pb = str; *pb != ')' && *pb; *pb++);
            for(pa = pb, pc = pb + 1; *pa; *pa++ = *pc++);
            for(pb -= 1;str < pb; ++str, --pb) {
                    ch  = *str;
                   *str = *pb;
                   *pb = ch;
            }
        }
        *str++;
   }
   return tmp;
}
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
22.09.2011, 20:26     Решение задач из Russiancodecup (Первый квалификационный раунд)
Еще ссылки по теме:

Решение задач C++
Решение задач C++
Решение задач на C++ C++

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

Или воспользуйтесь поиском по форуму:
Jupiter
Каратель
Эксперт C++
6543 / 3963 / 226
Регистрация: 26.03.2010
Сообщений: 9,273
Записей в блоге: 1
Завершенные тесты: 2
22.09.2011, 20:26     Решение задач из Russiancodecup (Первый квалификационный раунд) #17
Цитата Сообщение от Sudoki Посмотреть сообщение
"B" Тарифы
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
31
32
33
34
35
36
#include <stdio.h>
#include <math.h>
 
int main(void)
{
    int n, m, call[100], rate[100][3], i, j, min_index = 0;
    float total_pay[100], *min = &total_pay[0];
    FILE* input = fopen("input.txt", "rt");
    FILE* output = fopen("output.txt", "wt");
    
    fscanf(input, "%d %d", &n, &m);
    
    for (i = 0; i < n; ++i)
        fscanf(input, "%d %d %d", &rate[i][0], &rate[i][1], &rate[i][2]);
    
    for (i = 0; i < m; ++i)
        fscanf(input, "%d", &call[i]);
    
    for (i = 0; i < n; ++i)
    {
        total_pay[i] = 100.0f * rate[i][0];
        for (j = 0; j < m; ++j)
            total_pay[i] += ceil((float)call[j] / rate[i][1]) * rate[i][2];
        if (total_pay[i] < *min)
        {
            min = &total_pay[i];
            min_index = i;
        }
    }
    
    fprintf(output, "%d", min_index + 1);
    
    fclose(input);
    fclose(output);
    return 0;
}
на первых шести(1-6) и двух последних(22-23) тестах и на 14 тесте все совпадает, на 19 тесте не совпало, на остальных не проверял
Yandex
Объявления
22.09.2011, 20:26     Решение задач из Russiancodecup (Первый квалификационный раунд)
Ответ Создать тему
Опции темы

Текущее время: 08:48. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru