125 / 65 / 9
Регистрация: 19.04.2010
Сообщений: 196
1

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

21.09.2011, 09:29. Показов 2754. Ответов 16
Метки нет (Все метки)

Author24 — интернет-сервис помощи студентам
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
Лучшие ответы (1)
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
21.09.2011, 09:29
Ответы с готовыми решениями:

Напишите программу, обрабатывающую один раунд игры «Быки и коровы»
Напишите программу, обрабатывающую один раунд игры «Быки и коровы». Пользователь вводит две строки....

Множество странных папок в C:\ProgramData и реклама при старте браузера (Раунд 2)
Здравствуйте прошу помочь avz не открывается в win 10 выдает остановка программы а так пытался все...

Решение задач на C#
на С# помогите, если не решу числанут( 1. Составить программу для вычисления значений функции...

Решение задач по ДМ
Уважаемые форумчане! Помогите, пожалуйста, решить вот эти 4 задачи! Я ни черта не понимаю!!! В...

16
125 / 65 / 9
Регистрация: 19.04.2010
Сообщений: 196
21.09.2011, 09:34  [ТС] 2
Свое решение задачи
Вложения
Тип файла: txt c11.txt (1.2 Кб, 66 просмотров)
0
Евгений М.
21.09.2011, 10:04
  #3

Не по теме:

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

0
Эксперт С++
5043 / 2622 / 241
Регистрация: 07.10.2009
Сообщений: 4,310
Записей в блоге: 1
21.09.2011, 12:27 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);
}
Первое, что пришло в голову.
1
Эксперт С++
4267 / 2241 / 203
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
21.09.2011, 12:45 5
Цитата Сообщение от Евгений М. Посмотреть сообщение

Не по теме:

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

Не по теме:

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

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

Не по теме:

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

0
Evg
Эксперт CАвтор FAQ
21279 / 8301 / 637
Регистрация: 30.03.2009
Сообщений: 22,659
Записей в блоге: 30
21.09.2011, 20:08 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, который в этом случае был бы отличен от единицы). Теоретически продвинутые компиляторы в таких простых случаях должны уметь сами делать такую оптимизацию, но будут делать или нет - хз
3
1186 / 542 / 78
Регистрация: 01.07.2009
Сообщений: 3,517
21.09.2011, 21:14 8
Какое условие хитрое, обычная конкатенация строк, а так замудрили.
0
Эксперт С++
5043 / 2622 / 241
Регистрация: 07.10.2009
Сообщений: 4,310
Записей в блоге: 1
21.09.2011, 21:56 9
Цитата Сообщение от Evg Посмотреть сообщение
И ещё, вместо конструкций типа
Да само собой многое можно улучшить Но, алгоритмически, разницы не будет. Я хотел показать насколько более простой можно написать алгоритм, чем у ТС. Так как-то мудрено все же...
Однако, я не отмазываюсь, мог сразу написать правильно, но не написал. В следующий раз буду учитывать.

Куда интереснее было бы увидеть алгоритм без дополнительной памяти.
0
Evg
Эксперт CАвтор FAQ
21279 / 8301 / 637
Регистрация: 30.03.2009
Сообщений: 22,659
Записей в блоге: 30
21.09.2011, 23:40 10
Цитата Сообщение от fasked Посмотреть сообщение
Да само собой многое можно улучшить
Ну тебе-то понятно, но другим не всегда очевидно. В первую очередь для дургих писал особенно для начинающих
1
Эксперт С++
3224 / 1751 / 436
Регистрация: 03.05.2010
Сообщений: 3,867
22.09.2011, 00:23 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;
}
2
1080 / 1007 / 106
Регистрация: 28.02.2010
Сообщений: 2,889
22.09.2011, 07:40 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);
}
0
125 / 65 / 9
Регистрация: 19.04.2010
Сообщений: 196
22.09.2011, 08:23  [ТС] 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 минуту
Забыл как их можно добавить в первый пост
0
1080 / 1007 / 106
Регистрация: 28.02.2010
Сообщений: 2,889
22.09.2011, 08:28 14
Цитата Сообщение от Sudoki Посмотреть сообщение
Забыл как их можно добавить в первый пост
У модератора попросить.
0
Evg
Эксперт CАвтор FAQ
21279 / 8301 / 637
Регистрация: 30.03.2009
Сообщений: 22,659
Записей в блоге: 30
22.09.2011, 08:39 15
Евгений М., по поводу поста #12. Хвостовые символы незачем стирать. Достаточно поставить один единственный нолик и он будет обозначать конец строки. А что идёт после этого - уже пофигу. Считай как просто неиспользуемая в строке память и незачем лишние такты тратить на заполнение их нулями
1
935 / 760 / 299
Регистрация: 09.12.2010
Сообщений: 1,346
Записей в блоге: 1
22.09.2011, 15:54 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;
}
0
Каратель
Эксперт С++
6609 / 4028 / 401
Регистрация: 26.03.2010
Сообщений: 9,273
Записей в блоге: 1
22.09.2011, 20:26 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 тесте не совпало, на остальных не проверял
0
22.09.2011, 20:26
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
22.09.2011, 20:26
Помогаю со студенческими работами здесь

Решение задач
Здравствуйте!Помогите пожалуйста полному нубу с решением задач.А именно:как решить первую?Почему не...

Решение задач
Всем салам! Нам задали 30 задач на c++ кто сможет написать их ? подам 200 рублей на нашем 1000...

решение задач
Помогите решить задачи до завтра. Буду очень признателен. Не разбираюсь совсем в этом.

Решение задач
Всем здравствуйте. Буду благодарна за любую помощь. У меня уже психоз скоро начнется. Вообще я...


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

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

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