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

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

Войти
Регистрация
Восстановить пароль
 
 
iama
1250 / 975 / 49
Регистрация: 30.07.2010
Сообщений: 5,297
#1

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

24.08.2011, 15:42. Просмотров 1062. Ответов 15
Метки нет (Все метки)

Здравствуйте! После участия в ДЛКШ я понял, что очень много не знаю даже о самых элементарных вещах в Си\Си++. Например, обыкновенная простая задача на теорию вероятностей -
полное условие под катом.
Цветные шары

В урне находится 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++
Пожалуйста помогите кто может, очень нужно Даны натуральное число n, действительные числа a1,...,an (1 и n это нижние индексы). Выяснить...

простая задача - C++
Напишите программу, которая подводит итоги Олимпийских игр. Программа должна получить от пользователя число медалей разного достоинства,...

Простая задача - C++
Друзья, в общем если нарушаю какие-либо правила заранее извиняюсь. В общем говорю честно я студент, и в с++ пока что в общем то 0. Прошу...

Простая задача - C++
Помогите пожалуйста решить. Имеется в наличии 3 арбуза. Найти самый тяжелый. Примечание: решить задачу, используя язык...

Простая задача с массивами - C++
Добрый день, на сайте ********/asp/gb.asp?page2=1&amp;id=9&amp;page=1 есть задача, Я ее решил, у меня все работает, и когда я подставляю в...

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

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

Добавлено через 2 минуты
Переписал с cstdio и stdio.h Не проходит тот же тест - все остальные - "Засчитано"
Deviaphan
Делаю внезапно и красиво
Эксперт C++
1286 / 1220 / 50
Регистрация: 22.03.2011
Сообщений: 3,744
24.08.2011, 16:01 #4
Цитата Сообщение от iama Посмотреть сообщение
printf("%.5f
Округляет до ближайшего или как? Может вручную округлить до пятого знака?
iama
1250 / 975 / 49
Регистрация: 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
Эксперт С++
1908 / 1440 / 111
Регистрация: 29.05.2011
Сообщений: 2,996
24.08.2011, 17:58 #6
iama, попробуй в Паскале вот такие числа, как здесь. Что выводится на Паскале? У меня просто его нет под рукой.
iama
1250 / 975 / 49
Регистрация: 30.07.2010
Сообщений: 5,297
24.08.2011, 18:09  [ТС] #7
grizlik78, в смысле, как округлять будет? Ты имеешь в виду, просто вывести те же числа с такой же точностью?
grizlik78
Эксперт С++
1908 / 1440 / 111
Регистрация: 29.05.2011
Сообщений: 2,996
24.08.2011, 18:25 #8
Да. Интересно, что выводится в тем компилятором Паскаля, на котором задача прошла.

Добавлено через 6 минут
Интересно ещё то, что если в моей программе заменить double на float, то округление происходит ожидаемым образом. Но всё это зыбко и на это полагаться не очень-то хорошо. Но прибавление epsilon перед выводом, мне кажется, в данной конкретной задаче бы должно помочь.
iama
1250 / 975 / 49
Регистрация: 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
Эксперт С++
1908 / 1440 / 111
Регистрация: 29.05.2011
Сообщений: 2,996
24.08.2011, 18:39 #10
Ну я багами считаю как раз вот такие задания, так как максимально чётко должно быть оговорено, что значит точность. Проверяющая система, выходит, считает ошибочными результаты, которые отличаются от истинного значения на половину разряда (хотя принимаемый её за правильный ответ отличается от истинного значения на те же пол-разряда, только в другую сторону).
iama
1250 / 975 / 49
Регистрация: 30.07.2010
Сообщений: 5,297
24.08.2011, 18:43  [ТС] #11
grizlik78, ты идеалист сейчас на многих платформах очень хорошим тоном считается давать условие одними недомолвками...

Не по теме:

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

Deviaphan
Делаю внезапно и красиво
Эксперт C++
1286 / 1220 / 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
Эксперт С++
1908 / 1440 / 111
Регистрация: 29.05.2011
Сообщений: 2,996
24.08.2011, 19:17 #13
Цитата Сообщение от iama Посмотреть сообщение
printf("%.5Lf\n", r);
Вот здесь выводится как бы long double, хотя r имеет тип double. Это сделано намеренно? Потому что, это, вообще говоря, должно привести к выводу неправильных значений там, где sizeof(long double) != sizeof(double).
iama
1250 / 975 / 49
Регистрация: 30.07.2010
Сообщений: 5,297
24.08.2011, 19:34  [ТС] #14
grizlik78, экспериментальным путем было выяснено, что для тамошнего компилятора разницы, вроде бы и нет. Просто я посылаю много отправок, и, временами засчитывается такое, что приличным людям стыдно показывать конкретно тут я поправить забыл

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

Добавлено через 3 минуты
Deviaphan, и таки тоже засчитано запомню и буду пользовать вместо моего быдлоокругления, спасибо
Deviaphan
Делаю внезапно и красиво
Эксперт C++
1286 / 1220 / 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:41
Привет! Вот еще темы с ответами:

простая задача на цикл - C++
Определите сумму всех элементов последовательности, завершающейся числом 0. Числа, следующие за нулем, считывать не нужно. Вот...

Пифагоровы тройки (простая задача) - C++
Прямоугольный треугольник может иметь все стороны, выраженные целыми числами. Множество троек целых значений сторон прямоугольного...

Двумерный массив, простая задача. - C++
Задать квадратную матрицу порядка N. Вычислить и запомнить в массиве произведение элементов каждого столбца матрицы. //вроде эелементарно,...

Задача простая Года n<=100 - C++
Дано натуральне число n(n&lt;=100), яке визначає вік людини ( в роках). Дати для цього числа найменування «років», «рік», «роки»: наприклад, 1...


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

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
24.08.2011, 19:41
Ответ Создать тему
Опции темы

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