For all $x_i\in A_i$, consider the function $f(x_1,x_2,\ldots,x_n)=x_1+x_2+\cdots+x_n$. We want to find the smallest $k$ such that the image of $f$ includes all the numbers $0,1,2,\ldots,n-1.$ The optimal size of the image occurs when $f$ is injective, but even assuming this, we have that the image of $f$ is at most $k^r.$ So if $k^r<n$, then there are $x\in [0,n-1]$ which cannot be computed. Now consider $k=\lceil n^{\frac{1}{r}}\rceil$. If we show this is possible, we are done. So consider the $r$ sets $A_1=\{0,1,\ldots,k-1\}$, $A_2=\{0,k,2k,\ldots,k(k-1)\}$, $\ldots$ $A_r=\{0,k^{r-1},2k^{r-1},\ldots,(k-1)k^{r-1}\}$. Finally, if any of the elements of $A_r$ are greater than $n-1$, then simply replace them, by say, $1.$ It is not hard to show that this is equivalent to writing $x$ in base $k$ with $r$ digits, and in fact all $x\in [0,n-1]$.