% =====================================================================
% cheatsheet.tex — KACTL-style multi-column competitive-programming
% cheatsheet template.
%
% This file is a TEMPLATE consumed by tools/cheatsheet.py. The script
% replaces three placeholder tokens (each written as two percent signs,
% a NAME, then two percent signs) before compiling:
%
%   TITLE       -> the cheatsheet title (LaTeX-escaped)
%   NUMCOLUMNS  -> number of multicol columns (integer)
%   BODY        -> the generated body (one block per algorithm)
%
% The tokens themselves appear only in the title/multicols area below.
% It compiles with a plain `pdflatex` and only common packages:
% article + geometry + multicol + listings + xcolor.
% =====================================================================
\documentclass[8pt,a4paper,landscape]{extarticle}

\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\usepackage[a4paper,landscape,margin=1cm]{geometry}
\usepackage{multicol}
\usepackage{xcolor}
\usepackage{listings}
\usepackage{graphicx}   % for optional logos on the title page (see below)

% Tighten everything up for a dense reference sheet.
\setlength{\parindent}{0pt}
\setlength{\columnsep}{1.2em}
\setlength{\columnseprule}{0.2pt}
\pagestyle{empty}

% --- Colours -----------------------------------------------------------
\definecolor{cs@rule}{gray}{0.55}
\definecolor{cs@kw}{RGB}{0,0,153}
\definecolor{cs@cmt}{RGB}{0,128,0}
\definecolor{cs@str}{RGB}{163,21,21}
\definecolor{cs@bg}{gray}{0.97}

% --- Listings: small, tight, monospaced --------------------------------
\lstset{
  basicstyle=\ttfamily\scriptsize,
  keywordstyle=\color{cs@kw}\bfseries,
  commentstyle=\color{cs@cmt}\itshape,
  stringstyle=\color{cs@str},
  showstringspaces=false,
  breaklines=true,
  breakatwhitespace=false,
  columns=fullflexible,
  keepspaces=true,
  tabsize=2,
  aboveskip=2pt,
  belowskip=2pt,
  lineskip=-1pt,
  xleftmargin=0pt,
  frame=none,
  backgroundcolor=\color{cs@bg},
  % `listings` is byte-oriented, so multi-byte UTF-8 chars that show up in
  % comments must be mapped explicitly or inputenc rejects them.
  extendedchars=true,
  literate=
    {á}{{\'a}}1 {é}{{\'e}}1 {í}{{\'i}}1 {ó}{{\'o}}1 {ú}{{\'u}}1
    {Á}{{\'A}}1 {É}{{\'E}}1 {Í}{{\'I}}1 {Ó}{{\'O}}1 {Ú}{{\'U}}1
    {ñ}{{\~n}}1 {Ñ}{{\~N}}1 {ü}{{\"u}}1 {Ü}{{\"U}}1 {ç}{{\c c}}1
    {—}{{---}}1 {–}{{--}}1 {…}{{\ldots}}1
    {¿}{{?`}}1 {¡}{{!`}}1 {«}{{<<}}1 {»}{{>>}}1
    {→}{{$\rightarrow$}}1 {←}{{$\leftarrow$}}1
    {≤}{{$\leq$}}1 {≥}{{$\geq$}}1 {≠}{{$\neq$}}1
    {×}{{$\times$}}1 {·}{{$\cdot$}}1 {∞}{{$\infty$}}1 {°}{{$^\circ$}}1,
}

% Section heading for one algorithm: bold title, then a separating rule.
% The rule sits BELOW the title (small positive gaps around it) so it never
% overlaps the heading text.
\newcommand{\csalgo}[1]{%
  \vspace{0.8ex}%
  {\bfseries\small #1}\par
  \vspace{0.4ex}{\color{cs@rule}\hrule height 0.4pt}\vspace{0.5ex}%
}
% Stats line (complexity / use case) under an algorithm heading.
\newcommand{\csstats}[1]{{\scriptsize\itshape #1\par\vspace{0.3ex}}}

\begin{document}

% =====================================================================
% TITLE PAGE — your team's cover sheet.
%
% Edit the fields marked "<-- EDIT" below (team name, university, members,
% logos). Contests such as ICPC / SWERC usually require your team name and
% institution on printed material, so keep a cover page handy.
%
% To add a logo: drop an image (png / jpg / pdf) next to this .tex file and
% UNCOMMENT the matching \includegraphics line (graphicx is already loaded).
%
% Don't want a cover? Delete this whole block, from the line below down to
% and including the "\clearpage".
% ---------------------------------------------------------------------
\begin{titlepage}
\begin{center}
  \vspace*{\fill}

  % \includegraphics[width=7cm]{logo.png}\par        % <-- EDIT: university logo (uncomment)
  \vspace{1cm}

  {\Huge\bfseries Nombre del equipo}\par              % <-- EDIT: your team name
  \vspace{0.8cm}
  {\Large CUNEF Universidad}\par                      % <-- EDIT: your university / institution
  \vspace{0.5cm}
  {\large Integrante 1 \quad Integrante 2 \quad Integrante 3}\par   % <-- EDIT: team members
  \vspace{1.5cm}

  % \includegraphics[width=4cm]{mascota.png}\par      % <-- EDIT: extra image / mascot (uncomment)

  \vspace*{\fill}
\end{center}
\end{titlepage}
\clearpage
% =====================================================================

% --- Title -------------------------------------------------------------
\begin{center}
  {\Large\bfseries Chuletario ICPC CUNEF}
\end{center}
\vspace{0.5ex}
{\color{cs@rule}\hrule height 0.6pt}
\vspace{0.8ex}

\begin{multicols}{3}
\csalgo{Binary search}
\csstats{time: O(log n), space: O(1)  |  Encontrar un valor en un array ordenado.}
\begin{lstlisting}[language=C++]
#include <vector>
using namespace std;
int binary_search_idx(const vector<int>& a, int target) {
    int lo = 0, hi = (int)a.size() - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (a[mid] == target) return mid;
        if (a[mid] < target) lo = mid + 1;
        else                 hi = mid - 1;
    }
    return -1;
}
\end{lstlisting}

\csalgo{Fast I/O (C++)}
\begin{lstlisting}[language=C++]
// C++ fast I/O — put these two lines first, inside main():
ios::sync_with_stdio(false);
cin.tie(nullptr);
// Then read/print as usual:  cin >> x;   cout << x << '\n';
// (use '\n', never endl inside loops — endl flushes the buffer every time).
\end{lstlisting}

\csalgo{Fast I/O (Python)}
\begin{lstlisting}[language=Python]
# Python fast I/O — swap input() for the buffered reader (drop-in, at the top):
import sys
input = sys.stdin.readline
# input().split() reads one line; for many tokens at once: sys.stdin.read().split().
# Print a lot in one go:  print("\n".join(map(str, answers)))
\end{lstlisting}

\csalgo{Dijkstra}
\csstats{time: O((V+E) log V), space: O(V+E)  |  Camino más corto desde un origen con pesos no negativos.}
\begin{lstlisting}[language=C++]
#include <vector>
#include <queue>
#include <functional>
using namespace std;
const long long INF = 1e18;
vector<long long> dijkstra(int n, const vector<vector<pair<int, int>>>& adj, int src) {
    vector<long long> dist(n, INF);
    priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<>> pq;
    dist[src] = 0;
    pq.push({0, src});
    while (!pq.empty()) {
        auto [d, u] = pq.top();
        pq.pop();
        if (d > dist[u]) continue;
        for (auto [v, w] : adj[u]) {
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                pq.push({dist[v], v});
            }
        }
    }
    return dist;
}
\end{lstlisting}

\csalgo{MiniMax}
\csstats{time: O(n), space: O(n)  |  Encontrar el mejor movimiento en un juego de dos jugadores.}
\begin{lstlisting}[language=C++]
#include <vector>
#include <functional>
#include <limits>
#include <utility>
using namespace std;
template <typename State>
pair<double, int> minimax(
    const State& current_state,
    int maximizing_player,
    const function<vector<State>(const State&)>& possible_moves_funct,
    const function<double(const State&)>& score_funct) {
    vector<State> next_states = possible_moves_funct(current_state);
    if (next_states.empty())
        return {score_funct(current_state), -1};
    double best_value = (maximizing_player == 1)
        ? -numeric_limits<double>::infinity()
        :  numeric_limits<double>::infinity();
    int best_move = -1;
    for (int index = 0; index < (int) next_states.size(); ++index) {
        double value = minimax(next_states[index], -maximizing_player,
                               possible_moves_funct, score_funct).first;
        if (maximizing_player == 1) {
            if (value > best_value) { best_value = value; best_move = index; }
        } else {
            if (value < best_value) { best_value = value; best_move = index; }
        }
    }
    return {best_value, best_move};
}
\end{lstlisting}

\csalgo{Fenwick Tree (BIT)}
\csstats{build: O(n), update: O(log n), query: O(log n), space: O(n)  |  Sumas de prefijos con actualizaciones puntuales.}
\begin{lstlisting}[language=C++]
#include <vector>
using namespace std;
struct FenwickTree {
    int n;
    vector<int> tree;
    FenwickTree(int n) : n(n), tree(n) {}
    void update(int index, int delta) {
        for (index++; index <= n; index += index & -index)
            tree[index - 1] += delta;
    }
    int query(int index) {
        int acc = 0;
        for (; index > 0; index -= index & -index)
            acc += tree[index - 1];
        return acc;
    }
    int query_range(int l, int r) { return query(r) - query(l); }
};
\end{lstlisting}

\csalgo{Convex hull}
\csstats{time: O(n log n), space: O(n)  |  El menor polígono convexo que contiene un conjunto de puntos.}
\begin{lstlisting}[language=C++]
#include <vector>
#include <algorithm>
using namespace std;
struct P {
    long long x, y;
    bool operator<(const P& o) const {
        return x < o.x || (x == o.x && y < o.y);
    }
};
long long cross(const P& O, const P& A, const P& B) {
    return (A.x - O.x) * (B.y - O.y) - (A.y - O.y) * (B.x - O.x);
}
vector<P> convex_hull(vector<P> pts) {
    int n = pts.size();
    if (n < 3) return pts;
    sort(pts.begin(), pts.end());
    vector<P> hull;
    for (int i = 0; i < n; i++) {
        while (hull.size() >= 2 &&
               cross(hull[hull.size() - 2], hull.back(), pts[i]) <= 0)
            hull.pop_back();
        hull.push_back(pts[i]);
    }
    size_t base = hull.size() + 1;
    for (int i = n - 2; i >= 0; i--) {
        while (hull.size() >= base &&
               cross(hull[hull.size() - 2], hull.back(), pts[i]) <= 0)
            hull.pop_back();
        hull.push_back(pts[i]);
    }
    hull.pop_back();
    return hull;
}
\end{lstlisting}
\end{multicols}

\end{document}
