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

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

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

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

24.01.2013, 13:41. Просмотров 726. Ответов 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;
	}
}
Отлично проходит тестовый пример, но при первом же реальном тесте неверно.
Помогите найти ошибку, может что-то в логике отбора?
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
24.01.2013, 13:41     Задача с olympiads.ru
Посмотрите здесь:

Задача с Olympiads C++

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

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

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

Добавлено через 1 минуту
кроме того при проверке цены, как только она превысит лимит наличности, сразу можно прекратить цикл проверки товаров
lunohod-1
1 / 1 / 0
Регистрация: 14.12.2011
Сообщений: 44
24.01.2013, 16:52  [ТС]     Задача с olympiads.ru #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; //Не хватает или много
    }
}
UserAK
73 / 73 / 4
Регистрация: 25.12.2012
Сообщений: 189
Записей в блоге: 2
24.01.2013, 17:24     Задача с olympiads.ru #6
читал условие и к сожалению не понял может ли он покупать один и тот же товар несколько раз?
lunohod-1
1 / 1 / 0
Регистрация: 14.12.2011
Сообщений: 44
24.01.2013, 17:29  [ТС]     Задача с olympiads.ru #7
Да, упустил. Это действительно странно...
А если это пока пропустить, то отбор кандидатов на проверку суммы, вроде, в порядке?
UserAK
73 / 73 / 4
Регистрация: 25.12.2012
Сообщений: 189
Записей в блоге: 2
24.01.2013, 17:39     Задача с olympiads.ru #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);
    }
};
lunohod-1
1 / 1 / 0
Регистрация: 14.12.2011
Сообщений: 44
24.01.2013, 17:41  [ТС]     Задача с olympiads.ru #9
А мне кажется, что он покупает его один раз, ведь денег у него только 2.
UserAK
73 / 73 / 4
Регистрация: 25.12.2012
Сообщений: 189
Записей в блоге: 2
24.01.2013, 17:47     Задача с olympiads.ru #10
а какой он покупает? я запутался чего-то

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

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

Добавлено через 16 минут
P.S. А разве в третьем плане он покупает не третий товар?
UserAK
73 / 73 / 4
Регистрация: 25.12.2012
Сообщений: 189
Записей в блоге: 2
24.01.2013, 18:27     Задача с olympiads.ru #12
в третьем у него 2 денег, и он может купить 3 и 5 товары
lunohod-1
1 / 1 / 0
Регистрация: 14.12.2011
Сообщений: 44
24.01.2013, 18:47  [ТС]     Задача с olympiads.ru #13
Упс, точно.
valeriikozlov
Эксперт C++
4663 / 2489 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
24.01.2013, 20:22     Задача с olympiads.ru #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;
    }
}
lunohod-1
1 / 1 / 0
Регистрация: 14.12.2011
Сообщений: 44
25.01.2013, 22:42  [ТС]     Задача с olympiads.ru #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 минут
А все же, у меня ошибка в коде или в логике построения кода?
valeriikozlov
Эксперт C++
4663 / 2489 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
26.01.2013, 06:27     Задача с olympiads.ru #16
Цитата Сообщение от lunohod-1 Посмотреть сообщение
А все же, у меня ошибка в коде или в логике построения кода?
и в коде и в логике (см комментарии):
Цитата Сообщение от lunohod-1 Посмотреть сообщение
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
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) {// в массиве a[] записано всего k чисел с индексами от 0 до k-1, поэтому эта строка неправильная
return 1;
}
else {
* * for(b=0;b<=r;b++) {// здесь таже самая ошибка, при b равном r
* * 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;
* * }
}
Вот так проходит все тесты:
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
#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;
bool 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;
}
 
bool tryto(long long a[],int k,int s) {
    bool b[100001]={0};
    int i, j;
    for(i=0; i<r; i++)
    {
        for(j=s; j>0; j--)
            if(b[j] && a[i]+j<=s)
                b[j+a[i]]=true;
        b[a[i]]=true;
    }
    return b[s];
}
lunohod-1
1 / 1 / 0
Регистрация: 14.12.2011
Сообщений: 44
26.01.2013, 20:42  [ТС]     Задача с olympiads.ru #17
Спасибо. Понял, исправил.

Добавлено через 35 минут
Конечно, уже слишком много спрашиваю, но не хватает 70 баллов для более-менее приличного рейтинга
3 задача (про плитку) отлично проходит первую группу тестов, но падает уже на второй...
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
#include <iostream>
double round(double,int); //функция округления
double w,h,a,b,d,e,l,k;
int f,g,sum,n,m;
using namespace std;
 
int main() {
    std::cin>>w>>h;
    std::cin>>a>>b;
    f=w/a; //количество целых в ширину
    g=h/b; //кол-во целых в высоту
    f*=g;  //количество целых
    sum+=f;
    f=w/a;  
    l=w-f*a;//ширина дырки
    f=h/b;
    k=h-f*b;//высота дырки
    if(l<=a/2 && l>0) {
    //режем пополам или больше в ширину
        d=a;
        m=1;
        d-=l;
        while(d>=l) { //режем пока хватает
            d-=l;
            m++;
        }
        sum+=round(h/(b*m),0);
    }
    else {
    if(l>0)
//если не режется
        sum+=h/b;
    }
    
    if(k<=a/2 && k>0) {
//режем в высоту, дальше аналогично
        d=b;
        m=n=1;
        d-=k;
        while(d>=k) {
            d-=k;
            m++;
        }
        sum+=round(w/(a*m),0);
    }
    else {
    if(k>0)
        sum+=round(w/a,0);
    }
//вывод
    std::cout<<sum<<std::endl;
    return 0;
}
 
 
double round(double input, int method) {
method=(method)?method:0;
    switch(method) {
    case 0: return (input-((int)input)>=0.5)?(double)((int)input)+1:(double)(int)input;break;
    case 1: return frac(input>0)?(double)((int)input)+1:(double)(int)input;break;
    case 2: return (double)(int)input;break;
    }
}
valeriikozlov
Эксперт C++
4663 / 2489 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
26.01.2013, 23:25     Задача с olympiads.ru #18
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
#include <iostream>
//double round(double,int); //функция округления
int w,h,a,b,d,e,l,k;
int f,g,sum,n,m;
using namespace std;
 
int main() {
    std::cin>>w>>h;
    std::cin>>a>>b;
    f=w/a; //количество целых в ширину
    g=h/b; //кол-во целых в высоту
    f*=g;  //количество целых
    sum+=f;
    f=w/a;  
    l=w-f*a;//ширина дырки
    f=h/b;
    k=h-f*b;//высота дырки
    int tmp;
    int s1=0, s2=0;
    if(l!=0)
    {
        tmp=(a/l)*b;
        s1+=h/tmp;
        if(h%tmp)
            s1++;
    }
    if(k!=0)
    {
        tmp=(b/k)*a;
        s1+=(w-l)/tmp;
        if((w-l)%tmp)
            s1++;
    }
    if(k!=0)
    {
        tmp=(b/k)*a;
        s2+=w/tmp;
        if(w%tmp)
            s2++;
    }
    if(l!=0)
    {
        tmp=(a/l)*b;
        s2+=(h-k)/tmp;
        if((h-k)%tmp)
            s2++;
    }
    if(s2<s1)
        sum+=s2;
    else
        sum+=s1;
//вывод
    std::cout<<sum<<std::endl;
    return 0;
}
Yandex
Объявления
26.01.2013, 23:25     Задача с olympiads.ru
Ответ Создать тему
Опции темы

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