According to an ancient legend, the sage who invented chess demanded such a quantity of wheat from the Persian Shah that they could cover the chessboard, putting 1 grain on the first cell, 2 on the second cell, 4 on the third, etc. . for every next two more than the previous one. How much grain can a chessboard cover?

Here is the code:

#include <stdio.h> #include <math.h> #include <conio.h> void main() {long int s, k, i; clrscr; s=1; for(i=1;i<=64;i++) {k=exp(i*log(2)); s+=k } printf("Kol-vo zeren=%50d\n",s); getch(); }

The problem is that the code gives the wrong answer, and yes even with a minus. I do not understand why, and judging by the benefits - the cycle is set correctly

  • one
    You have k overflow. When reaching too large values ​​of integer variables go into the negative. Read, for example, this discussion . (There's about Java, but with C ++ the same story.) - VladD
  • Um, and how to fix it? Never encountered overflow) - Treaq
  • one
    @Treaq: 1. Try increasing the width of your variable. For example, instead of long take long long . This will help for a while. 2. Use the floating point type instead of the integer type. There are even more limits. But all the same, sooner or later you will come to the limit. 3. Use special arithmetic types of arbitrary precision. (for example, GMP or boost :: multiprecision ). There are no such types built into the language. - VladD
  • one
    @VladD, I agree, the TC has an incorrect cycle. By the condition of the problem, one seed should lie on the first cell, not two. - falstaf
  • one
    again, these cycles for progressions ... school chtol canceled? - Yura Ivanov

2 answers 2

The long type includes the range of values [–2147483,648; 2147483647] [–2147483,648; 2147483647] (or [0; 4294967295] , in the case of unsigned long ). Obviously, the value

 18 446 744 073 709 551 615

which is the answer to this problem, does not fall within the specified ranges. As a result, you have an overflow. Read, for example, here .

Solution: use unsigned long long .

  • Well, it depends on the capacity of the system. 32-bit long for today is quite a rare thing. --- Hmm, I take my words back. MSVC 2013 has a long 32-bit . - VladD
  • It still does not help. Refuses to give the correct answer - Treaq
  • one
    @Treaq, do you want your program with exp() and log() work? It will not work. The size of the mantissa in double (the result of these functions) is only 52 bits. - avp
  • @avp: Right. Due to rounding errors, the result will be different. - VladD

Since the number of grains doubles with each cell, the result can be represented as a binary number:

 1*2^0 + 1*2^1 + ... + 1*2^63

There is nothing more than a completely clogged 64bit integer.
It is known that such a number (all bits included) also represents -1 in the sign representation.

Therefore, the solution to the problem may simply be castes:

 #include <iostream> int main() { std::cout << (uint64_t) -1 << "\n"; }
  • You, of course, did a great job of rewriting the three-year-old comments from VladD and falstaf as a useless answer, but I would not praise you for that. - Alex Krass
  • @AlexKrass, they have accused me of the unknown. Give me a link - vp_arth
  • Oops, I didn’t look at the dates, sorry. This @Kromster is to blame - vp_arth
  • But I didn't need the 128bit type, did I? And about the castes of -1 there is not a word - vp_arth
  • As you wish, but the consequence is obvious to me. In general, your case, I expressed my opinion. At least the question implies not finding the right answer, but finding out the reason for its incorrectness in the TS code. - Alex Krass