This is my most favorite problem on INAMO this year.(Generally disappointed on the problems' quality this year) The answer is all polynomials of the form $P(x) = c$ or $P(x) = x + c$ for some $c \in \mathbb{Z}$. First, such polynomial works since \[ P(\lfloor x \rfloor) = c = \lfloor c \rfloor = \lfloor P(x) \rfloor, \forall x \in \mathbb{R} \]and \[ P(\lfloor x \rfloor) = \lfloor x \rfloor + c = \lfloor x + c \rfloor = \lfloor P(x) \rfloor \]Now, we will prove that no other polynomials satisfy. $\textbf{Claim 01.}$ $P(a) \in \mathbb{Z}$ if $a \in \mathbb{Z}$. Proof. Notice that if $a \in \mathbb{Z}$, then \[ P(a) = \lfloor P(a) \rfloor \rightarrow \{ P(a) \} = 0 \]which forces $P(a) \in \mathbb{Z}$. $\textbf{Claim 02.}$ $P(x) - 1 \le P(x + 1) \le P(x) + 1$ for all $x \in \mathbb{Z}$. $\textit{Proof.}$ Suppose that there exists an integer $a$ such that $P(a + 1) > P(a) + 1$. Then, by Intermediate Value Theorem (since every polynomial is a continuous function), then there exists $\varepsilon \in (0,1)$ such that \[ P(a + \varepsilon) = P(a) + 1 \]However, we know that $P(a) \in \mathbb{Z}$ by assumption, and $P(a) + 1 = \lfloor P(a + \varepsilon) \rfloor = P(\lfloor a + \varepsilon \rfloor) = P(a)$, which is a contradiction. The other inequality is also analogously similar in proof. Now, notice that for every integers $x$, we have either $P(x + 1) = P(x)$, $P(x + 1) = P(x) + 1$ or $P(x + 1) = P(x) - 1$, since $P(a) \in \mathbb{Z}$ for every $a \in \mathbb{Z}$. Therefore, by Pigeon Hole Principle, there exists a constant $c \in \{ -1, 0, 1 \}$ such that \[ P(x + 1) = P(x) + c \]is true for infinitely many integers $x$. Now, consider $Q(x) = P(x + 1) - P(x) - c$ which has infinitely many integer roots, forcing $Q(x) \equiv 0$. Therefore, \[ P(x + 1) = P(x) + c \ \forall x \in \mathbb{R} \]Case 01. If $c = 0$. Then $P(x + 1) = P(x)$ for all $x \in \mathbb{R}$. Now, consider the polynomials $P(x) - P(0)$, which has infinitely many roots. Therefore, this forces $P(x) = P(0)$ for all $x \in \mathbb{R}$, which means that $P(x) = c$. Now, since the polynomial is constant and attains integer value for all integer plug ins, then $c \in \mathbb{Z}$. Case 02. If $c = 1$ or $c = -1$. (Both of this are handled the same way). Therefore, we have \[ P(x + 1) = P(x) + 1, \forall x \in \mathbb{R} \]Then, $P(x + 1) - P(x) = 1$ for all $x \in \mathbb{R}$, forcing $P$ being linear why?. Now, let $P(x) = ax + b$. We know that $a = 1$ by simple checking. Therefore, $P(x) = x + b$ for a constant $b \in \mathbb{R}$. However, remember that $b = P(0) - 0 \in \mathbb{Z}$. Therefore, $P(x) = x + c$ for a constant $c \in \mathbb{Z}$.

The idea is that large polynomial goes large very fast, and that's not good. Clearly, $P$ constant works if it is an integer. If $P(x)=ax+b$ is linear, we have that $b=P(0)=\left\lfloor P(0)\right\rfloor$, so thus $b$ is an integer. Now, $a$ must also be an integer by considering $P(1)$. If $a>1$, we get that $P(0.5)=0.5a+b\geq b+1$, a contradiction. Similarly, if $a<0$, we have \[P(0.5)=0.5a+b<b\]a further contradiction. Thus $a=1$, and we get $P(x)=x+b$. Now, assume $P$ has degree at least 2 and consider the finite difference sequence $\Delta P$. We note that $\Delta P$ has degree at least $1$, so it is unbounded. If it is unbounded positive, we can find some $n$ such that $\Delta P(n)>10^{420}$, and thus by the Intermediate Value Theorem, as $P(x)$ is continuous, there exists $\delta\in (n,n+1)$ with $P(\delta)=P(n)+10^{69}$, and thus we have our contradiction, as clearly $\left\lfloor \delta\right\rfloor=n$ but $\left\lfloor P(\delta)\right\rfloor\neq P(n)$. Similarly, if it is unbounded below, we can do the same thing - consider some $n$ such that $\Delta P(n)<-10^{420}$. Then, we get there exists some $\delta\in (n,n+1)$ with $P(\delta)=P(n)-10^{69}$, once again contradictory (as the floor is not equal). Thus this case is impossible. Thus all solutions are $P(x)=c,x+c$ for $c\in\mathbb Z$.

Claim 1. $P(x)$ is linear. Proof. Assume that its degree is $\ge 2$. Then $ P(\lfloor x \rfloor) = \lfloor P(x) \rfloor \ \leq P(x)$. The condition implies that $|P(v_1)-P(v_2)|<1$ for all $i\leq v_1,v_2<i+1$ where $i$ is an integer. However, there is such an $i$ such that $|P(v_1)-P(v_2)|>1$ because there exists only finitely (downwards or upwards) mountains (a formal way to define mountains is when the second derivative is $0$) Let $P(x)=mx+c$. $x=0 \implies c$ is an integer. $x=1 \implies m+c=\lfloor m \rfloor +c \implies m$ is an integer. $x= \frac{1}{m} \implies m\lfloor \frac{1}{m} \rfloor =1 \implies m |1 \implies m=\pm 1$. $m=-1$ is obviously impossible. The solutions are $m=1,0$. Now we verify the solution 1. $P(x)=c$ for any integer $c$ $c=c$. 2. $P(x)=x+c$ for any integer $c$ $\lfloor x \rfloor +c=\lfloor x + c \rfloor = \lfloor x \rfloor + c$ @Below It's fixed

@above uuuh... to show that $P$ is non-decreasing, you have to show that $P(x) \leq P(y)$ for all $x \leq y$. But you only show it for the case where $x$ is an integer and $x \leq y < x + 1$. @2above wrote a solution that relies less on calculus, a nice one, so I will just write a solution that tries to avoid calculus. However, the nature of the solution should at least be the same as those above, if the solution is not exactly the same. Let's skip the case where $P$ is constant; this is easy to bash. Write $P(x) = \sum_{i = 0}^d a_i x^i$ for some $d \geq 1$ and real numbers $a_0, a_1, \ldots, a_d$, with $a_d \neq 0$. Notice that for all integers $n$, \[ \lfloor P(n) \rfloor = P(n) = \left\lfloor P\left(n + \frac{1}{2}\right) \right\rfloor. \]That means $P(n)$ is an integer and $P(n) \leq P\left(n + \frac{1}{2}\right) < P(n) + 1$. Now, consider the function $Q(x) = P\left(x + \frac{1}{2}\right) - P(x)$. It is well-known that $Q$ is a polynomial, so we can write either $Q(x) = \sum_{i = 0}^{d'} b_i x^i$ for some $d' \geq 0$ and $b_0, \ldots, b_{d'}$ with $b_{d'} \neq 0$, or $Q \equiv 0$. Actually, we can check that the latter is impossible for our pick of $P$ and that $d' = d - 1$ by a bit of bashing: $(x + 1/2)^k - x^k$ is a polynomial with degree $k - 1$ and leading coefficient $\frac{k}{2}$ for each $k \geq 1$, and summing all the expressions means that $Q$ is a polynomial with degree $d - 1$. By our argument before, $0 \leq Q(n) < 1$ for all integers $n$. Next, suppose for the sake of contradiction that $d > 1$, so $Q$ has degree $d - 1 \geq 1$. Then, the idea is that for all integers $n > 0$ big enough, \[ |Q(n)| \geq |b_{d - 1}| n^{d - 1} - \sum_{i = 0}^{d - 2} |b_i| n^i > 1. \]The left inequality is true due to triangle inequality, so we will try making the right inequality true. One idea is to take $n$ large enough such that $|b_{d - 1}| n > |b_{d - 1}| + |b_i|$ for each $0 \leq i \leq d - 2$ and also $|b_{d - 1}| n > |b_0| + 1$, i.e., we take: \[ n > \frac{1}{|b_{d - 1}|} \max\{|b_0| + 1, |b_{d - 1}| + \max_{0 \leq i \leq d - 2} |b_i|\}. \]Then, we can prove that for each $2 \leq k \leq n - 1$, \[ |b_{d - 1}| n^k - \sum_{i = 0}^{k - 1} |b_i| n^i \geq |b_{d - 1}| n^{k - 1} - \sum_{i = 0}^{k - 2} |b_i| n^i, \]which holds simply because $|b_{d - 1}| n^k - |b_{k - 1}| n^{k - 1} \geq |b_{d - 1}| n^{k - 1}$. Then, induction brings us to \[ |Q(n)| \geq |b_{d - 1}| n - |b_0|. \]And then, we also have $|b_{d - 1}| n - |b_0| > 1$, so $|Q(n)| > 1$ for some integer $n > 0$. A contradiction! As a result, $d = 1$, and thus $P$ is linear. Write $P(x) = cx + d$ for some $c \neq 0$ and $d \in \mathbb{R}$. As discussed before, $P(n)$ is an integer for all integers $n$, so $P(0) = d$ and $P(1) - P(0) = c$ is an integer. Expanding $P(\lfloor x \rfloor) = \lfloor P(x) \rfloor$ yields $c \lfloor x \rfloor + d = \lfloor cx + d \rfloor = \lfloor cx \rfloor + d$, so $c \lfloor x \rfloor = \lfloor cx \rfloor$ for all $x \in \mathbb{R}$. The rest is immediate to check that $c = 1$ (we ignored the case $c = 0$ already). Comment: This is actually at least an okay problem (pretty good), but I'm bugged by the fact that its natural solutions would likely use calculus. The solution I presented seems to also use the idea of calculus, although I tried to avoid it using some other idea.

Let $n $ be an integer. For $x$ in $(n,n+1),P(x) $ is in $(P(n),P(n)+1). $ Note that, $P(n)\le\,P(n+1)\le\,P(n)+1. $ So, if $T(x)=P(x+1)-P(x) $ is constant $c $ in $[0,1].$ Substituting $x=1\implies c=\lfloor c\rfloor\implies c$ is an integer. Both $c=0,1. $ works. $c $ is an integer in $[0,1] $ so the only options are $0,1. $ Address the constant term which needs to be an integer. Only tried $f(x)=x $ and $f(x)=0$ clearly works.