1 Тема від aassii

  • aassii
  • Користувач
  • Поза форумом
  • Дата реєстрації: 09.01.2019
  • Повідомлень: 27
    • Репутація: 8

Тема: Пограбування магазину: знайди помилку - не проходить всі тести

Пiд час порабування магазину злодiй виявив N ящичкiв iз золотим пiском. У ящичку пiд номером i пiсок має вартiсть Vi i вагу Wi. Щоб винести награбоване, злодiй використовує рюкзак. Потрiбно визначити найбiльшу сумарну вартiсть пiска, який може винести грабiжник, якщо вантажомiсткiсть рюкзака обмежена величиною W. Iз ящичкiв можна пересипати довiльну кiлькiсть пiска, тодi вiдношення вартостi вiдсипаного пiска до вартостi усього ящика буде дорiвнювати вiдношенню об’єма вiдсипаного пiска до об’єма
усього ящика.
Не проходить всі тести:

▼Прихований текст

====== Test =======
--- Input: size 14 ---
1 1000
500 30

--- Output: size 20 ---
500.000000000000057

--- Correct: size 20 ---
500.000000000000000

--- Stderr: size 0 ---

--- Checker output: size 77 ---
Line 1 differs: output:
>500.000000000000057<
correct:
>500.000000000000000<

▼Прихований текст

====== Test  =======
--- Input: size 12 ---
1 10
500 30

--- Output: size 20 ---
166.666666666666686

--- Correct: size 20 ---
166.666666666667000

--- Stderr: size 0 ---

--- Checker output: size 77 ---
Line 1 differs: output:
>166.666666666666686<
correct:
>166.666666666667000<


▼Прихований текст

====== Test #6 =======
--- Input: size 57 ---
5 9022
1717 8427
2852 6912
5375 8940
3316 1601
3336 9926

--- Output: size 21 ---
7777.730984340044415

--- Correct: size 21 ---
7777.730984340040000

--- Stderr: size 0 ---

--- Checker output: size 79 ---
Line 1 differs: output:
>7777.730984340044415<
correct:
>7777.730984340040000<

Програма:

▼Прихований текст
#include <iostream>
#include <vector>
#include <algorithm>
#include <iomanip>
using namespace std;
vector<pair<double, double>> vect;
int main()
{
    int i,n;
    double w,vi,wi,res;
    cin>>n>>w;
    for(i=0; i<n; i++)
    {
        cin>>vi>>wi;
        vect.push_back(make_pair(vi/wi, wi));
    }
    sort(vect.begin(),vect.end());
    reverse(vect.begin(),vect.end());
    for(i=0; i<vect.size(); i++)
    {
        res += min(w, vect[i].second)*vect[i].first;
        w -= min(w, vect[i].second);
    }
    cout<<fixed<<setprecision(15)<<res<<endl;
    return 0;
}
Подякували: varkon, HetmanNet2

2 Відповідь від aassii

  • aassii
  • Користувач
  • Поза форумом
  • Дата реєстрації: 09.01.2019
  • Повідомлень: 27
    • Репутація: 8

Re: Пограбування магазину: знайди помилку - не проходить всі тести

Тему закрито - помилка в тестах.
(Тему можна видалити).

3 Відповідь від koala Востаннє редагувалося koala (09.02.2019 21:48:05)

  • koala
  • koala
  • Лінива тваринка
  • Поза форумом
  • Дата реєстрації: 01.05.2013
  • Повідомлень: 15 621
    • Репутація: 13334

Re: Пограбування магазину: знайди помилку - не проходить всі тести

Авторам таких "тестів" хочеться відірвати руки. Похибка в 13-му знаку.
Можете спробувати підвищити точність, не ділячи елементи без потреби - або зберігайте трійку (vi/wi, wi, vi) і не домножуйте дріб, а використовуйте збережений vi; або сортуйте пари (vi,wi) за допомогою спеціальної функції-порівняння, це, загалом, найправильніший спосіб тут.
Можу ще запропонувати оригінальніший спосіб - визначити власний тип "дріб" (чи використати boost/rational.hpp) і зберігати дроби в такий спосіб.
Але, ще раз, у вашому коді особливих проблем немає (якщо немає вимог надмірної точності), проблеми у тестах.

(коли я починав писати цю відповідь, ще не було уточнення від автора про помилку в тестах)

Подякували: leofun01, aassii2

koala вебсайт

4 Відповідь від koala

  • koala
  • koala
  • Лінива тваринка
  • Поза форумом
  • Дата реєстрації: 01.05.2013
  • Повідомлень: 15 621
    • Репутація: 13334

Re: Пограбування магазину: знайди помилку - не проходить всі тести

Спроба виправлення №1:

#include <iostream>
#include <vector>
#include <algorithm>
#include <iomanip>
using namespace std;
vector<pair<double, double>> vect;
int main()
{
    int i,n;
    double w,vi,wi,res;
    cin>>n>>w;
    for(i=0; i<n; i++)
    {
        cin>>vi>>wi;
        vect.push_back(make_pair(vi, wi));
    }
    sort(vect.begin(),vect.end(), [](auto x, auto y){return x.first*y.second < y.first*x.second;});
    reverse(vect.begin(),vect.end());
    for(i=0; i<vect.size(); i++)
    {
        if(w>=vect[i].second){
            res += vect[i].first;
            w -= vect[i].second;
        } else {
            res += w*vect[i].first/vect[i].second;
            break;
        }
    }
    cout<<fixed<<setprecision(15)<<res<<endl;
    return 0;
}

Тести проходить, але мені не подобається стиль.

Подякували: NaharD, aassii2

koala вебсайт

5 Відповідь від aassii

  • aassii
  • Користувач
  • Поза форумом
  • Дата реєстрації: 09.01.2019
  • Повідомлень: 27
    • Репутація: 8

Re: Пограбування магазину: знайди помилку - не проходить всі тести

Тести проходить

Проходить тільки перший тест, а два останніх - ні.

Бачу використовуєте компаратор (вказівник на функцію) для сортування зі встроєною функцією:
sort(vect.begin(),vect.end(), [](auto x, auto y){return x.first*y.second < y.first*x.second;});
[] - це називається лямбда-вираз - встроєна безіменна локальна функція, у вигляді якої записаний компаратор сортування?
Цікаво, а як правильно записати цей компаратор для сортування через окрему функцію?
Наприклад:

bool Fab(const int a, const int b)
{
    return a > b;
}
...
int a[10];
sort(a, a + 10, Fab);

6 Відповідь від koala

  • koala
  • koala
  • Лінива тваринка
  • Поза форумом
  • Дата реєстрації: 01.05.2013
  • Повідомлень: 15 621
    • Репутація: 13334

Re: Пограбування магазину: знайди помилку - не проходить всі тести

Ну так же й записати, тільки типи доведеться повністю вказувати:

bool cmp(pair<double, double> x, pair<double, double> y)
{
    return x.first*y.second < y.first*x.second;
}
...
std::sort(vect.begin(), vect.end(), &cmp);
Подякували: aassii1

koala вебсайт