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

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

Войти
Регистрация
Восстановить пароль
 
 
lunohod-1
1 / 1 / 0
Регистрация: 14.12.2011
Сообщений: 44
#1

Задача с olympiads.ru - C++

24.01.2013, 13:41. Просмотров 790. Ответов 17
Метки нет (Все метки)

Всем привет.
Столкнулся с проблемой при решении задачи E "Распродажа" с сайла olympiads.ru (http://olympiads.ru/zaoch/2012-13/problems/index.shtml)

Написал код:
Код
#include <iostream>
#include <algorithm>
int n,i,j,r;
unsigned int c[501];
long long a[501],b[501];
unsigned long M;
long long m[500001],k[500001],s[500001],t[500001];
using namespace std;
int tryto(long long a[],int r,int sum);
int main() {
cin>>n;
for(i=1;i<=n;i++) {
	cin>>c[i]>>a[i]>>b[i];
}
cin>>M;
for(i=1;i<=M;i++) {
cin>>m[i]>>k[i]>>s[i];
}
long v;
r=0;
for(i=1;i<=M;i++) {
	for(j=1;j<=n;j++) {
		if((m[i]>=a[j]) && (m[i]+s[i]<0 || m[i]+s[i]+1<=b[j]) && (k[i]>=c[j])) {
				t[r]=c[j];
				r++;
			}
			}
		if(tryto(t,r,k[i])==1 && t[0]>0) {
		cout<<"YES"<<endl;
		}
		else { cout<<"NO"<<endl; 
		}
		for(v=0;v<r;v++) { t[v]=0; }
		r=0;
}
return 0;
}

int tryto(long long a[],int k,int s) {
long sum,b,c,d,e,r;
sum=b=0;
std::sort(a,a+k);
int i=0;
while(a[i]<=s && i<=k) {
i++;
}
r=i;
if(a[i]==s) {
return 1;
}
else if(a[0]>s) {
return 0;
}
else {
	for(b=0;b<=r;b++) {
	sum=a[b];
		for(c=b;c<=r;c++) {
		if(c!=b) {
			if(a[b]+a[c]<=s) { sum+=a[c]; }
		}
		}
		if(sum==s) { return 1; }
	}
	return 0;
	}
}
Отлично проходит тестовый пример, но при первом же реальном тесте неверно.
Помогите найти ошибку, может что-то в логике отбора?
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
24.01.2013, 13:41
Я подобрал для вас темы с готовыми решениями и ответами на вопрос Задача с olympiads.ru (C++):

Задача с Olympiads - C++
Вроде работает, но на половине тестов срезается... Условие: В столице одной небольшой страны очень сложная ситуация. Многокилометровые...

Задача: В некотором государстве ввели компьютерный паспорт гражданина.(задача) - Pascal
Доброго времени суток,форумчане. Хотелось бы попросить помощи в решении одной задачи от умных голов. Задача: В некотором...

Задача на k-тую цифру последовательности, задача на схему Горнера. - Pascal
Ну, собственно опять прошу помощи... Задача 1: Определить k-тую цифру последовательности 1234567891011121314…, в которой выписаны подряд...

Задача на перебор вариантов. Задача Л.Эйлера. Про чиновника - PascalABC.NET
Задача Л.Эйлера. Некий чиновник купил лошадей и быков на сумму 1770 талеров. За каждую лошадь он уплатил по 31 талеру, а за каждого быка по...

Первая смешанная задача для волнового уравнения на отрезке (задача о колебаниях ограниченной струны) методом Фурье - Дифференциальные уравнения
Решить первую смешанную задачу для волнового уравнения на отрезке (задача о колебаниях ограниченной струны) методом Фурье ...

Задача о размещении весов по ящикам (задача о рюкзаках) - Delphi
Есть упорядоченный по невозрастанию набор весов предметов w1..wn, которые необходимо распределить по ящикам способным выдержать вес V,...

17
UserAK
73 / 73 / 4
Регистрация: 25.12.2012
Сообщений: 189
Записей в блоге: 2
24.01.2013, 16:05 #2
Вы бы сразу в машинном коде выложили Ну ничего же не понятно, мозг взрывается где-то посередине функции с загадочным названием tryto
0
lunohod-1
1 / 1 / 0
Регистрация: 14.12.2011
Сообщений: 44
24.01.2013, 16:20  [ТС] #3
Функция пытается составить число k[i] (деньги Кеши) из цен всех доступных ему товаров. Если ей удается, то возвращает 1 и 0, если ему не удастся выполнить свой план.
0
UserAK
73 / 73 / 4
Регистрация: 25.12.2012
Сообщений: 189
Записей в блоге: 2
24.01.2013, 16:49 #4
можно отсортировать список товаров по цене сразу после ввода, и потом не надо будет каждый раз сортировать цены

Добавлено через 3 минуты
надеюсь структуры то создавать можно для задания

Добавлено через 1 минуту
кроме того при проверке цены, как только она превысит лимит наличности, сразу можно прекратить цикл проверки товаров
0
lunohod-1
1 / 1 / 0
Регистрация: 14.12.2011
Сообщений: 44
24.01.2013, 16:52  [ТС] #5
Чуть измененный и оптимизированный вариант функции:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int tryto(long long a[],int k,int s) {
//a-массив с ценами, k-размер массива, s-нужная сумма
long sum,b,c,r;
sum=b=0;
std::sort(a,a+k);  //сортируем полученный массив
r=k;  
if(a[k]==s) { //если самый большой элемент равен s, сразу же возвращаем 1
return 1;
}
else {
    for(b=0;b<=r;b++) {  //берем первую цифру для сравнения
    sum=a[b];  //ставим ее первой в сумму
        for(c=1;c<=r;c++) {  //перебираем все варианты сумм.
        if(c!=b) { //элементы можно брать только один раз
            if(a[b]+a[c]<=s) { sum+=a[c]; }  //если это меньше наличности, берем
        }
        if(sum==s) { return 1; }  //Ура, хватило!:)
        }
    }
    return 0; //Не хватает или много
    }
}
0
UserAK
73 / 73 / 4
Регистрация: 25.12.2012
Сообщений: 189
Записей в блоге: 2
24.01.2013, 17:24 #6
читал условие и к сожалению не понял может ли он покупать один и тот же товар несколько раз?
0
lunohod-1
1 / 1 / 0
Регистрация: 14.12.2011
Сообщений: 44
24.01.2013, 17:29  [ТС] #7
Да, упустил. Это действительно странно...
А если это пока пропустить, то отбор кандидатов на проверку суммы, вроде, в порядке?
0
UserAK
73 / 73 / 4
Регистрация: 25.12.2012
Сообщений: 189
Записей в блоге: 2
24.01.2013, 17:39 #8
а вот понял. в третьем плане он покупает 3 раза третий товар
5
6 2 7
5 4 9
1 2 4
2 5 8
1 3 9
5
2 7 1
2 7 2
3 2 0
5 7 2
4 1 5

YES
NO
YES
YES
NO

Добавлено через 5 минут
я создал две структуры и всё туда поместил вот структуры "товар" и "поход за покупками"
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
struct SGoods{
    unsigned Price; // от 1 до 1 000
    unsigned TimeIn; // от 1 до 10^9
    unsigned TimeOut; // от больше TimeIn до 10^9
    SGoods(const unsigned &price, const unsigned &timein, const unsigned &timeout)
        : Price(price), TimeIn(timein), TimeOut(timeout) {}
};
 
struct STrip{
    unsigned TimeIn; // от 1 до 10^9
    unsigned Cash; // от 1 до 100 000
    unsigned Duration; // от 0 до 10^9
    STrip(){}
    bool TooExpensive(const SGoods &g){
        // денег не хватает на покупку этого товара
        return ( Cash < g.Price );
    }
    bool HasTimeToBuy(const SGoods &g){
        // товар в магазине на протяжении всего срока пребывания покупателя
        return ( TimeIn >= g.TimeIn && (TimeIn + Duration) <= g.TimeOut);
    }
};
0
lunohod-1
1 / 1 / 0
Регистрация: 14.12.2011
Сообщений: 44
24.01.2013, 17:41  [ТС] #9
А мне кажется, что он покупает его один раз, ведь денег у него только 2.
0
UserAK
73 / 73 / 4
Регистрация: 25.12.2012
Сообщений: 189
Записей в блоге: 2
24.01.2013, 17:47 #10
а какой он покупает? я запутался чего-то

Добавлено через 49 секунд
последний 2 раза?

Добавлено через 1 минуту
а вот 3 и 5 он покупает
0
lunohod-1
1 / 1 / 0
Регистрация: 14.12.2011
Сообщений: 44
24.01.2013, 18:09  [ТС] #11
Ну тогда перебором, как я предполагал, лучше не делать и поискать другие способы?

Добавлено через 16 минут
P.S. А разве в третьем плане он покупает не третий товар?
0
UserAK
73 / 73 / 4
Регистрация: 25.12.2012
Сообщений: 189
Записей в блоге: 2
24.01.2013, 18:27 #12
в третьем у него 2 денег, и он может купить 3 и 5 товары
0
lunohod-1
1 / 1 / 0
Регистрация: 14.12.2011
Сообщений: 44
24.01.2013, 18:47  [ТС] #13
Упс, точно.
0
valeriikozlov
Эксперт С++
4681 / 2507 / 322
Регистрация: 18.08.2009
Сообщений: 4,550
24.01.2013, 20:22 #14
См комментарии:
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
#include <iostream>
#include <algorithm>
int n,i,j,r;
unsigned int c[501];
long long a[501],b[501];
unsigned long M;
long long m[500001],k[500001],s[500001],t[500001];
using namespace std;
int tryto(long long a[],int r,int sum);
int main() {
cin>>n;
for(i=1;i<=n;i++) {
    cin>>c[i]>>a[i]>>b[i];
}
cin>>M;
for(i=1;i<=M;i++) {
cin>>m[i]>>k[i]>>s[i];
}
long v;
r=0;
for(i=1;i<=M;i++) {
    for(j=1;j<=n;j++) {
        if((m[i]>=a[j]) && (m[i]+s[i]<0 || m[i]+s[i]+1<=b[j]) && (k[i]>=c[j])) {// вот здесь запоминаем условие что k[i]>=c[j]
                t[r]=c[j];// т.е. в массив t[] попадают все цены, меньше или равные k[i]
                r++;
            }
            }
        if(tryto(t,r,k[i])==1 && t[0]>0) {// итак, в фунцкцию tryto() мы посылаем массив t[] в котором r чисел (с индексами от 0 до r-1), значения которых меньше или равно k[i]. Теперь отправляемся в саму функцию tryto()
        cout<<"YES"<<endl;
        }
        else { cout<<"NO"<<endl; 
        }
        for(v=0;v<r;v++) { t[v]=0; }
        r=0;
}
return 0;
}
 
int tryto(long long a[],int k,int s) {// здесь имеем массив a[] (со значения по индексам от 0 до k-1), значения которых меньше или равно s.
long sum,b,c,d,e,r;
sum=b=0;
std::sort(a,a+k);
int i=0;
while(a[i]<=s && i<=k) {// вот в этом цикле i вырастет до значения k+1 (к гадалке не ходи). Уже при i==k идет обращение неизвестно к какому элементу в массиве a[].
i++;
}
r=i;// r тоже станет значением k+1
if(a[i]==s) {// в элементе a[k+1] неизвестно что записано (и может быть даже выход за границы массива a[])
return 1;
}
else if(a[0]>s) {// в a[] записывались элементы меньшие или равные s, поэтому очень странное условие
return 0;
}
else {
    for(b=0;b<=r;b++) {// на этой строчке пиво заканчивается, но уже и так достаточно написал. Еще раз пересмотрите код. Задача решаема (довольно очень простая), скорее всего даже если исправите ошибки, по времени не пройдет. Пробуйте сдавать, что получится показывайте )
    sum=a[b];
        for(c=b;c<=r;c++) {
        if(c!=b) {
            if(a[b]+a[c]<=s) { sum+=a[c]; }
        }
        }
        if(sum==s) { return 1; }
    }
    return 0;
    }
}
0
lunohod-1
1 / 1 / 0
Регистрация: 14.12.2011
Сообщений: 44
25.01.2013, 22:42  [ТС] #15
Код чуть изменил, н всё равно не проходит
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
#include <iostream>
#include <algorithm>
int n,i,j,r;
unsigned int c[501];
long long a[501],b[501];
unsigned long M;
long long m[500001],k[500001],s[500001],t[500001];
using namespace std;
int tryto(long long a[],int r,int sum);
int main() {
cin>>n;
for(i=1;i<=n;i++) {
    cin>>c[i]>>a[i]>>b[i];
}
cin>>M;
for(i=1;i<=M;i++) {
cin>>m[i]>>k[i]>>s[i];
}
long v;
r=0;
for(i=1;i<=M;i++) {
    for(j=1;j<=n;j++) {
        if((m[i]>=a[j]) && (m[i]+s[i]<0 || m[i]+s[i]+1<=b[j]) && (k[i]>=c[j])) {
                t[r]=c[j];
                r++;
            }
            }
        if(tryto(t,r,k[i])==1 && t[0]>0) {
        cout<<"YES"<<endl;
        }
        else { cout<<"NO"<<endl; 
        }
        for(v=0;v<r;v++) { t[v]=0; }
        r=0;
}
return 0;
}
 
int tryto(long long a[],int k,int s) {
long sum,b,c,r;
sum=b=0;
std::sort(a,a+k);
r=k;
if(a[k]==s) {
return 1;
}
else {
    for(b=0;b<=r;b++) {
    sum=a[b];
        for(c=1;c<=r;c++) {
        if(c!=b) {
            if(a[b]+a[c]<=s) { sum+=a[c]; }
        }
        if(sum==s) { return 1; }
        }
    }
    return 0;
    }
}
Добавлено через 6 часов 47 минут
А все же, у меня ошибка в коде или в логике построения кода?
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
25.01.2013, 22:42
Привет! Вот еще темы с ответами:

Задача Дам или задача Восьми - Алгоритмы
помогите найти ошибку в алгоритме. не находит ответ подозреваю ошибку в k, i, j package com.company; import java.util.Arrays;...

Задача на файл и задача на создание очереди - Pascal
1 Дан символьный файл, содержащий, по крайней мере, один символ пробела. Удалить из файла все символы, предшествующие пробелу 2 ...

Задача линейного программирования, транспортная задача - Методы оптимизации
Всем привет. сижу на экзамене, помогите пожалуйста решить,сроно!!! заранее спасибо.

задача Коши и краевая задача - Matlab
Помогите кто чем может))


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

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

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