1 - Programming languages, Working with numbers

책 읽고 정리

Part 1 Basic techniques
Competitive programming combines two topics:
(1) the design of algorithms
(2) the implementation of algorithms

Programming languages

C++ code template

#include <bits/stdc++.h>

using namespace std;

int main() {
	// solution comes here 
}

1) Input and output
Input and output is sometimes a bottleneck in the program. The following lines at the beginning of the code make input and output more efficient

ios::sync_with_stdio(0); 
cin.tie(0);

Sometimes the program should read a whole line from the input, possibly containing spaves.
This can be accomplished by using the getline function

string s;
getline(cin, s);

If the amout of data is unknown, the following loop is useful

while(cin >>x){
	//code
}

In some contest systems, files are used for input and output An easy solution for this is to write the code as usual standard streams, but add the following lines to the beginning of the code

freopen("input.txt", "r", stdin); 
freopen("output.txt", "w", stdout);

Working with numbers

1) Integers

int 32-bit
long 64-bit

long long x =123456789123456789LL;

A common mistake when using the type long long is that the type int is still user somewhere in the code.

int a = 123456789; 
long long b = a*a; 
cout << b << "\n"; // -1757895751

The problem can be solved by changing the type of a to long long or by changint the expression to (long long) a*a

2) Modular arithmetic

An important property of the remainder is that in addition, subtraction and multiplication, the remainder can be taken before the operation 

(a+b) mod m = (a mod m+b mod m) mod m 
(a−b) mod m = (a mod m−b mod m) mod m 
(a·b) mod m = (a mod m·b mod m) mod m

The following code calculates n!, the factorial of n, modulo m

long long x =1;
for(int i=2;i<=n;i++){
	x = (x*i)*m;
}
cout<<x%m<<"\n;

Floating point numbers
A difficulty when using floating point numbers is that some numbers cannot be represented accurately as floating poing numbers, and there will be rounding errors.

double x = 0.3*3+0.1; 
printf("%.20f\n", x); // 0.99999999999999988898

Due to a rounding error, the value of x is a bit smaller than 1, while the correct value would be 1

if (abs(a-b) < 1e-9){ 
	// a and b are equal 
}