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

Простая задача? - C++

Восстановить пароль Регистрация
 
iama
 Аватар для iama
1249 / 974 / 48
Регистрация: 30.07.2010
Сообщений: 5,297
24.08.2011, 15:42     Простая задача? #1
Здравствуйте! После участия в ДЛКШ я понял, что очень много не знаю даже о самых элементарных вещах в Си\Си++. Например, обыкновенная простая задача на теорию вероятностей -
полное условие под катом.
Цветные шары

В урне находится n шаров, каждый из которых имеет один из k цветов, причём количество шаров каждого цвета, как и сам цвет, известно и написано на отдельной табличке. Дима, начавший изучать теорию вероятности, решил подшутить над своими товарищами и пользуясь случаем, незаметно от остальных заменил все шары какого-то непонравившегося ему цвета шарами совсем других цветов, каждый из которых в надписях на табличках отсутствует, а саму табличку спрятал.

Теперь каждому, кто заходит в аудиторию, он задаёт один и тот же вопрос:

- А скажите-ка мне, с какой вероятностью Вы достанете из урны шар с цветом, не указанным на табличках?

Ваше задание состоит в том, чтобы написать программу, быстро отвечающую на Димины вопросы.

Технические условия

Входные данные

В первой строке задано количество товарищей m (1 ≤ m ≤ 1000), которым Дима задал свой вопрос. Каждая из последующих 2m строк имеет следующую структуру: в первой из них задано два числа n и k (1 ≤ kn ≤ 10000), а во второй k-1 число, разделённое пробелами - количество шаров очередного известного цвета, написанное на табличке.

Выходные данные

В каждой из m строк должен содержаться ответ к Диминой задачке, выведенный с точностью 5 знаков после запятой.

Информация о задаче
Лимит времени: 1 секунда
Лимит памяти: 64 MB
Баллы за пройденный тест: 9.09091
Сложность: 44% 5/9

Пример входных данных
2
10 3
5 3
10 3
3 2

Пример выходных данных
0.20000
0.50000
Для тех, кто не хочет читать - правильное решение сводится к тому, чтобы вывести 1 - s / n, с точностью 5 знаков после запятой - проверено. Я пишу стандартное решение на плюсах:
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
#include <iostream>
 
using namespace std;
 
int main()
{
    int t, q, n, k, s, a, i;
 
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
 
    scanf("%d", &t);
 
    for (q = 0; q < t; q++)
    {
        s = 0;
        scanf("%d %d", &n, &k);
 
        for (i = 0; i < k - 1; i++)
        {
            scanf("%d", &a);
            s += a;
        }
 
        printf("%.5f\n", 1. - double(s) / double(n));
    }
 
    return 0;
}
Не проходит один тест (на сайте стоит Microsoft (R) 32-bit C/C++ Optimizing Compiler Version 15.00.30729.01 for 80x86). Исследую тесты, вычитываю задание, делаю еще 25 отправок с разными модификациями этого решения - этот тест ни один вариант не прошел. Попробовал - чем черт не шутит - переписать на паскаль - вдруг пройдет (компилятор на сайте - dcc (Borland Delphi for Windows) 15.0)
Delphi
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
{$APPTYPE CONSOLE}
 
 uses
  SysUtils;
 var
  t, q, n, k, s, a, i: longint;
 
 begin
  readln(t);
 
  for q := 0 to t - 1 do begin
    s := 0;
        read(n, k);
 
        for i := 0 to k - 2 do begin
      read(a);
      s := s + a;
    end;
 
    writeln(1 - s / n :5:5);
  end;
 
 end.
И таки прошло. Администратор сайта говорит, ошибка в реализации (на Си++). Не подскажите, где же ошибка? Если я ошибся разделом - переместите, пожалуйста если подскажете, есть похожая проблема, на том же сайте такая же элементарная задача не сдается, если использовать потоки в стиле Си++, но если использовать ввод-вывод в стиле Си - прекрасно проходит.

Еще буду очень благодарен за литературу, где можно повычитывать подобные нюансы
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
24.08.2011, 15:42     Простая задача?
Посмотрите здесь:

C++ Простая задача.
простая задача C++
Простая задача C++
Простая задача с массивами C++
C++ Простая задача
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Kastaneda
Модератор
Эксперт С++
 Аватар для Kastaneda
4236 / 2769 / 218
Регистрация: 12.12.2009
Сообщений: 7,104
Записей в блоге: 1
Завершенные тесты: 1
24.08.2011, 15:52     Простая задача? #2
iama, так freopen(), scanf() и printf() находятся в <stdio.h>.
Некоторые компиляторы не требуют его подключения, но все таки если говорить о правильности кода, то stdio.h (cstdio) конечно же нужен!

Добавлено через 3 минуты
Цитата Сообщение от iama Посмотреть сообщение
Я пишу стандартное решение на плюсах:
Я вот не понял - это код, который проходит, или который не проходит? Т.к. решение вобщем-то написанно на С
iama
 Аватар для iama
1249 / 974 / 48
Регистрация: 30.07.2010
Сообщений: 5,297
24.08.2011, 15:57  [ТС]     Простая задача? #3
Kastaneda, тот код на сях проходит все тесты, кроме одного, судя по всему, компилятор свежий, у меня в VC++ 2010 тоже не нужно cstdio подключать.

Добавлено через 2 минуты
Переписал с cstdio и stdio.h Не проходит тот же тест - все остальные - "Засчитано"
Deviaphan
Делаю внезапно и красиво
Эксперт C++
 Аватар для Deviaphan
1283 / 1217 / 50
Регистрация: 22.03.2011
Сообщений: 3,744
24.08.2011, 16:01     Простая задача? #4
Цитата Сообщение от iama Посмотреть сообщение
printf("%.5f
Округляет до ближайшего или как? Может вручную округлить до пятого знака?
iama
 Аватар для iama
1249 / 974 / 48
Регистрация: 30.07.2010
Сообщений: 5,297
24.08.2011, 16:27  [ТС]     Простая задача? #5
Deviaphan, мне тоже кажется, что проблема в округлении. Практика на той же тестирующей системе показывает, что под "точностью" в большинстве случаев имеется в виду именно отбрасывание остатка, а не округление. Попробую округлять и отпишусь

Добавлено через 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
#include <iostream>
#include <cmath>
 
using namespace std;
 
int main()
 {
    int t, q, n, k, s, a, i;
    double r, x;
 
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
 
    scanf("%d", &t);
 
    for (q = 0; q < t; q++)
    {
        s = 0;
        scanf("%d %d", &n, &k);
 
        for (i = 0; i < k - 1; i++)
        {
            scanf("%d", &a);
            s += a;
        }
 
        r = 1. - double(s) / double(n);
 
        r *= 100000.;
        x = floor(r);
 
        if (r - x < 0.5)
            r = x;
        else
            r = x + 1.;
 
        r /= 100000.;
 
        printf("%.5Lf\n", r);
    }
 
    return 0;
 }
grizlik78
Эксперт C++
 Аватар для grizlik78
1882 / 1414 / 101
Регистрация: 29.05.2011
Сообщений: 2,958
24.08.2011, 17:58     Простая задача? #6
iama, попробуй в Паскале вот такие числа, как здесь. Что выводится на Паскале? У меня просто его нет под рукой.
iama
 Аватар для iama
1249 / 974 / 48
Регистрация: 30.07.2010
Сообщений: 5,297
24.08.2011, 18:09  [ТС]     Простая задача? #7
grizlik78, в смысле, как округлять будет? Ты имеешь в виду, просто вывести те же числа с такой же точностью?
grizlik78
Эксперт C++
 Аватар для grizlik78
1882 / 1414 / 101
Регистрация: 29.05.2011
Сообщений: 2,958
24.08.2011, 18:25     Простая задача? #8
Да. Интересно, что выводится в тем компилятором Паскаля, на котором задача прошла.

Добавлено через 6 минут
Интересно ещё то, что если в моей программе заменить double на float, то округление происходит ожидаемым образом. Но всё это зыбко и на это полагаться не очень-то хорошо. Но прибавление epsilon перед выводом, мне кажется, в данной конкретной задаче бы должно помочь.
iama
 Аватар для iama
1249 / 974 / 48
Регистрация: 30.07.2010
Сообщений: 5,297
24.08.2011, 18:34  [ТС]     Простая задача? #9
Цитата Сообщение от grizlik78 Посмотреть сообщение
Но прибавление epsilon перед выводом, мне кажется, в данной конкретной задаче бы должно помочь.
Спасибо, сейчас попробую

Добавлено через 3 минуты
И таки прошло! Тот тест который не проходило, но завалило 2 еще сейчас еще поэкспериментирую

Добавлено через 1 минуту
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
#include <iostream>
 
using namespace std;
 
int main()
 {
    int t, q, n, k, s, a, i;
    double r, x;
 
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
 
    scanf("%d", &t);
 
    for (q = 0; q < t; q++)
    {
        s = 0;
        scanf("%d %d", &n, &k);
 
        for (i = 0; i < k - 1; i++)
        {
            scanf("%d", &a);
            s += a;
        }
 
        r = 1.0000001 - double(s) / double(n);
 
        printf("%.5Lf\n", r);
    }
 
    return 0;
 }
Прошло на полный балл. Мда, но как такие баги (если это баги) можно отловить не имея тестов и тестирующей системы? Всегда добавлять константу, которая в 10 раз меньше величины погрешности? Опять-таки иллюзия того, что всегда сработает верно, а вычитывать IEEE 754 перед каждым контестом...
grizlik78
Эксперт C++
 Аватар для grizlik78
1882 / 1414 / 101
Регистрация: 29.05.2011
Сообщений: 2,958
24.08.2011, 18:39     Простая задача? #10
Ну я багами считаю как раз вот такие задания, так как максимально чётко должно быть оговорено, что значит точность. Проверяющая система, выходит, считает ошибочными результаты, которые отличаются от истинного значения на половину разряда (хотя принимаемый её за правильный ответ отличается от истинного значения на те же пол-разряда, только в другую сторону).
iama
 Аватар для iama
1249 / 974 / 48
Регистрация: 30.07.2010
Сообщений: 5,297
24.08.2011, 18:43  [ТС]     Простая задача? #11
grizlik78, ты идеалист сейчас на многих платформах очень хорошим тоном считается давать условие одними недомолвками...

Не по теме:

Пойду-ка я на zadolbali.ru душу изливать...

Deviaphan
Делаю внезапно и красиво
Эксперт C++
 Аватар для Deviaphan
1283 / 1217 / 50
Регистрация: 22.03.2011
Сообщений: 3,744
24.08.2011, 18:53     Простая задача? #12
По поводу округления. Не быдлокод.) И без условных переходов.
C++
1
2
3
4
5
6
double v = ...;
v *= 1e5;
v += 0.5;
v = floor(v);
v *= 1e-5;
// Округлено до пятого знака.
grizlik78
Эксперт C++
 Аватар для grizlik78
1882 / 1414 / 101
Регистрация: 29.05.2011
Сообщений: 2,958
24.08.2011, 19:17     Простая задача? #13
Цитата Сообщение от iama Посмотреть сообщение
printf("%.5Lf\n", r);
Вот здесь выводится как бы long double, хотя r имеет тип double. Это сделано намеренно? Потому что, это, вообще говоря, должно привести к выводу неправильных значений там, где sizeof(long double) != sizeof(double).
iama
 Аватар для iama
1249 / 974 / 48
Регистрация: 30.07.2010
Сообщений: 5,297
24.08.2011, 19:34  [ТС]     Простая задача? #14
grizlik78, экспериментальным путем было выяснено, что для тамошнего компилятора разницы, вроде бы и нет. Просто я посылаю много отправок, и, временами засчитывается такое, что приличным людям стыдно показывать конкретно тут я поправить забыл

Deviaphan, спасибо, тоже попробую

Добавлено через 3 минуты
Deviaphan, и таки тоже засчитано запомню и буду пользовать вместо моего быдлоокругления, спасибо
Deviaphan
Делаю внезапно и красиво
Эксперт C++
 Аватар для Deviaphan
1283 / 1217 / 50
Регистрация: 22.03.2011
Сообщений: 3,744
24.08.2011, 19:41     Простая задача? #15
Цитата Сообщение от iama Посмотреть сообщение
и буду пользовать вместо моего быдлоокругления
float можно ещё округлять на битовом уровне. Но там уже до представления числа нужно опускаться.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
24.08.2011, 19:43     Простая задача?
Еще ссылки по теме:

простая задача на цикл C++
Простая задача с использованием циклов C++
простая задача C++

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

Или воспользуйтесь поиском по форуму:
iama
 Аватар для iama
1249 / 974 / 48
Регистрация: 30.07.2010
Сообщений: 5,297
24.08.2011, 19:43  [ТС]     Простая задача? #16
Deviaphan, по мне, для олимпиадного программирования это уже перебор хотя прийдет время, когда и это прийдется разбирать.
Мда, кто бы мог подумать, что printf не умеет нормально округлять...
Yandex
Объявления
24.08.2011, 19:43     Простая задача?
Ответ Создать тему
Опции темы

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