Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
MihaniX
137 / 47 / 2
Регистрация: 06.08.2013
Сообщений: 292
Записей в блоге: 4
1

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

02.02.2014, 21:09. Просмотров 501. Ответов 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 минут
УУУуууух. Разобрался. Когда я отправлял код, сервер лагал и медленно работал. Я второй раз отправил тот же код на питоне и он сработал. Статус ОК
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
02.02.2014, 21:09
Ответы с готовыми решениями:

TreeView где найти событие Scroll или как написать свое
Никак немогу найти у treeView событие Scroll или чтолибо подобное. В инете ничего толком так и не...

Найти общее решение или частное решение уравнения первого порядка
Помогите решить: 2*x*sqrt(1-y^2)=y' * (1+x^2). Я не понимаю как решить это, т.к. dx и dy получаются...

Найти общее решение или решение задачи Коши
вот пример:

Найти ошибку (решение уравнения)
Очень давно не использовал matlab, а теперь нужно решить уравнение, ткните носом пожалуйста где...

Решение квадратного уравнения (найти ошибку)
float discr( float a,float b,float c); float findx(float b, float a, float c); int main() { ...

0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
02.02.2014, 21:09

найти обще решение (общий интеграл) или частное решение( частный интеграл) дифференциального уравнения
xy'-y=x*tg(y/x)

найти обще решение (общий интеграл) или частное решение( частный интеграл) дифференциального уравнения
xy'+y+xe^((-x)^2)=0; y(1)=1/2e

Решение задачи Коши. Ode45. Найти ошибку
Надо решить задачу y''+4y=4/sin(2x) y(pi/4)=2 y'(pi/4)=pi и построить график, проблема в том,...


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

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

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