Блог пользователя vjindal23

Submission #48143688 on A. Integer Sequence Dividing in Codeforces Round #531 (Div. 3)
Автор vjindal23, история, 5 лет назад, По-английски

While I submitted, my solution was accepted but now I check next day to know my ranking it shows that in last test case no output is printed. I tried same code with that input on my laptop and it works fine. Can someone point the mistake?

Error: "wrong output format Unexpected end of file — token expected"

Code:

#include <stdio.h>

int main(){ // commented section removed
    int i, j, k;
    long int n;
    scanf("%ld", &n);
    long int sum = 0;
    sum = n*(n+1)/2;
    if(sum%2 == 1) printf("1");
    if(sum%2 == 0) printf("0");
    return 0;
}
  • Проголосовать: нравится
  • +3
  • Проголосовать: не нравится

»
5 лет назад, # |
← Rev. 7   Проголосовать: нравится +5 Проголосовать: не нравится

The long int is not enough as when n is 1e9, the sum can be 1e18. Try using long long and you can get AC :).

→ Ответить
»
5 лет назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

The bug is in this 4 lines of your code:

long int n;
scanf("%ld", &n);
long int sum = 0;
sum = n*(n+1)/2;

Or more specifically, this line: sum = n*(n+1)/2; Since type long int holds a maximum value of 2147483647, when n reaches 999999998 (as in test #10), sum equals to 499999998500000001, which is way larger than what it can hold. Note that n does not overflow, but we still have to change it to long long int to not get integer overflow in the line sum = n*(n+1)/2; To fix this, change to:

long long int n;
scanf("%lld", &n);
long long int sum = 0;
sum = n*(n+1)/2;

Bingo!

→ Ответить
  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +4 Проголосовать: не нравится

    Good details!

    → Ответить
  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Thanks for the details, but I don't get why "n" should also be long long int type? I agree with you that sum should have been long long int. Can't we manage with "n" being long int only? If you happen to know the details as to how "sum = n*(n+1)/2" happens to execute which probably makes you say that "n" should be long long int then please share. Anyhow, thanks for the reason :)

    → Ответить
    • »
      »
      »
      5 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      If n is a 32-bit integer, then the multiplication will be carried out in 32-bits, then cast to 64 bits. You'd want something like

      long long sum = 1LL * n * (n + 1) / 2

      to avoid overflow.

      → Ответить