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

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

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 11, средняя оценка - 4.73
Sudoki
124 / 64 / 1
Регистрация: 19.04.2010
Сообщений: 196
#1

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

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

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)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
21.09.2011, 09:29
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Решение задач из Russiancodecup (Первый квалификационный раунд) (C++):

Решение задач - C++
Это снова я, сейчас мне дали задание вот такого типа, опять же согласился ибо выбора не оставалось. Вводится последовательность из N...

решение задач С++ - C++
дано целое число n>0, найти сумму 1 в первой степени + 2 во второй + N в степени N

Решение задач С++ - C++
Вводится последовательность из N целых чисел. Определить наибольшее чисел среди кратных 11.

Решение задач на C++ - C++
Привет, помогите решить задачи (они будут в документе) , очень нужна ваша помощь, так как я неразбираюсь в программировании, но у меня...

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

Решение задач - C++
Доброго времени дня! помогите пожалуйста составить программы по с++ так как я не понимаю программирование совсем! Вот условия задач: ...

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

Не по теме:

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

0
fasked
Эксперт С++
4937 / 2517 / 180
Регистрация: 07.10.2009
Сообщений: 4,311
Записей в блоге: 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
Thinker
Эксперт C++
4226 / 2200 / 150
Регистрация: 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
17826 / 6036 / 388
Регистрация: 30.03.2009
Сообщений: 16,567
Записей в блоге: 26
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
Gepar
1177 / 533 / 20
Регистрация: 01.07.2009
Сообщений: 3,517
21.09.2011, 21:14 #8
Какое условие хитрое, обычная конкатенация строк, а так замудрили.
0
fasked
Эксперт С++
4937 / 2517 / 180
Регистрация: 07.10.2009
Сообщений: 4,311
Записей в блоге: 1
21.09.2011, 21:56 #9
Цитата Сообщение от Evg Посмотреть сообщение
И ещё, вместо конструкций типа
Да само собой многое можно улучшить Но, алгоритмически, разницы не будет. Я хотел показать насколько более простой можно написать алгоритм, чем у ТС. Так как-то мудрено все же...
Однако, я не отмазываюсь, мог сразу написать правильно, но не написал. В следующий раз буду учитывать.

Куда интереснее было бы увидеть алгоритм без дополнительной памяти.
0
Evg
Эксперт CАвтор FAQ
17826 / 6036 / 388
Регистрация: 30.03.2009
Сообщений: 16,567
Записей в блоге: 26
21.09.2011, 23:40 #10
Цитата Сообщение от fasked Посмотреть сообщение
Да само собой многое можно улучшить
Ну тебе-то понятно, но другим не всегда очевидно. В первую очередь для дургих писал особенно для начинающих
1
Mr.X
Эксперт С++
3049 / 1694 / 265
Регистрация: 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
Евгений М.
1035 / 976 / 54
Регистрация: 28.02.2010
Сообщений: 2,829
Завершенные тесты: 2
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
Sudoki
124 / 64 / 1
Регистрация: 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
Евгений М.
1035 / 976 / 54
Регистрация: 28.02.2010
Сообщений: 2,829
Завершенные тесты: 2
22.09.2011, 08:28 #14
Цитата Сообщение от Sudoki Посмотреть сообщение
Забыл как их можно добавить в первый пост
У модератора попросить.
0
Evg
Эксперт CАвтор FAQ
17826 / 6036 / 388
Регистрация: 30.03.2009
Сообщений: 16,567
Записей в блоге: 26
22.09.2011, 08:39 #15
Евгений М., по поводу поста #12. Хвостовые символы незачем стирать. Достаточно поставить один единственный нолик и он будет обозначать конец строки. А что идёт после этого - уже пофигу. Считай как просто неиспользуемая в строке память и незачем лишние такты тратить на заполнение их нулями
1
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
22.09.2011, 08:39
Привет! Вот еще темы с ответами:

Решение задач с Си++ - C++
Код доступа к банковскому счету представляет собой набор из 9 десятичных цифр. При проведении банковских операций онлайн клиента, в целях...

Решение задач С++ - C++
Заданы три точки на плоскости: М с координатами (х1, у1), L с координатами (х2, у2) и Н с координатами (х3, у3). Определить лежат ли они на...

Решение контрольной из 5 задач - C++
Привет!Помогите решить контрольную из 5 задач. . Оплата сдельная. Делать в Microsoft Visual Studio Express Edition

нужна решение задач в с++ - C++
1) Решить задачу. Функция у=2х, если х&gt;0, и у=х+10 в других случиях. 2) Решить задачу. Дан одномерный массив А(К). Определить сумму...


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

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
22.09.2011, 08:39
Ответ Создать тему
Опции темы

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