Код решения-силы «Театральная площадь, 1А» в C - PullRequest
Новая
       178

Код решения-силы «Театральная площадь, 1А» в C

1 голос
/ 01 августа 2020

начинающий программист пытается улучшить C, поэтому я начал решать проблемы с кодом на веб-сайте codeforces. Однако я, кажется, застрял, я написал код, который, кажется, работает на практике, но веб-сайт не принимает его как правильное.

проблема:

Театральная площадь в столице Берляндии имеет форму прямоугольника angular размером n × m метров. По случаю юбилея города было принято решение выложить площадь квадратными гранитными плитами. Каждая плита имеет размер a × a. Какое наименьшее количество плит необходимо для мощения Площади? Разрешено покрывать площадь больше Театральной площади, но площадь должна быть закрыта. Не разрешается ломать плиты. Стороны плиток должны быть параллельны сторонам Квадрата. 1

Источник:

https://codeforces.com/problemset/problem/1/A

Мне было трудно полностью понять математику, стоящую за проблемой, и я использовал ответ этого источника от пользователя по имени «Джошуа Пан», чтобы лучше понять проблему.

Источник:

https://www.quora.com/How-do-I-solve-the-problem-Theatre-Square-on-Codeforces

Это мой код: 

#include<stdio.h>
#include<math.h>

int main(void)
{
    double n,m,a;
    scanf("%lf %lf %lf", &n,&m,&a);
    printf("%1.lf\n", ceil(n/a)*ceil(m/a));

    return 0;
}

Я скомпилировал его с помощью "g cc TheatreSquare. c -lm"

Если задано пример ввода 6,6,4 мой код дает правильный результат 4, однако веб-сайт не принимает этот код как правильный, я могу ошибаться, но, возможно, я неправильно использую спецификаторы формата?

Заранее спасибо.

Ответы [ 2 ]

2 голосов
/ 01 августа 2020

Типичный double (64-битная с плавающей запятой IEEE754) не имеет достаточной точности для решения проблемы.

Например, для ввода 

999999999 999999999 1

Ваша программа может выдавать выходные данные 

999999998000000000

Фактический ответ: 

999999998000000001

Чтобы избежать этого, вам не следует использовать тип данных с плавающей запятой.

Вы можете добавить #include <inttypes.h> и используйте 64-битный целочисленный тип int64_t для этого расчета.

"%" SCNd64 - для чтения, а "%" PRId64 - для записи int64_t.

cell(n/a) для целых чисел может быть выполнено по (n + a - 1) / a.

1 голос
/ 01 августа 2020

Вы можете решить эту проблему с помощью целых чисел. 

#include <stdio.h>

int main()
{
    unsigned long n, m, a = 1;
    unsigned long na, ma, res = 0;
    
    scanf("%lu %lu %lu", &n, &m, &a);
    
    na = n/a;

    if (n%a != 0)
        na++;
    
    ma = m/a;

    if (m%a != 0)
        ma++;

    res = na * ma;

    printf("%lu", res);

    return 0;
}

Этот код завершится ошибкой на платформе Codeforce в тесте 9 (см. Ниже). Но если вы скомпилируете его и запустите локально с теми же входными данными, результат будет правильным. 

> Test: #9, time: 15 ms., memory: 3608 KB, exit code: 0, checker exit code: 1, verdict: WRONG_ANSWER
> Input 1000000000 1000000000 1
> Output 2808348672 Answer 1000000000000000000
> Checker Log wrong answer 1st numbers differ - expected: '1000000000000000000', found: '2808348672'

EDIT:

Проблема, описанная выше, связана с тот факт, что я использую 64-битную машину, а онлайн-компилятор, вероятно, использует 32-битную версию. Переполнение переменных unsigned long.

Следующий код пройдет все тесты. 

#include <stdio.h>

int main()
{
    unsigned long long n, m, a = 1;
    unsigned long long na, ma, res = 0;
    
    scanf("%llu %llu %llu", &n, &m, &a);
    
    na = n/a;

    if (n%a != 0)
        na++;
    
    ma = m/a;

    if (m%a != 0)
        ma++;

    res = na * ma;

    printf("%llu", res);

    return 0;
}
...