المپدیا

دانش‌نامه‌ی المپیاد کامپیوتر ایران

ابزار کاربر

ابزار سایت


سوالات المپیاد:مرحله‌ی سوم:دوره‌ی ۲۰:سوال ۲

شماره تلفن رند

یک شماره تلفن ۷ رقمی را رند می‌گوییم اگر بتوان ارقام آن را به صورت $\underline{a \quad bbb \quad ccc}$ یا $\underline{aaa \quad b \quad ccc}$ یا $\underline{aaa \quad bbb \quad c}$ یا $\underline{aa \quad bb \quad ccc}$ یا $\underline{aa \quad bbb \quad cc}$ یا $\underline{aaa \quad bb \quad cc}$ یا $\underline{abababa}$ نوشت که $a$، $b$ و $c$ ارقام یک رقمی نه لزوما متمایز هستند.

برای مثال شماره‌های ۹۹۲۲۶۶۶ و ۳۳۳۰۳۳۳ و ۴۴۴۴۴۴۴ همگی رند هستند. ولی شماره‌های ۹۲۲۳۳۲۲ و ۹۱۲۰۹۱۲ و ۱۲۳۴۳۲۱ هیچ یک رند نیستند.

تعداد شماره‌های رندی که با صفر شروع نشوند و عدد ۷ رقمی متناظر آن‌ها از ۷۸۰۱۳۸۹ کوچک‌تر باشد، چند تا است؟ اگر این تعداد را $M$ بنامیم، باقی‌مانده‌ی تقسیم $M^2$ بر $\Delta$ چند است؟

پاسخ

‎
 
 
#include <iostream>
#include <set>
using namespace std;
 
typedef long long LL;
 
const string paterns[] = {"abbbccc",
       "aaabccc", "aaabbbc", "aabbccc",
       "aabbbcc", "aaabbcc", "abababa"};
const int delta = 90907;
 
int main() {
  int np = sizeof(paterns) / sizeof(paterns[1]);
 
  set<string> myset;
 
  int d[3];
  for (d[0] = 0; d[0] <= 9; d[0]++)
    for (d[1] = 0; d[1] <= 9; d[1]++)
      for (d[2] = 0; d[2] <= 9; d[2]++)
        for (int k=0; k<np; k++) {
          string s = paterns[k];
          for (int i=0; i<(int)s.length(); i++)
            s[i] = '0'+d[s[i]-'a'];
          if (s < "7801389" && s[0] != '0')
            myset.insert(s);
        }
 
  LL cnt = myset.size();
  cout << (cnt*cnt) % delta << endl;
 
  return 0;
}

ابزار صفحه