سربازها

۱۳۸۹ سرباز در یک سطر ایستاده‌اند به طوری که سربازهایی که اندیس‌شان، از سمت چپ، یک عدد اول است رو به راست ($R$) و سایر سربازها رو به چپ ($L$) هستند. یعنی صف ما چنین است: $LRRLRLRLLL…L$.

هر بار که سوت زده می‌شود، هر دو سربازی که «چشم تو چشم» هم باشند، جای‌شان را با هم عوض می‌کنند (فقط یک مرحله در هر سوت). به عنوان مثال اگر جایی به صورت $...R\underline{R}LL\underline{R}LR…$ باشیم، پس از یک سوت ترتیب همین تکه از دنباله به صورت $...RL\underline{R}LL\underline{R}?...$ خواهد بود. (برخی سربازهای جابه‌جا شده متناظر، مشخص شده‌اند).

فرض کنید پس از زدن $S$ بار سوت، به ترتیبی رسیده‌ایم که می‌توان فهمید دیگر سوت زدن فایده‌ای ندارد! در این صورت، مقدار باقی‌مانده‌ی تقسیم عدد $R=(S+S^2+S^3)$ بر $\Delta$ چند است؟

‎
 
 
#include <iostream>
using namespace std;
 
bool isPrime(int x) {
  if (x < 2) return false;       
  for (int i=2; i*i<=x; i++) 
    if (x % i == 0)
      return false;  
  return true;
}
 
const int n = 1389;
const int delta = 90907;
 
int main() {
  bool r[n+1]; // looking to right
  for (int i=0; i<n; i++)    
    r[i] = isPrime(i+1);
 
  bool changed = true;
  long long t = 0;
  for (t = 0; ; t++) {
    changed = false;
    for (int i=0; i<n-1; i++)
      if (r[i] && !r[i+1])
        { swap(r[i], r[i+1]); i++; changed=true; }
 
    if (!changed) break;  
  }
 
  long long R = t + t*t + t*t*t;
  cout << (R % delta) << endl;
 
  return 0;
}

• سوال بعد