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

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

Войти
Регистрация
Восстановить пароль
 
MihaniX
134 / 44 / 1
Регистрация: 06.08.2013
Сообщений: 292
Записей в блоге: 4
#1

найти ошибку или предложить свое решение - C++

02.02.2014, 21:09. Просмотров 380. Ответов 0
Метки нет (Все метки)

Мальчик Вася играет в свою любимую RPG. Он нашел сундук с M ячейками, в каждой из которых лежит по одной бутылке с зельем лечения. У его героя на поясе есть N карманов, в каждом из которых также лежит по одной бутылке. Каждая бутылка восстанавливает фиксированное число очков здоровья.

Вася хочет заменить часть бутылок, находящихся в кармане на поясе, бутылками из сундука так, чтобы суммарное количество очков здоровья, восстанавливаемых бутылками, которые окажутся на поясе после этого, было максимальным. Ему доступна одна операция: поменять бутылку из указанного кармана пояса с бутылкой из указанной ячейки сундука.

Вам нужно указать последовательность операций, после которой суммарный запас очков здоровья у Васи на поясе будет максимальный.

Формат входных данных
Сначала вводятся N, M (1 ≤ N ≤ 1000, 1 ≤ M ≤ 1000). Далее идут N чисел, причём i-е равно количеству очков здоровья, восстанавливаемых бутылкой из i-го кармана пояса. Далее – M чисел, j-е из которых равно количеству очков здоровья, восстанавливаемых бутылкой из j-й ячейки сундука. Все очки – натуральные числа, не превосходящие 10000.

Формат выходных данных
Вначале выведите K – количество операций обмена. Оно не должно превышать 100000. Далее выведите K пар чисел, описывающих, какие бутылки нужно поменять: первое из чисел от 1 до N – задает номер кармана на поясе, второе – от 1 до M – номер ячейки в сундуке. Если существует более одного варианта, выведите любой.


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
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
#include <iostream>
#include <vector>
 
using namespace std;
 
struct bottle
{
public:
    bottle(long long, long long);
    long long hp;
    long long num;
};
 
bottle::bottle(long long a, long long b)
{
    bottle::hp=a;
    bottle::num=b;
}
 
void sort1(vector<bottle> w)
{
    long long j=w.size();
 
    while (j>1)
    {
        for (long long i=0; i<(j-1); i++)
        {
            if (w[i].hp>w[i+1].hp)
            {
                w[i], w[i+1]=w[i+1], w[i];
            }
        }
        j--;
    }
    return;
}
 
 
void sort2(vector<bottle> w)
{
    long long j=w.size();
 
    while (j>1)
    {
        for (long long i=0; i<(j-1); i++)
        {
            if (w[i].hp<w[i+1].hp)
            {
                w[i], w[i+1]=w[i+1], w[i];
            }
        }
        j--;
    }
 
    return;
}
 
vector<bottle> a, b;
long long n, m;
 
void input()
{
    long long tmp;
    bottle qwe=bottle(0, 0);
    cin>>n>>m;
 
    for (long long  i=0; i<n; i++)
    {
        cin>>tmp;
        qwe=bottle(tmp, i+1);
        a.push_back(qwe);
    }
    sort1(a);
 
    for (long long i=0; i<m; i++)
    {
        cin>>tmp;
        qwe=bottle(tmp, i+1);
        b.push_back(qwe);
    }
    sort2(b);
 
    return;
}
 
vector< vector<long long> > result;
long long counter;
 
void solve(vector<bottle> a, vector<bottle> b)
{
    long long x=a.size(); if(a.size()<b.size()){x=b.size();}
    long long counter;
    vector<long long> v;
    v.push_back(0); v.push_back(0);
    for (long long i=0; i<x; i++)
    {
        if (a[i].hp<b[i].hp)
        {
            counter++;
            vector<long long> v;
            v[0], v[1]=a[i].num, b[i].num;
            result.push_back(v);
        }
        else{break;}
    }
    return;
}
 
int main()
{
    input();
    solve(a, b);
 
    for(long long i=0; i<a.size(); i++)
    {
        cout<<a[i].hp<<" ";
    }
    cout<<endl;
    for(long long i=0; i<b.size(); i++)
    {
        cout<<b[i].hp<<" ";
    }
    cout<<endl;
 
    cout<<counter;
    for (long long i=0; i<result.size(); i++)
    {
        cout<<result[i][0]<<" "<<result[i][1]<<endl;
    }
 
    return 0;
}
не работает....

а вот код на питоне, который работает но ему не хватает времени (13 миллисекунд)

Python
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
class bottle:
    def __init__(self, hp, num):
        self.num=num
        self.hp=hp
 
def sort1(w): 
    j = len(w)
    while j > 1:
        for i in range(j-1):
            if w[i].hp > w[i+1].hp:              
                tmpw = w[i]
                w[i] = w[i+1]
                w[i+1] = tmpw
        j -= 1
def sort2(w): 
    j = len(w)
    while j > 1:
        for i in range(j-1):
            if w[i].hp < w[i+1].hp:              
                tmpw = w[i]
                w[i] = w[i+1]
                w[i+1] = tmpw
        j -= 1
 
x=input().split()
n, m=int(x[0]), int(x[1])
a=input().split()
for i in range(n):
    a[i]=bottle(int(a[i]), i+1)
sort1(a)
b=input().split()
for i in range(m):
    b[i]=bottle(int(b[i]), i+1)
sort2(b)
result=[]
count=0
 
for i in range(min(len(a), len(b))):
    if a[i].hp<b[i].hp:
        count+=1
        result.append(str(a[i].num)+' '+str(b[i].num))
    else:
        break
print(count)
for i in range(len(result)):
    print(result[i])
Помогите, пожалуйста:
либо оптимизировать код питона,
либо найти ошибку в коде С++
либо написать свой вариант

буду благодарен

Добавлено через 5 минут
УУУуууух. Разобрался. Когда я отправлял код, сервер лагал и медленно работал. Я второй раз отправил тот же код на питоне и он сработал. Статус ОК
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
02.02.2014, 21:09
Здравствуйте! Я подобрал для вас темы с ответами на вопрос найти ошибку или предложить свое решение (C++):

Не могу найти ошибку в функции. Решение СЛАУ методом ортогонализации - C++
Дана СЛАУ, а точнее, матрица A и вектор f. Надо найти решения СЛАУ методом ортогонализации. Вот, собственно, сам алгоритм метода. ...

Определить, находится ли координата на "ободе", или за пределами, или внутри круга (найти ошибку) - C++
Задача: пользователь вводит радиус круга и координату точки (х,у). Нужно определить находиться ли координата на &quot;ободе&quot; круга или за...

Пегерузка operator<< или свое универсальное исключение - C++
Пытаюсь создать свой класс исключений: class YacException : public exception { private: tLog log; int messageLevel; ...

найти ошибку(запятые или скобки) - C++
Где-то намикимаусил, не вижу где)) #include&lt;iostream.h&gt; main() { int i,j=1; cout&lt;&lt;&quot;2\t3\t5\t7\t11\t13\t17\t23\t29\t31\n&quot;; ...

Помогите найти ошибку или переписать программу! - C++
Здравствуйте! Никак не могу справиться с одной задачей. Я и несколько одногруппников &quot;прокрутили в голове&quot; саму задачу и все говорят, что...

Нужно найти библиотеку или готовое решение - C++
Доброе время суток. Подскажите, пожалуйста, библиотеку под C/C++, которая умеет работать с математическими выражениями и преобразовывать...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
02.02.2014, 21:09
Привет! Вот еще темы с ответами:

Найдите ошибку или что я пропустил не могу найти ! - C++
void SortBubble(int ar, int n) { int temp; for(int i=0 ; i&lt;n-2 ; i++) { for(int j=0 ; j &lt; n-1 ; j++) { if(ar&gt;ar) ...

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

Найти ошибку в программе: в visual studio выдает ошибку - C++
#include &lt;math.h&gt; #include &lt;conio.h&gt; #include &lt;iostream&gt; using namespace std; int main() { double x, E, ypred, y, S; ...

Найдите ошибку!Пишет Решение «зависло» на тесте 1 - C++
Решил я порешать задачи на codefoces. Начал с 1A :http://codeforces.ru/problemset/problem/1/A #include &lt;iostream&gt; #include &lt;conio.h&gt; ...


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

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

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