A Kac ring is a dynamical system defined as follows:
- there are N points x0,…,xN−1x_0, …, x_{N-1}x0,…,xN−1 arranged in a circle, numbered clockwise.
- each point is occupied by either a white ball or a black ball.
- in addition, M of these points are “marked.”
- at each step, balls are moved one step clockwise, i.e. x0→x1,x1→x2,…,xN−1→x0x_0 \to x_1, x_1 \to x_2, …, x_{N-1} \to x_0x0→x1,x1→x2,…,xN−1→x0.
- if a ball leaves a marked point, it changes color. For example, if at time ttt the ball at point xix_ixi is white and xix_ixi is marked, then at time t+1t+1t+1 the ball at xi+1x_{i+1}xi+1 is now black. If point xjx_jxj is not marked, then at t+1t+1t+1 the ball at xj+1x_{j+1}xj+1 keeps its color.
Part 1: Implement a Kac ring with the following interface:
- The initializer accepts N (number of points) and a sorted list of marked points 0≤y1<…<ym<N0 \le y_1 < … < y_m < N0≤y1<…<ym<N. All points start white.
step()advances the model one step.color()returns the ratio (W−B)/N(W – B) / N(W−B)/N, where W is the number of white balls and B is the number of black balls. This method should be O(1).
N 个点环形排列，部分位置被标记。每一步所有球顺时针移动一格；若从“被标记”位置离开则翻转颜色。实现类：初始化 (N、已标记点列表)、step() 前进一步、color() 以 O(1) 返回 (白球数−黑球数)/N(白球数 - 黑球数)/N(白球数−黑球数)/N。考点：环形索引、翻转规则、用计数 / 差分实现 O(1) 统计。
VOprep 团队长期陪同学员实战各类大厂 OA 与 VO，包括 Voleon、Google、Amazon、Citadel、SIG 等，提供实时答案助攻、远程陪练与面试节奏提醒，帮助大家在关键时刻不卡壳。
如果你也在准备 Tiktok 或类似工程向公司，可以了解一下我们的定制助攻方案——从编程面到系统设计，全程护航上岸。
正文完
