علی می‌خواهد مقدار مبنای دوی اعداد ۳،۲،۱،… تا ۱۳۸۹ را به ترتیب در یک خط پشت سر هم و بدون فاصله بنویسد. منتهی چون جوهر خودکارش کم است، تصمیم می‌گیرد که یک ایده‌ی جالب بزند!

برای هر عدد $i$، بعد از آن‌که علی رشته‌ی مبنای دوی عدد $i$ را محاسبه کرد (فرض کنید طول این رشته $l$ باشد)، می‌خواهد کم‌ترین تعداد بیت (صفر یا یک) را به انتهای رشته‌ای که تا کنون نوشته شده بیافزاید، به طوری که $l$ بیت سمت راست این رشته، عینا معادل دودویی $i$ باشند.

با این روش، شرو دنباله به صورت $10110010110…$ خواهد بود؛ که ۱۱ بیت نوشته شده مقادیر مبنای دوی اعداد ۱ تا ۶ را به روش علی دارند.

طول این دنباله در نهایت، وقتی اعداد ۱ تا ۱۳۸۹ نوشته شد، را $L$ می‌نامیم. مقدار باقی‌مانده‌ی ($1389\times L$) بر $\Delta$ چند است؟

‎
 
#include <iostream>
#define SZ length()
using namespace std;
 
const int n = 1389;
const int delta = 90907;
 
string n2b(int x) {
  string s;
  for(; x; x/=2)
    s = string(1, '0'+(x%2)) + s;
  return s;
}
 
int main() {
  string r = "";
 
  for (int i=1; i<=n; i++) {
    string s = n2b(i);
    for (int k = max(0, (int)r.SZ-(int)s.SZ);
        k<(int)r.SZ; k++) {
      if (r.substr(k) == s.substr(0, r.SZ - k)) {
        r += s.substr(r.length() - k);
        goto nexti;
      }
    }
    r += s;
 
  nexti: ;
  }
 
  long long ans = r.length() * 1389;
  cout << (ans % delta) << endl;
 
  return 0;
}

• سوال بعد
• سوال قبل