fork download
  1. #define _CRT_SECURE_NO_WARNINGS
  2. #define NDEBUG
  3.  
  4. #include <string.h>
  5. #include <stdio.h>
  6. #include <ctype.h>
  7. #include <assert.h>
  8. #include <algorithm>
  9. #include <string>
  10. #include <vector>
  11. #include <future>
  12. #include <locale>
  13. #include <thread>
  14.  
  15. using namespace std;
  16.  
  17. inline long long ipow(long long x, long long p)
  18. {
  19. if (x == 0 || x == 1) return x;
  20. long long r = 1;
  21. while(p)
  22. {
  23. if (p&0x1) r*= x;
  24. x *= x;
  25. p >>= 1;
  26. }
  27. return r;
  28. }
  29.  
  30. inline unsigned long long isqrt(unsigned long long x)
  31. {
  32. unsigned long long x1, g0, g1;
  33. if (x <= 1) return x;
  34. int s = 1;
  35. x1 = x - 1;
  36. if (x1 > 0xFFFFFFFF) { s = s + 16; x1 >>= 32; }
  37. if (x1 > 0xFFFF) { s = s + 8; x1 >>= 16; }
  38. if (x1 > 0xFF) { s = s + 4; x1 >>= 8; }
  39. if (x1 > 0xF) { s = s + 2; x1 >>= 4; }
  40. if (x1 > 0x3) { s = s + 1; }
  41.  
  42. g0 = 1ll << s;
  43. g1 = (g0 +(x>>s)) >> 1;
  44. while( g1 < g0) {
  45. g0 = g1;
  46. g1 = (g0 + (x/g0)) >> 1;
  47. }
  48. return g0;
  49. }
  50.  
  51. long long fact(long long x)
  52. {
  53. assert(x <= 20);
  54. static long long vals[21] = {1,1,2,6,24,120,720,5040,0,0,0,0,0,0,0,0,0,0,0,0,0};
  55. if (vals[x]) return vals[x];
  56. long long s = 1;
  57. for(int i = 1; i <= x; ++i)
  58. {
  59. s *= i;
  60. vals[i] = s;
  61. }
  62. return s;
  63. }
  64.  
  65. long long bifact(long long x)
  66. {
  67. assert(x <= 32);
  68. static long long vals[33] = {1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0};
  69. if (vals[x]) return vals[x];
  70. long long s = 1;
  71. for(int i = 1; i <= 31; i += 2)
  72. {
  73. s *= i;
  74. vals[i] = s;
  75. }
  76. s = 1;
  77. for(int i = 2; i <= 32; i += 2)
  78. {
  79. s *= i;
  80. vals[i] = s;
  81. }
  82. return vals[x];
  83. }
  84.  
  85.  
  86.  
  87. typedef long long ALM_STYPE;
  88. static int alm_parse( void * alm_param );
  89.  
  90. #define Number 257
  91. #define Wrong 258
  92. #define uminus 259
  93. #define alm_IntError
  94. #define alm_clearin alm_char = -1
  95. #define alm_errok alm_errflag = 0
  96. #ifndef ALM_MAXDEPTH
  97. #define ALM_MAXDEPTH 150
  98. #endif
  99. #define ALM_ERRCODE 256
  100.  
  101.  
  102.  
  103. template< typename RandomAccess, typename Compare >
  104. bool next_kpermutation( RandomAccess first, RandomAccess last,
  105. typename std::iterator_traits< RandomAccess >::difference_type k,
  106. Compare comp )
  107. {
  108.  
  109. typedef typename std::iterator_traits< RandomAccess >::difference_type Int;
  110. typedef typename std::iterator_traits< RandomAccess >::value_type Val;
  111.  
  112. if( first == last ) return false;
  113. Int n = std::distance(first, last);
  114. if (k > n) return false;
  115.  
  116. //Int n = distance(first, last);
  117. //Int i = -1;
  118.  
  119. RandomAccess i = last;
  120. for(RandomAccess j = first + k - 1;
  121. j >= first; --j)
  122. {
  123. if (std::max_element(j,last) != j)
  124. {
  125. i = j;
  126. break;
  127. }
  128. }
  129.  
  130. if (i == last) return false;
  131.  
  132. {
  133. // Сначала ищем первый, больший p_[i]
  134. RandomAccess j = i;
  135. ++j;
  136. while(!comp(*i,*j)) ++j;
  137. RandomAccess imin = j; // Индекс минимального
  138. for(; j != last; ++j)
  139. {
  140. if (comp(*i,*j) &&
  141. comp(*j,*imin))
  142. {
  143. imin = j;
  144. }
  145. }
  146. std::swap( *i, *imin );
  147. ++i;
  148. }
  149.  
  150. RandomAccess u = first + std::min(k,n-1);
  151. while ( i < u )
  152. {
  153. RandomAccess imin = i;
  154. for(RandomAccess j = i + 1; j != last; ++j)
  155. {
  156. if (comp(*j,*imin)) imin = j;
  157. }
  158. std::swap( *i, *imin );
  159. ++i;
  160. }
  161.  
  162. return true;
  163. }
  164.  
  165. template< typename RandomAccess >
  166. bool next_kpermutation( RandomAccess first, RandomAccess last, int k )
  167. {
  168. return ( next_kpermutation( first, last, k,
  169. std::less< typename std::iterator_traits< RandomAccess >::value_type >( )
  170. ) );
  171. }
  172.  
  173. static void alm_error(int) {}
  174. static int alm_lex(void*qq,ALM_STYPE*alm_lval)
  175. {
  176. const char *& alm_textpointer = *(const char **)qq;
  177.  
  178. while(*alm_textpointer==' ' /*||*alm_textpointer=='\t' */) ++alm_textpointer;
  179. switch(*alm_textpointer)
  180. {
  181. case 0: return EOF;
  182. case '0':
  183. {
  184. if (isdigit(*(alm_textpointer+1))) return Wrong;
  185. }
  186. case '1':
  187. case '2':
  188. case '3':
  189. case '4':
  190. case '5':
  191. case '6':
  192. case '7':
  193. case '8':
  194. case '9':
  195. {
  196. *alm_lval = 0;
  197. while(*alm_textpointer >= '0' && *alm_textpointer <= '9')
  198. {
  199. *alm_lval = (*alm_lval)*10 + (*alm_textpointer - '0');
  200. ++alm_textpointer;
  201. }
  202. return Number;
  203. } break;
  204. case '*':
  205. if (*(alm_textpointer+1) == '*')
  206. {
  207. alm_textpointer += 2;
  208. return '^';
  209. }
  210. case '+':
  211. case '-':
  212. case '(':
  213. case ')':
  214. case '/':
  215. case '=':
  216. case '^':
  217. case ';':
  218. case '!':
  219. case '#':
  220. case '%':
  221. {
  222. *alm_lval = 0;
  223. return *alm_textpointer++;
  224. } break;
  225.  
  226. }
  227. ++alm_textpointer;
  228. return Wrong;
  229. }
  230.  
  231. mutex mx;
  232. int total_count = 0;
  233.  
  234. void almetis(int begin, int end,
  235. const char * buf, const char * symbols, int symno)
  236. {
  237. char digs[] = "0123456789";
  238. int no = 0;
  239. do {
  240. if (no >= end) break;
  241. if (no < begin) continue;
  242.  
  243. char stmt[2048];
  244. const char * c = buf;
  245. char * t = stmt;
  246. for(;*c; ++c,++t)
  247. {
  248. switch(*c)
  249. {
  250. case ' ':
  251. case '0':
  252. case '1':
  253. case '2':
  254. case '3':
  255. case '4':
  256. case '5':
  257. case '6':
  258. case '7':
  259. case '8':
  260. case '9':
  261. case '(':
  262. case ')':
  263. case '+':
  264. case '-':
  265. case '*':
  266. case '/':
  267. case '=':
  268. case '^':
  269. case ';':
  270. case '!':
  271. case '#':
  272. case '%':
  273. case '\t':
  274. case '\r':
  275. case '\n': *t = *c; break;
  276. default:
  277. for(int j = 0; j < symno; ++j)
  278. {
  279. if (*c == symbols[j])
  280. {
  281. *t = digs[j];
  282. break;
  283. }
  284. }
  285. }
  286. }
  287. *t = 0;
  288. const char * q = stmt;
  289. if (alm_parse(&q) == 0)
  290. {
  291. lock_guard<mutex> lk(mx);
  292. total_count++;
  293. printf("%s\n",stmt);
  294. }
  295. } while(++no, next_kpermutation(digs,digs+10,symno));
  296.  
  297. };
  298.  
  299.  
  300. int main(int argc, char* argv[])
  301. {
  302. setlocale(LC_ALL,"Rus");
  303. int threads = thread::hardware_concurrency();
  304. if (threads <= 1) threads = 1;
  305. else if (threads > 8) threads = 8;
  306. printf("Threads: %d\n",threads);
  307.  
  308. char buf[2048] = { 0 };
  309.  
  310. fgets(buf,2048,stdin);
  311.  
  312. char symbols[11] = { 0 };
  313. int symno = 0;
  314. for(const char * c = buf; *c; ++c)
  315. {
  316. if (strchr(" 01234567890()+-*/=^;#%!\t\r\n",*c)) continue;
  317. bool found = false;
  318. for(int j = 0; j < symno; ++j)
  319. if (symbols[j] == *c)
  320. {
  321. found = true;
  322. break;
  323. }
  324. if (!found) symbols[symno++] = *c;
  325. if (symno == 11)
  326. {
  327. fprintf(stderr,"Too many symbols\n");
  328. return 1;
  329. }
  330. }
  331.  
  332. printf("There are %d symbols: %s\n",symno,symbols);
  333.  
  334. int count = 1;
  335. for(int i = 0; i < symno; ++i) count *= (10-i);
  336.  
  337. if ((count < 5000) || (threads == 1))
  338. {
  339. almetis(0,count,buf,symbols,symno);
  340. }
  341. else
  342. {
  343. int part = count / threads;
  344. assert(threads * part == count);
  345.  
  346. vector<future<void>> fus;
  347. for(int i = 0; i < threads; ++i)
  348. {
  349. fus.push_back(async(almetis,i*part,(i+1)*part,buf,symbols,symno));
  350. }
  351. for(auto& x: fus) x.get();
  352. }
  353. printf("Solutions: %d\n",total_count);
  354. }
  355. static const int alm_exca[] ={
  356. -1, 1,
  357. 0, -1,
  358. -2, 0,
  359. };
  360.  
  361. #define ALM_NPROD 22
  362. #define ALM_LAST 228
  363. static const int alm_act[]={
  364.  
  365. 9, 13, 4, 2, 9, 10, 1, 20, 8, 10,
  366. 7, 21, 8, 0, 7, 33, 17, 15, 20, 16,
  367. 20, 19, 21, 0, 21, 20, 0, 17, 15, 21,
  368. 16, 0, 19, 5, 17, 15, 20, 16, 0, 19,
  369. 21, 0, 0, 6, 0, 17, 14, 26, 0, 0,
  370. 19, 22, 23, 24, 25, 0, 0, 0, 27, 28,
  371. 29, 30, 31, 32, 0, 0, 0, 0, 18, 0,
  372. 0, 0, 0, 0, 0, 0, 0, 0, 0, 18,
  373. 0, 18, 0, 0, 0, 0, 18, 0, 0, 0,
  374. 0, 0, 0, 0, 0, 0, 0, 18, 0, 0,
  375. 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
  376. 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
  377. 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
  378. 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
  379. 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
  380. 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
  381. 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
  382. 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
  383. 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
  384. 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
  385. 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
  386. 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
  387. 0, 3, 11, 12, 0, 0, 11, 12 };
  388.  
  389. static const int alm_pact[]={
  390.  
  391. -35, -1000, -1000, -1000, -58, -1000, -15, -31, -31, -31,
  392. -31, -1000, -1000, -31, -31, -31, -31, -31, -31, -31,
  393. -1000, -1000, -13, -13, -1000, -26, -1000, -8, 3, 3,
  394. -13, -13, -13, -1000 };
  395.  
  396. static const int alm_pgo[]={
  397.  
  398. 0, 6, 3, 2, 33, 43 };
  399.  
  400. static const int alm_r1[]={
  401.  
  402. 0, 1, 1, 2, 2, 3, 3, 4, 4, 5,
  403. 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
  404. 5, 5 };
  405.  
  406. static const int alm_r2[]={
  407.  
  408. 0, 1, 1, 1, 2, 3, 1, 3, 1, 3,
  409. 3, 2, 2, 3, 3, 3, 2, 2, 2, 3,
  410. 1, 1 };
  411.  
  412. static const int alm_chk[]={
  413.  
  414. -1000, -1, -2, 256, -3, -4, -5, 45, 43, 35,
  415. 40, 257, 258, 59, 61, 43, 45, 42, 94, 47,
  416. 33, 37, -5, -5, -5, -5, -4, -5, -5, -5,
  417. -5, -5, -5, 41 };
  418.  
  419. static const int alm_def[]={
  420.  
  421. 0, -2, 1, 2, 3, 6, 8, 0, 0, 0,
  422. 0, 20, 21, 4, 0, 0, 0, 0, 0, 0,
  423. 16, 17, 11, 12, 18, 0, 5, 7, 9, 10,
  424. 13, 14, 15, 19 };
  425.  
  426. #define YACC_MEM_STACK
  427. //#define alm_IntError
  428.  
  429. #ifdef alm_IntError
  430. #define alm_errNoMemory -1
  431. #define alm_errStackOvr -2
  432. #define alm_errSyntax -3
  433. #else
  434. #define alm_errNoMemory "not enough memory"
  435. #define alm_errStackOvr "internal stack overflow"
  436. #define alm_errSyntax "syntax error"
  437. #endif
  438.  
  439. #define ALM_FLAG (-1000)
  440. #define ALM_ERROR goto alm_errlab
  441. #define ALM_ACCEPT return(0)
  442. #define ALM_ABORT return(1)
  443.  
  444. #if defined(YACC_MEM_HEAP)
  445. template<typename T>
  446. class alm__memory
  447. {
  448. T * ptr_;
  449. public:
  450. alm__memory(unsigned int size)
  451. {
  452. ptr_ = new T[size];
  453. };
  454. ~alm__memory()
  455. {
  456. delete[] ptr_;
  457. };
  458. T* ptr()
  459. {
  460. return ptr_;
  461. };
  462. };
  463. #endif
  464.  
  465. static int alm_parse( void * alm_param )
  466. {
  467. ALM_STYPE alm_lval = ALM_STYPE(), alm_val = ALM_STYPE();
  468. int alm_char = -1;
  469. int alm_nerrs = 0;
  470. int alm_errflag = 0;
  471. #if defined(YACC_MEM_HEAP)
  472. int * alm_s;
  473. ALM_STYPE * alm_v;
  474. #endif
  475. #if defined(YACC_MEM_STACK)
  476. int alm_s[ALM_MAXDEPTH+2];
  477. ALM_STYPE alm_v[ALM_MAXDEPTH+2];
  478. #endif
  479. int alm_j, alm_m;
  480. ALM_STYPE * alm_pvt;
  481. int alm_state, *alm_ps, alm_n;
  482. ALM_STYPE * alm_pv;
  483. const int * alm_xi;
  484.  
  485. #if defined(YACC_MEM_HEAP)
  486. alm__memory<ALM_STYPE> ALM__M (ALM_MAXDEPTH+2);
  487. alm__memory<int > ALM__M1(ALM_MAXDEPTH+2);
  488.  
  489. alm_v = ALM__M.ptr();
  490. alm_s = ALM__M1.ptr();
  491.  
  492. if ((alm_v == NULL) || (alm_s == NULL))
  493. {
  494. alm_error(alm_errNoMemory);
  495. return(1);
  496. };
  497. #endif
  498.  
  499. alm_state = 0;
  500. alm_char = -1;
  501. alm_nerrs = 0;
  502. alm_errflag = 0;
  503. alm_ps = &alm_s[-1];
  504. alm_pv = &alm_v[-1];
  505.  
  506. alm_stack:
  507. if( ++alm_ps > &alm_s[ALM_MAXDEPTH] )
  508. {
  509. alm_error(alm_errStackOvr);
  510. return(1);
  511. }
  512. *alm_ps = alm_state;
  513. ++alm_pv;
  514. *alm_pv = alm_val;
  515.  
  516. alm_newstate:
  517. alm_n = alm_pact[alm_state];
  518. if( alm_n <= ALM_FLAG )
  519. goto alm_default;
  520. if( alm_char < 0 )
  521. if( (alm_char = (int )alm_lex(alm_param,&alm_lval)) < 0 )
  522. alm_char = 0;
  523. if( (alm_n += alm_char) < 0 || alm_n >= ALM_LAST )
  524. goto alm_default;
  525. if( alm_chk[alm_n = alm_act[alm_n]] == alm_char )
  526. {
  527. alm_char = -1;
  528. alm_val = alm_lval;
  529. alm_state = alm_n;
  530. if( alm_errflag > 0 )
  531. --alm_errflag;
  532. goto alm_stack;
  533. }
  534.  
  535. alm_default:
  536.  
  537. if( (alm_n = alm_def[alm_state]) == -2 )
  538. {
  539. if( alm_char < 0 )
  540. if( (alm_char = (int )alm_lex(alm_param,&alm_lval)) < 0 )
  541. alm_char = 0;
  542. for(alm_xi=alm_exca; (*alm_xi!=(-1)) || (alm_xi[1]!=alm_state);alm_xi+=2)
  543. ;
  544. while( *(alm_xi += 2) >= 0 )
  545. if( *alm_xi == alm_char )
  546. break;
  547. if( (alm_n = alm_xi[1]) < 0 )
  548. return(0);
  549. }
  550. if( alm_n == 0 )
  551. {
  552. switch( alm_errflag )
  553. {
  554. case 0:
  555. alm_error(alm_errSyntax);
  556. alm_errlab:
  557. ++alm_nerrs;
  558. case 1:
  559. case 2:
  560. alm_errflag = 3;
  561. while ( alm_ps >= alm_s )
  562. {
  563. alm_n = alm_pact[*alm_ps] + ALM_ERRCODE;
  564. if( alm_n >= 0 && alm_n < ALM_LAST &&
  565. alm_chk[alm_act[alm_n]] == ALM_ERRCODE )
  566. {
  567. alm_state = alm_act[alm_n];
  568. goto alm_stack;
  569. }
  570. alm_n = alm_pact[*alm_ps];
  571. --alm_ps;
  572. --alm_pv;
  573. }
  574. alm_abort:
  575. return(1);
  576. case 3:
  577. if( alm_char == 0 )
  578. goto alm_abort;
  579. alm_char = -1;
  580. goto alm_newstate;
  581. }
  582. }
  583. alm_ps -= alm_r2[alm_n];
  584. alm_pvt = alm_pv;
  585. alm_pv -= alm_r2[alm_n];
  586. alm_val = alm_pv[1];
  587. alm_m = alm_n;
  588. alm_n = alm_r1[alm_n];
  589. alm_j = alm_pgo[alm_n] + *alm_ps + 1;
  590. if( alm_j >= ALM_LAST || alm_chk[alm_state = alm_act[alm_j]] != -alm_n )
  591. alm_state = alm_act[alm_pgo[alm_n]];
  592. switch(alm_m)
  593. {
  594.  
  595.  
  596. case 1:{
  597. return alm_pvt[-0] ? 0 : -1;
  598. } break;
  599. case 2:{
  600. return -1;
  601. } break;
  602. case 3:{
  603. alm_val = alm_pvt[-0];
  604. } break;
  605. case 4:{
  606. alm_val = alm_pvt[-1];
  607. } break;
  608. case 5:{
  609. if (alm_pvt[-0] == 0) return -1;
  610. alm_val = alm_pvt[-2] && alm_pvt[-0];
  611. } break;
  612. case 6:{
  613. if (alm_pvt[-0] == 0) return -1;
  614. alm_val = alm_pvt[-0];
  615. } break;
  616. case 7:{
  617. alm_val = (alm_pvt[-2] == alm_pvt[-0]) ? 1 : 0;
  618. } break;
  619. case 8:{
  620. alm_val = (alm_pvt[-0] == 0) ? 1 : 0;
  621. } break;
  622. case 9:{
  623. alm_val = alm_pvt[-2] + alm_pvt[-0];
  624. } break;
  625. case 10:{
  626. alm_val = alm_pvt[-2] - alm_pvt[-0];
  627. } break;
  628. case 11:{
  629. alm_val = -alm_pvt[-0];
  630. } break;
  631. case 12:{
  632. alm_val = alm_pvt[-0];
  633. } break;
  634. case 13:{
  635. alm_val = alm_pvt[-2] * alm_pvt[-0];
  636. } break;
  637. case 14:{
  638. if (alm_pvt[-0] < 0) return -1;
  639. alm_val = 1;
  640. for(int i = 0; i < alm_pvt[-0]; ++i) alm_val *= alm_pvt[-2];
  641. } break;
  642. case 15:{
  643. if (alm_pvt[-0] == 0) return -1;
  644. alm_val = alm_pvt[-2] / alm_pvt[-0];
  645. if (alm_val*alm_pvt[-0] != alm_pvt[-2]) return -1;
  646. } break;
  647. case 16:{
  648. if (alm_pvt[-1] < 0) return -1;
  649. if (alm_pvt[-1] >=20) return -1;
  650. alm_val = fact(alm_pvt[-1]);
  651. } break;
  652. case 17:{
  653. if (alm_pvt[-1] < 0) return -1;
  654. if (alm_pvt[-1] >=33) return -1;
  655. alm_val = bifact(alm_pvt[-1]);
  656. } break;
  657. case 18:{
  658. if (alm_pvt[-1] < 0) return -1;
  659. alm_val = isqrt(alm_pvt[-0]);
  660. if (alm_val*alm_val != alm_pvt[-0]) return -1;
  661. } break;
  662. case 19:{
  663. alm_val = alm_pvt[-1];
  664. } break;
  665. case 20:{
  666. alm_val = alm_pvt[-0];
  667. } break;
  668. case 21:{
  669. return -1;
  670. } break;
  671.  
  672. }
  673. goto alm_stack;
  674. }
  675.  
Success #stdin #stdout 0.9s 4296KB
stdin
VOLVO+FIAT=MOTOR
stdout
Threads: 8
There are 9 symbols: VOLFIATMR
15615+9743=25358

15715+9643=25358

46346+9821=56167

46846+9321=56167

71571+9642=81213

71671+9542=81213

36736+9825=46561

36836+9725=46561

72472+9651=82123

72672+9451=82123

Solutions: 10