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

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

Восстановить пароль Регистрация
 
MihaniX
 Аватар для MihaniX
134 / 44 / 1
Регистрация: 06.08.2013
Сообщений: 292
Записей в блоге: 4
02.02.2014, 21:09     найти ошибку или предложить свое решение #1
Мальчик Вася играет в свою любимую 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++
Пегерузка operator<< или свое универсальное исключение C++
не работет программа или функция, не могу найти ошибку, ругается не неправильные указатели C++
C++ Определить, находится ли координата на "ободе", или за пределами, или внутри круга (найти ошибку)
C++ Найдите ошибку или что я пропустил не могу найти !
C++ Найдите ошибку!Пишет Решение «зависло» на тесте 1
C++ Не могу найти ошибку в функции. Решение СЛАУ методом ортогонализации

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Ответ Создать тему
Опции темы

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