Anna3O0

Backtracking

Feb 27th, 2021 (edited)
970
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. //                                           --------GENERARE PERMUTARI---------
  2. #include <iostream>
  3.  
  4. using namespace std;
  5.  
  6. int n,s[100];
  7.  
  8. void init(int k)
  9. {
  10.     s[k]=0;
  11. }
  12.  
  13. int succesor(int k)
  14. {
  15.     if(s[k]<n)
  16.     {
  17.         s[k]++;
  18.         return 1;
  19.     }
  20.     return 0;
  21. }
  22.  
  23. int valid(int k)//sa nu se afle sk de 2 ori in solutie
  24. {
  25.     int i;
  26.     for(i=1;i<k;i++)
  27.         if(s[i]==s[k])
  28.             return 0;
  29.     return 1;
  30. }
  31.  
  32. int solutie(int k)//sa aiba nr acelasi nr de elem
  33. {
  34.     if(k==n)
  35.         return 1;
  36.     return 0;
  37. }
  38.  
  39. void tipar(int k)
  40. {
  41.     int i;
  42.     for(i=1;i<=k;i++)
  43.         cout<<s[i]<<" ";
  44.     cout<<endl;
  45. }
  46.  
  47. void bkt(int k)
  48. {
  49.     int as,ev;
  50.     init(k);
  51.     while(k>0)
  52.     {
  53.         do
  54.         {
  55.             as=succesor(k);
  56.             if(as==1)
  57.                 ev=valid(k);
  58.         }while(as==1 && ev==0);
  59.         if(as==1)
  60.             if(solutie(k)==1)
  61.                 tipar(k);
  62.         else
  63.         {
  64.             k++;
  65.             init(k);
  66.         }
  67.         else
  68.             k--;
  69.     }
  70. }
  71.  
  72. int main()
  73. {
  74.     cin>>n;
  75.     bkt(1);
  76.     return 0;
  77. }
  78.  
  79. //                                 --------1 PE PRIMA POZITIE SI N PE ULTIMA---------
  80.  
  81. #include <iostream>
  82.  
  83. using namespace std;
  84.  
  85. int n,s[100];
  86.  
  87. void init(int k)
  88. {
  89.     s[k]=0;
  90. }
  91.  
  92. int succesor(int k)
  93. {
  94.     if(s[k]<n)
  95.     {
  96.         s[k]++;
  97.         return 1;
  98.     }
  99.     return 0;
  100. }
  101.  
  102. int valid(int k)
  103. {
  104.     int i;
  105.     if(k==1)
  106.         if(s[k]!=1)
  107.             return 0;
  108.     if(k==n)
  109.         if(s[k]!=n)
  110.             return 0;
  111.     for(i=1;i<k;i++)
  112.         if(s[i]==s[k])
  113.             return 0;
  114.     return 1;
  115. }
  116.  
  117. int solutie(int k)
  118. {
  119.     if(k==n)
  120.         return 1;
  121.     return 0;
  122. }
  123.  
  124. void tipar(int k)
  125. {
  126.     int i;
  127.     for(i=1;i<=k;i++)
  128.         cout<<s[i]<<" ";
  129.     cout<<endl;
  130. }
  131.  
  132. void bkt(int k)
  133. {
  134.     int as,ev;
  135.     init(k);
  136.     while(k>0)
  137.     {
  138.         do
  139.         {
  140.             as=succesor(k);
  141.             if(as==1)
  142.                 ev=valid(k);
  143.         }while(as==1 && ev==0);
  144.         if(as==1)
  145.             if(solutie(k)==1)
  146.                 tipar(k);
  147.         else
  148.         {
  149.             k++;
  150.             init(k);
  151.         }
  152.         else
  153.             k--;
  154.     }
  155. }
  156.  
  157. int main()
  158. {
  159.     cin>>n;
  160.     bkt(1);
  161.  
  162.     return 0;
  163. }
  164.  
  165. //                                 --------NU EXISTA 2 VALORI ALATURATE CONSECUTIVE---------
  166.  
  167. #include <iostream>
  168.  
  169. using namespace std;
  170.  
  171. int n,i,s[100];
  172.  
  173. void init(int k)
  174. {
  175.     s[k]=0;
  176. }
  177.  
  178. int succesor(int k)
  179. {
  180.     if(s[k]<n)
  181.     {
  182.         s[k]++;
  183.         return 1;
  184.     }
  185.     return 0;
  186. }
  187.  
  188. int valid(int k)
  189. {
  190.     int i;
  191.     if(k>1)
  192.         if(s[k]==s[k-1]+1 || s[k]==s[k-1]-1)
  193.             return 0;
  194.     for(i=1;i<k;i++)
  195.         if(s[i]==s[k])
  196.             return 0;
  197.     return 1;
  198. }
  199.  
  200. int solutie(int k)
  201. {
  202.     if(k==n)
  203.         return 1;
  204.     return 0;
  205. }
  206.  
  207. void tipar(int k)
  208. {
  209.     int i;
  210.     for(i=1;i<=k;i++)
  211.         cout<<s[i]<<" ";
  212.     cout<<endl;
  213. }
  214.  
  215. void bkt(int k)
  216. {
  217.     int as,ev;
  218.     init(k);
  219.     while(k>0)
  220.     {
  221.         do
  222.         {
  223.             as=succesor(k);
  224.             if(as==1)
  225.                 ev=valid(k);
  226.         }while(as==1 && ev==0);
  227.         if(as==1)
  228.             if(solutie(k)==1)
  229.                 tipar(k);
  230.         else
  231.         {
  232.             k++;
  233.             init(k);
  234.         }
  235.         else
  236.             k--;
  237.     }
  238. }
  239.  
  240. int main()
  241. {
  242.     cin>>n;
  243.     bkt(1);
  244.  
  245.     return 0;
  246. }
  247.  
  248. //                                 --------NU EXISTA PERMUTARE CU P[I]=I---------
  249.  
  250. #include <iostream>
  251.  
  252. using namespace std;
  253.  
  254. int n,s[100];
  255.  
  256. void init(int k)
  257. {
  258.     s[k]=0;
  259. }
  260.  
  261. int succesor(int k)
  262. {
  263.     if(s[k]<n)
  264.     {
  265.         s[k]++;
  266.         return 1;
  267.     }
  268.     return 0;
  269. }
  270.  
  271. int valid(int k)
  272. {
  273.     int i;
  274.     if(s[k]==k)
  275.         return 0;
  276.     for(i=1;i<k;i++)
  277.         if(s[i]==s[k])
  278.             return 0;
  279.     return 1;
  280. }
  281.  
  282. int solutie(int k)
  283. {
  284.     if(k==n)
  285.         return 1;
  286.     return 0;
  287. }
  288.  
  289. void tipar(int k)
  290. {
  291.     int i;
  292.     for(i=1;i<=k;i++)
  293.         cout<<s[i]<<" ";
  294.     cout<<endl;
  295. }
  296.  
  297. void bkt(int k)
  298. {
  299.     int as,ev;
  300.     init(k);
  301.     while(k>0)
  302.     {
  303.         do
  304.         {
  305.             as=succesor(k);
  306.             if(as==1)
  307.                 ev=valid(k);
  308.         }while(as==1 && ev==0);
  309.         if(as==1)
  310.             if(solutie(k)==1)
  311.                 tipar(k);
  312.         else
  313.         {
  314.             k++;
  315.             init(k);
  316.         }
  317.         else
  318.             k--;
  319.     }
  320. }
  321.  
  322. int main()
  323. {
  324.     cin>>n;
  325.     bkt(1);
  326.  
  327.     return 0;
  328. }
  329.  
  330. //                                 --------PE PRIMA POZITIE E N SI PE ULTIMA E N+P---------
  331.  
  332. #include <iostream>
  333.  
  334. using namespace std;
  335.  
  336. int n,s[100],p;
  337.  
  338. void init(int k)
  339. {
  340.     s[k]=n-1;
  341. }
  342.  
  343. int succesor(int k)
  344. {
  345.     if(s[k]<n+p)
  346.     {
  347.         s[k]++;
  348.         return 1;
  349.     }
  350.     return 0;
  351. }
  352.  
  353. int valid(int k)
  354. {
  355.     int i;
  356.     if(k==1)
  357.         if(s[k]!=n)
  358.             return 0;
  359.     if(k>1)
  360.         if(s[k]<=s[k-1])
  361.             return 0;
  362.     return 1;
  363. }
  364.  
  365. int solutie(int k)
  366. {
  367.     if(s[k]==n+p)
  368.         return 1;
  369.     return 0;
  370. }
  371.  
  372. void tipar(int k)
  373. {
  374.     int i;
  375.     for(i=1;i<=k;i++)
  376.         cout<<s[i]<<" ";
  377.     cout<<endl;
  378. }
  379.  
  380. void bkt(int k)
  381. {
  382.     int as,ev;
  383.     init(k);
  384.     while(k>0)
  385.     {
  386.         do
  387.         {
  388.             as=succesor(k);
  389.             if(as==1)
  390.                 ev=valid(k);
  391.         }while(as==1 && ev==0);
  392.         if(as==1)
  393.             if(solutie(k)==1)
  394.                 tipar(k);
  395.         else
  396.         {
  397.             k++;
  398.             init(k);
  399.         }
  400.         else
  401.             k--;
  402.     }
  403. }
  404.  
  405. int main()
  406. {
  407.     cin>>n>>p;
  408.     bkt(1);
  409.  
  410.     return 0;
  411. }
  412.  
  413. //                                 --------2 NU ESTE INSCRIPTIONAT INAINTE DE 1---------
  414.  
  415. #include <iostream>
  416.  
  417. using namespace std;
  418.  
  419. int n,s[100];
  420.  
  421. void init(int k)
  422. {
  423.     s[k]=0;
  424. }
  425.  
  426. int succesor(int k)
  427. {
  428.     if(s[k]<n)
  429.     {
  430.         s[k]++;
  431.         return 1;
  432.     }
  433.     return 0;
  434. }
  435.  
  436. int valid(int k)
  437. {
  438.     int i;
  439.     if(s[k]==1)
  440.         for(i=1;i<k;i++)
  441.             if(s[i]==2)
  442.                 return 0;
  443.     for(i=1;i<k;i++)
  444.         if(s[i]==s[k])
  445.             return 0;
  446.     return 1;
  447. }
  448.  
  449. int solutie(int k)
  450. {
  451.     if(k==n)
  452.         return 1;
  453.     return 0;
  454. }
  455.  
  456. void tipar(int k)
  457. {
  458.     int i;
  459.     for(i=1;i<=k;i++)
  460.         cout<<s[i]<<" ";
  461.     cout<<endl;
  462. }
  463.  
  464. void bkt(int k)
  465. {
  466.     int as,ev;
  467.     init(k);
  468.     while(k>0)
  469.     {
  470.         do
  471.         {
  472.             as=succesor(k);
  473.             if(as==1)
  474.                 ev=valid(k);
  475.         }while(as==1 && ev==0);
  476.         if(as==1)
  477.             if(solutie(k)==1)
  478.                 tipar(k);
  479.         else
  480.         {
  481.             k++;
  482.             init(k);
  483.         }
  484.         else
  485.             k--;
  486.     }
  487. }
  488.  
  489. int main()
  490. {
  491.     cin>>n;
  492.     bkt(1);
  493.     return 0;
  494. }
  495.  
  496. //                                 --------DRAPELUL CU 3 CULORI NU ARE VOIE SA AIBA IN MIJLOC 1 SAU 4---------
  497.  
  498. #include <iostream>
  499.  
  500. using namespace std;
  501.  
  502. int n,s[100];
  503.  
  504. void init(int k)
  505. {
  506.     s[k]=0;
  507. }
  508.  
  509. int succesor(int k)
  510. {
  511.     if(s[k]<n)
  512.     {
  513.         s[k]++;
  514.         return 1;
  515.     }
  516.     return 0;
  517. }
  518.  
  519. int valid(int k)
  520. {
  521.     int i;
  522.     if(k==2)
  523.         if(s[k]==1 || s[k]==4)
  524.             return 0;
  525.     for(i=1;i<k;i++)
  526.         if(s[i]==s[k])
  527.             return 0;
  528.     return 1;
  529. }
  530.  
  531. int solutie(int k)
  532. {
  533.     if(k==3)
  534.         return 1;
  535.     return 0;
  536. }
  537.  
  538. void tipar(int k)
  539. {
  540.     int i;
  541.     for(i=1;i<=k;i++)
  542.     {
  543.         if(s[i]==1)
  544.             cout<<"galben ";
  545.         if(s[i]==2)
  546.             cout<<"portocaliu ";
  547.         if(s[i]==3)
  548.             cout<<"rosu ";
  549.         if(s[i]==4)
  550.             cout<<"visiniu ";
  551.         if(s[i]==5)
  552.             cout<<"verde ";
  553.         if(s[i]==6)
  554.             cout<<"albastru ";
  555.     }
  556.     cout<<endl;
  557. }
  558.  
  559. void bkt(int k)
  560. {
  561.     int as,ev;
  562.     init(k);
  563.     while(k>0)
  564.     {
  565.         do
  566.         {
  567.             as=succesor(k);
  568.             if(as==1)
  569.                 ev=valid(k);
  570.         }while(as==1 && ev==0);
  571.         if(as==1)
  572.             if(solutie(k)==1)
  573.                 tipar(k);
  574.         else
  575.         {
  576.             k++;
  577.             init(k);
  578.         }
  579.         else
  580.             k--;
  581.     }
  582. }
  583.  
  584. int main()
  585. {
  586.     cin>>n;
  587.     bkt(1);
  588.     return 0;
  589. }
  590.  
  591. //                                 --------NU EXISTA 2 VALORI ALATURATE CONSECUTIVE---------
  592.  
  593. #include <iostream>
  594.  
  595. using namespace std;
  596.  
  597. int n,i,s[100],v[100];
  598.  
  599. void init(int k)
  600. {
  601.     s[k]=0;
  602. }
  603.  
  604. int succesor(int k)
  605. {
  606.     if(s[k]<n)
  607.     {
  608.         s[k]++;
  609.         return 1;
  610.     }
  611.     return 0;
  612. }
  613.  
  614. int valid(int k)
  615. {
  616.     int i;
  617.     for(i=1;i<k;i++)
  618.         if(s[i]==s[k])
  619.             return 0;
  620.     return 1;
  621. }
  622.  
  623. int solutie(int k)
  624. {
  625.     if(k==n)
  626.         return 1;
  627.     return 0;
  628. }
  629.  
  630. void tipar(int k)
  631. {
  632.     int i;
  633.     for(i=1;i<=k;i++)
  634.         cout<<v[s[i]]<<" ";
  635.     cout<<endl;
  636. }
  637.  
  638. void bkt(int k)
  639. {
  640.     int as,ev;
  641.     init(k);
  642.     while(k>0)
  643.     {
  644.         do
  645.         {
  646.             as=succesor(k);
  647.             if(as==1)
  648.                 ev=valid(k);
  649.         }while(as==1 && ev==0);
  650.         if(as==1)
  651.             if(solutie(k)==1)
  652.                 tipar(k);
  653.         else
  654.         {
  655.             k++;
  656.             init(k);
  657.         }
  658.         else
  659.             k--;
  660.     }
  661. }
  662.  
  663. int main()
  664. {
  665.     cin>>n;
  666.     for(i=1;i<=n;i++)
  667.         cin>>v[i];
  668.     bkt(1);
  669.     return 0;
  670. }
  671.  
  672. //                                 --------NU EXISTA 2 VALORI ALATURATE CU ACEEASI PARITATE---------
  673.  
  674. #include <iostream>
  675.  
  676. using namespace std;
  677.  
  678. int n,i,s[100],v[100];
  679.  
  680. void init(int k)
  681. {
  682.     s[k]=0;
  683. }
  684.  
  685. int succesor(int k)
  686. {
  687.     if(s[k]<n)
  688.     {
  689.         s[k]++;
  690.         return 1;
  691.     }
  692.     return 0;
  693. }
  694.  
  695. int valid(int k)
  696. {
  697.     int i;
  698.     if(k>1)
  699.         if(v[s[k-1]]%2==v[s[k]]%2)
  700.             return 0;
  701.     for(i=1;i<k;i++)
  702.         if(s[i]==s[k])
  703.             return 0;
  704.     return 1;
  705. }
  706.  
  707. int solutie(int k)
  708. {
  709.     if(k==n)
  710.         return 1;
  711.     return 0;
  712. }
  713.  
  714. void tipar(int k)
  715. {
  716.     int i;
  717.     for(i=1;i<=k;i++)
  718.         cout<<v[s[i]]<<" ";
  719.     cout<<endl;
  720. }
  721.  
  722. void bkt(int k)
  723. {
  724.     int as,ev;
  725.     init(k);
  726.     while(k>0)
  727.     {
  728.         do
  729.         {
  730.             as=succesor(k);
  731.             if(as==1)
  732.                 ev=valid(k);
  733.         }while(as==1 && ev==0);
  734.         if(as==1)
  735.             if(solutie(k)==1)
  736.                 tipar(k);
  737.         else
  738.         {
  739.             k++;
  740.             init(k);
  741.         }
  742.         else
  743.             k--;
  744.     }
  745. }
  746.  
  747. int main()
  748. {
  749.     cin>>n;
  750.     for(i=1;i<=n;i++)
  751.         cin>>v[i];
  752.     bkt(1);
  753.     return 0;
  754. }
  755.  
  756. //                                 --------GENERARE ARANJAMENTE---------
  757.  
  758. #include <iostream>
  759.  
  760. using namespace std;
  761.  
  762. int n,s[100],p;
  763.  
  764. void init(int k)
  765. {
  766.     s[k]=0;
  767. }
  768.  
  769. int succesor(int k)
  770. {
  771.     if(s[k]<n)
  772.     {
  773.         s[k]++;
  774.         return 1;
  775.     }
  776.     return 0;
  777. }
  778.  
  779. int valid(int k)
  780. {
  781.     int i;
  782.     for(i=1;i<k;i++)
  783.         if(s[i]==s[k])
  784.             return 0;
  785.     return 1;
  786. }
  787.  
  788. int solutie(int k)
  789. {
  790.     if(k==p)
  791.         return 1;
  792.     return 0;
  793. }
  794.  
  795. void tipar(int k)
  796. {
  797.     int i;
  798.     for(i=1;i<=k;i++)
  799.         cout<<s[i]<<" ";
  800.     cout<<endl;
  801. }
  802.  
  803. void bkt(int k)
  804. {
  805.     int as,ev;
  806.     init(k);
  807.     while(k>0)
  808.     {
  809.         do
  810.         {
  811.             as=succesor(k);
  812.             if(as==1)
  813.                 ev=valid(k);
  814.         }while(as==1 && ev==0);
  815.         if(as==1)
  816.             if(solutie(k)==1)
  817.                 tipar(k);
  818.         else
  819.         {
  820.             k++;
  821.             init(k);
  822.         }
  823.         else
  824.             k--;
  825.     }
  826. }
  827.  
  828. int main()
  829. {
  830.     cin>>n>>p;
  831.     bkt(1);
  832.     return 0;
  833. }
  834.  
  835. //                                 --------TOATE NR DE N CIFRE DIVIZIBILE CU 3---------
  836.  
  837. #include <iostream>
  838.  
  839. using namespace std;
  840.  
  841. int n,i,s1,s[100];
  842.  
  843. void init(int k)
  844. {
  845.     s[k]=-1;
  846. }
  847.  
  848. int succesor(int k)
  849. {
  850.     if(s[k]<9)
  851.     {
  852.         s[k]++;
  853.         return 1;
  854.     }
  855.     return 0;
  856. }
  857.  
  858. int valid(int k)
  859. {
  860.     int i;
  861.     if(k==1)
  862.         if(s[k]==0)
  863.             return 0;
  864.     for(i=1;i<k;i++)
  865.         if(s[i]==s[k])
  866.             return 0;
  867.     return 1;
  868. }
  869.  
  870. int solutie(int k)
  871. {
  872.     if(k==n)
  873.         return 1;
  874.     return 0;
  875. }
  876.  
  877. int suma(int k)
  878. {
  879.     int s1=0;
  880.     for(i=1;i<=k;i++)
  881.          s1+=s[i];
  882.     return s1;
  883. }
  884.  
  885. void tipar(int k)
  886. {
  887.     int i;
  888.     if(suma(k)%3==0)
  889.     {
  890.         for(i=1;i<=k;i++)
  891.             cout<<s[i]<<" ";
  892.         cout<<endl;
  893.     }
  894. }
  895.  
  896. void bkt(int k)
  897. {
  898.     int as,ev;
  899.     init(k);
  900.     while(k>0)
  901.     {
  902.         do
  903.         {
  904.             as=succesor(k);
  905.             if(as==1)
  906.                 ev=valid(k);
  907.         }while(as==1 && ev==0);
  908.         if(as==1)
  909.             if(solutie(k)==1)
  910.                 tipar(k);
  911.         else
  912.         {
  913.             k++;
  914.             init(k);
  915.         }
  916.         else
  917.             k--;
  918.     }
  919. }
  920.  
  921. int main()
  922. {
  923.     cin>>n;
  924.     bkt(1);
  925.     return 0;
  926. }
  927.  
  928. //                                 --------CIFRELE IN ORDINE CRESCATOARE CARE CONTIN 3---------
  929.  
  930. #include <iostream>
  931.  
  932. using namespace std;
  933.  
  934. int n,s[100];
  935.  
  936. void init(int k)
  937. {
  938.     s[k]=-1;
  939. }
  940.  
  941. int succesor(int k)
  942. {
  943.     if(s[k]<n)
  944.     {
  945.         s[k]++;
  946.         return 1;
  947.     }
  948.     return 0;
  949. }
  950.  
  951. int valid(int k)
  952. {
  953.     int i;
  954.     if(k==1)
  955.         if(s[k]==0)
  956.             return 0;
  957.     if(k>1)
  958.         if(s[k-1]>=s[k])
  959.             return 0;
  960.     return 1;
  961. }
  962.  
  963. int solutie(int k)
  964. {
  965.     if(k==n)
  966.         return 1;
  967.     return 0;
  968. }
  969.  
  970. int verific(int k)
  971. {
  972.     int i;
  973.     for(i=1;i<=k;i++)
  974.         if(s[i]==3)
  975.             return 1;
  976.     return 0;
  977. }
  978.  
  979. void tipar(int k)
  980. {
  981.     int i;
  982.     if(verific(k)==1)
  983.     {
  984.         for(i=1;i<=k;i++)
  985.             cout<<s[i]<<" ";
  986.         cout<<endl;
  987.     }
  988. }
  989.  
  990. void bkt(int k)
  991. {
  992.     int as,ev;
  993.     init(k);
  994.     while(k>0)
  995.     {
  996.         do
  997.         {
  998.             as=succesor(k);
  999.             if(as==1)
  1000.                 ev=valid(k);
  1001.         }while(as==1 && ev==0);
  1002.         if(as==1)
  1003.             if(solutie(k)==1)
  1004.                 tipar(k);
  1005.         else
  1006.         {
  1007.             k++;
  1008.             init(k);
  1009.         }
  1010.         else
  1011.             k--;
  1012.     }
  1013. }
  1014.  
  1015. int main()
  1016. {
  1017.     cin>>n;
  1018.     bkt(1);
  1019.     return 0;
  1020. }
  1021.  
  1022. //                                 --------TOATE NR CARE NU CONTIN 3 CIFRE PARE SAU 3 CIFRE IMPARE ALATURATE---------
  1023.  
  1024. #include <iostream>
  1025.  
  1026. using namespace std;
  1027.  
  1028. int n,s[100];
  1029.  
  1030. void init(int k)
  1031. {
  1032.     s[k]=0;
  1033. }
  1034.  
  1035. int succesor(int k)
  1036. {
  1037.     if(s[k]<n)
  1038.     {
  1039.         s[k]++;
  1040.         return 1;
  1041.     }
  1042.     return 0;
  1043. }
  1044.  
  1045. int valid(int k)
  1046. {
  1047.     int i;
  1048.     if(k==1)
  1049.         if(s[k]==0)
  1050.             return 0;
  1051.     if(s[k-2]%2==s[k-1]%2 && s[k-1]%2==s[k]%2)
  1052.         return 0;
  1053.     return 1;
  1054. }
  1055.  
  1056. int solutie(int k)
  1057. {
  1058.     if(k==n)
  1059.         return 1;
  1060.     return 0;
  1061. }
  1062.  
  1063. void tipar(int k)
  1064. {
  1065.     int i;
  1066.     for(i=1;i<=k;i++)
  1067.         cout<<s[i]<<" ";
  1068.     cout<<endl;
  1069. }
  1070.  
  1071. void bkt(int k)
  1072. {
  1073.     int as,ev;
  1074.     init(k);
  1075.     while(k>0)
  1076.     {
  1077.         do
  1078.         {
  1079.             as=succesor(k);
  1080.             if(as==1)
  1081.                 ev=valid(k);
  1082.         }while(as==1 && ev==0);
  1083.         if(as==1)
  1084.             if(solutie(k)==1)
  1085.                 tipar(k);
  1086.         else
  1087.         {
  1088.             k++;
  1089.             init(k);
  1090.         }
  1091.         else
  1092.             k--;
  1093.     }
  1094. }
  1095.  
  1096. int main()
  1097. {
  1098.     cin>>n;
  1099.     bkt(1);
  1100.     return 0;
  1101. }
  1102.  
  1103. //                                 --------GENERARE COMBINARI---------
  1104.  
  1105. #include <iostream>
  1106.  
  1107. using namespace std;
  1108.  
  1109. int n,p,s[100];
  1110.  
  1111. void init(int k)
  1112. {
  1113.     s[k]=0;
  1114. }
  1115.  
  1116. int succesor(int k)
  1117. {
  1118.     if(s[k]<n)
  1119.     {
  1120.         s[k]++;
  1121.         return 1;
  1122.     }
  1123.     return 0;
  1124. }
  1125.  
  1126. int valid(int k)
  1127. {
  1128.     int i;
  1129.     if(k>1)
  1130.         if(s[k-1]>=s[k])
  1131.             return 0;
  1132.     return 1;
  1133. }
  1134.  
  1135. int solutie(int k)
  1136. {
  1137.     if(k==p)
  1138.         return 1;
  1139.     return 0;
  1140. }
  1141.  
  1142. void tipar(int k)
  1143. {
  1144.     int i;
  1145.     for(i=1;i<=k;i++)
  1146.         cout<<s[i]<<" ";
  1147.     cout<<endl;
  1148. }
  1149.  
  1150. void bkt(int k)
  1151. {
  1152.     int as,ev;
  1153.     init(k);
  1154.     while(k>0)
  1155.     {
  1156.         do
  1157.         {
  1158.             as=succesor(k);
  1159.             if(as==1)
  1160.                 ev=valid(k);
  1161.         }while(as==1 && ev==0);
  1162.         if(as==1)
  1163.             if(solutie(k)==1)
  1164.                 tipar(k);
  1165.         else
  1166.         {
  1167.             k++;
  1168.             init(k);
  1169.         }
  1170.         else
  1171.             k--;
  1172.     }
  1173. }
  1174.  
  1175. int main()
  1176. {
  1177.     cin>>n>>p;
  1178.     bkt(1);
  1179.     return 0;
  1180. }
  1181.  
  1182. //                                 --------------2 SI 4 SA NU FIE IN ACELASI BUCHET---------------
  1183.  
  1184. #include <iostream>
  1185.  
  1186. using namespace std;
  1187.  
  1188. int n,p,s[100];
  1189.  
  1190. void init(int k)
  1191. {
  1192.     s[k]=0;
  1193. }
  1194.  
  1195. int succesor(int k)
  1196. {
  1197.     if(s[k]<n)
  1198.     {
  1199.         s[k]++;
  1200.         return 1;
  1201.     }
  1202.     return 0;
  1203. }
  1204.  
  1205. int valid(int k)
  1206. {
  1207.     int i;
  1208.     if(k>1)
  1209.         if(s[k-1]>=s[k])
  1210.             return 0;
  1211.     if(s[k]==2)
  1212.         for(i=1;i<k;i++)
  1213.             if(s[i]==4)
  1214.                 return 0;
  1215.     if(s[k]==4)
  1216.         for(i=1;i<k;i++)
  1217.             if(s[i]==2)
  1218.                 return 0;
  1219.     return 1;
  1220. }
  1221.  
  1222. int solutie(int k)
  1223. {
  1224.     if(k==p)
  1225.         return 1;
  1226.     return 0;
  1227. }
  1228.  
  1229. void tipar(int k)
  1230. {
  1231.     int i;
  1232.     for(i=1;i<=k;i++)
  1233.     {
  1234.         if(s[i]==1)
  1235.             cout<<"brandusa ";
  1236.         if(s[i]==2)
  1237.             cout<<"iasomie ";
  1238.         if(s[i]==3)
  1239.             cout<<"lalea ";
  1240.         if(s[i]==4)
  1241.             cout<<"liliac ";
  1242.         if(s[i]==5)
  1243.             cout<<"margareta ";
  1244.     }
  1245.     cout<<endl;
  1246. }
  1247.  
  1248. void bkt(int k)
  1249. {
  1250.     int as,ev;
  1251.     init(k);
  1252.     while(k>0)
  1253.     {
  1254.         do
  1255.         {
  1256.             as=succesor(k);
  1257.             if(as==1)
  1258.                 ev=valid(k);
  1259.         }while(as==1 && ev==0);
  1260.         if(as==1)
  1261.             if(solutie(k)==1)
  1262.                 tipar(k);
  1263.         else
  1264.         {
  1265.             k++;
  1266.             init(k);
  1267.         }
  1268.         else
  1269.             k--;
  1270.     }
  1271. }
  1272.  
  1273. int main()
  1274. {
  1275.     cin>>n>>p;
  1276.     bkt(1);
  1277.     return 0;
  1278. }
  1279.  
  1280. //                                 --------GENERAREA SUBMULTIMILOR UNEI MULTIMI---------
  1281.  
  1282. #include <iostream>
  1283.  
  1284. using namespace std;
  1285.  
  1286. int n,s[100];
  1287.  
  1288. void init(int k)
  1289. {
  1290.     s[k]=0;
  1291. }
  1292.  
  1293. int succesor(int k)
  1294. {
  1295.     if(s[k]<2)
  1296.     {
  1297.         s[k]++;
  1298.         return 1;
  1299.     }
  1300.     return 0;
  1301. }
  1302.  
  1303. int valid(int k)
  1304. {
  1305.     return 1;
  1306. }
  1307.  
  1308. int solutie(int k)
  1309. {
  1310.     if(k==n)
  1311.         return 1;
  1312.     return 0;
  1313. }
  1314.  
  1315. void tipar(int k)
  1316. {
  1317.     int i;
  1318.     for(i=1;i<=k;i++)
  1319.         if(s[i]==1)
  1320.             cout<<i<<" ";
  1321.     cout<<endl;
  1322. }
  1323.  
  1324. void bkt(int k)
  1325. {
  1326.     int as,ev;
  1327.     init(k);
  1328.     while(k>0)
  1329.     {
  1330.         do
  1331.         {
  1332.             as=succesor(k);
  1333.             if(as==1)
  1334.                 ev=valid(k);
  1335.         }while(as==1 && ev==0);
  1336.         if(as==1)
  1337.             if(solutie(k)==1)
  1338.                 tipar(k);
  1339.         else
  1340.         {
  1341.             k++;
  1342.             init(k);
  1343.         }
  1344.         else
  1345.             k--;
  1346.     }
  1347. }
  1348.  
  1349. int main()
  1350. {
  1351.     cin>>n;
  1352.     bkt(1);
  1353.     return 0;
  1354. }
  1355.  
  1356. //                                 --------PARTITILE UNUI NR A---------
  1357.  
  1358. #include <iostream>
  1359.  
  1360. using namespace std;
  1361.  
  1362. int n,s[100];
  1363.  
  1364. int suma(int k)
  1365. {
  1366.     int i,s1=0;
  1367.     for(i=1;i<=k;i++)
  1368.         s1+=s[i];
  1369.     return s1;
  1370. }
  1371.  
  1372. void init(int k)
  1373. {
  1374.     s[k]=0;
  1375. }
  1376.  
  1377. int succesor(int k)
  1378. {
  1379.     if(s[k]<n && suma(k)<n)
  1380.     {
  1381.         s[k]++;
  1382.         return 1;
  1383.     }
  1384.     return 0;
  1385. }
  1386.  
  1387. int valid(int k)
  1388. {
  1389.     int i;
  1390.     return 1;
  1391. }
  1392.  
  1393. int solutie(int k)
  1394. {
  1395.     if(suma(k)==n)
  1396.         return 1;
  1397.     return 0;
  1398. }
  1399.  
  1400. void tipar(int k)
  1401. {
  1402.     int i;
  1403.     for(i=1;i<=k;i++)
  1404.         cout<<s[i]<<" ";
  1405.     cout<<endl;
  1406. }
  1407.  
  1408. void bkt(int k)
  1409. {
  1410.     int as,ev;
  1411.     init(k);
  1412.     while(k>0)
  1413.     {
  1414.         do
  1415.         {
  1416.             as=succesor(k);
  1417.             if(as==1)
  1418.                 ev=valid(k);
  1419.         }while(as==1 && ev==0);
  1420.         if(as==1)
  1421.             if(solutie(k)==1)
  1422.                 tipar(k);
  1423.         else
  1424.         {
  1425.             k++;
  1426.             init(k);
  1427.         }
  1428.         else
  1429.             k--;
  1430.     }
  1431. }
  1432.  int main()
  1433. {
  1434.     cin>>n;
  1435.     bkt(1);
  1436.  
  1437.     return 0;
  1438. }
  1439.  
  1440. //                                 --------PARTITILE UNUI NR B---------
  1441.  
  1442. #include <iostream>
  1443.  
  1444. using namespace std;
  1445.  
  1446. int n,s[100];
  1447.  
  1448. int suma(int k)
  1449. {
  1450.     int i,s1=0;
  1451.     for(i=1;i<=k;i++)
  1452.         s1+=s[i];
  1453.     return s1;
  1454. }
  1455.  
  1456. void init(int k)
  1457. {
  1458.     s[k]=0;
  1459. }
  1460.  
  1461. int succesor(int k)
  1462. {
  1463.     if(s[k]<n && suma(k)<n)
  1464.     {
  1465.         s[k]++;
  1466.         return 1;
  1467.     }
  1468.     return 0;
  1469. }
  1470.  
  1471. int valid(int k)
  1472. {
  1473.     int i;
  1474.     if(k>1)
  1475.         if(s[k]<s[k-1])
  1476.             return 0;
  1477.     return 1;
  1478. }
  1479.  
  1480. int solutie(int k)
  1481. {
  1482.     if(suma(k)==n)
  1483.         return 1;
  1484.     return 0;
  1485. }
  1486.  
  1487. void tipar(int k)
  1488. {
  1489.     int i;
  1490.     for(i=1;i<=k;i++)
  1491.         cout<<s[i]<<" ";
  1492.     cout<<endl;
  1493. }
  1494.  
  1495. void bkt(int k)
  1496. {
  1497.     int as,ev;
  1498.     init(k);
  1499.     while(k>0)
  1500.     {
  1501.         do
  1502.         {
  1503.             as=succesor(k);
  1504.             if(as==1)
  1505.                 ev=valid(k);
  1506.         }while(as==1 && ev==0);
  1507.         if(as==1)
  1508.             if(solutie(k)==1)
  1509.                 tipar(k);
  1510.         else
  1511.         {
  1512.             k++;
  1513.             init(k);
  1514.         }
  1515.         else
  1516.             k--;
  1517.     }
  1518. }
  1519.  int main()
  1520. {
  1521.     cin>>n;
  1522.     bkt(1);
  1523.  
  1524.     return 0;
  1525. }
  1526.  
  1527. //                                 --------PARTITILE UNUI NR C---------
  1528.  
  1529. #include <iostream>
  1530.  
  1531. using namespace std;
  1532.  
  1533. int n,s[100];
  1534.  
  1535. int suma(int k)
  1536. {
  1537.     int i,s1=0;
  1538.     for(i=1;i<=k;i++)
  1539.         s1+=s[i];
  1540.     return s1;
  1541. }
  1542.  
  1543. void init(int k)
  1544. {
  1545.     s[k]=0;
  1546. }
  1547.  
  1548. int succesor(int k)
  1549. {
  1550.     if(s[k]<n && suma(k)<n)
  1551.     {
  1552.         s[k]++;
  1553.         return 1;
  1554.     }
  1555.     return 0;
  1556. }
  1557.  
  1558. int valid(int k)
  1559. {
  1560.     int i;
  1561.     if(k>1)
  1562.         if(s[k]<s[k-1])
  1563.             return 0;
  1564.     for(i=1;i<k;i++)
  1565.         if(s[i]==s[k])
  1566.             return 0;
  1567.     return 1;
  1568. }
  1569.  
  1570. int solutie(int k)
  1571. {
  1572.     if(suma(k)==n)
  1573.         return 1;
  1574.     return 0;
  1575. }
  1576.  
  1577. void tipar(int k)
  1578. {
  1579.     int i;
  1580.     for(i=1;i<=k;i++)
  1581.         cout<<s[i]<<" ";
  1582.     cout<<endl;
  1583. }
  1584.  
  1585. void bkt(int k)
  1586. {
  1587.     int as,ev;
  1588.     init(k);
  1589.     while(k>0)
  1590.     {
  1591.         do
  1592.         {
  1593.             as=succesor(k);
  1594.             if(as==1)
  1595.                 ev=valid(k);
  1596.         }while(as==1 && ev==0);
  1597.         if(as==1)
  1598.             if(solutie(k)==1)
  1599.                 tipar(k);
  1600.         else
  1601.         {
  1602.             k++;
  1603.             init(k);
  1604.         }
  1605.         else
  1606.             k--;
  1607.     }
  1608. }
  1609.  int main()
  1610. {
  1611.     cin>>n;
  1612.     bkt(1);
  1613.  
  1614.     return 0;
  1615. }
  1616.  
  1617. //                                 --------PROBLEMA CELOR N DAME---------
  1618.  
  1619. #include <iostream>
  1620. #include <cmath>
  1621.  
  1622. using namespace std;
  1623.  
  1624. int n,s[100];
  1625.  
  1626. void init(int k)
  1627. {
  1628.     s[k]=0;
  1629. }
  1630.  
  1631. int succesor(int k)
  1632. {
  1633.     if(s[k]<n)
  1634.     {
  1635.         s[k]++;
  1636.         return 1;
  1637.     }
  1638.     return 0;
  1639. }
  1640.  
  1641. int valid(int k)
  1642. {
  1643.     int i;
  1644.     for(i=1;i<k;i++)
  1645.     {
  1646.         if(s[i]==s[k])
  1647.             return 0;
  1648.         if(abs(s[k]-s[i])==k-i)
  1649.             return 0;
  1650.     }
  1651.     return 1;
  1652. }
  1653.  
  1654. int solutie(int k)
  1655. {
  1656.     if(k==n)
  1657.         return 1;
  1658.     return 0;
  1659. }
  1660.  
  1661. void tipar(int k)
  1662. {
  1663.     int i,j;
  1664.     for(i=1;i<=k;i++)
  1665.     {
  1666.         for(j=1;j<=k;j++)
  1667.             if(s[i]==j)
  1668.                 cout<<"R";
  1669.             else
  1670.                 cout<<"*";
  1671.         cout<<endl;
  1672.     }
  1673.     cout<<endl;
  1674. }
  1675.  
  1676. void bkt(int k)
  1677. {
  1678.     int as,ev;
  1679.     init(k);
  1680.     while(k>0)
  1681.     {
  1682.         do
  1683.         {
  1684.             as=succesor(k);
  1685.             if(as==1)
  1686.                 ev=valid(k);
  1687.         }while(as==1 && ev==0);
  1688.         if(as==1)
  1689.             if(solutie(k)==1)
  1690.                 tipar(k);
  1691.         else
  1692.         {
  1693.             k++;
  1694.             init(k);
  1695.         }
  1696.         else
  1697.             k--;
  1698.     }
  1699. }
  1700.  int main()
  1701. {
  1702.     cin>>n;
  1703.     bkt(1);
  1704.  
  1705.     return 0;
  1706. }
  1707.  
  1708. //                                 --------COLORAREA HARTILOR---------
  1709.  
  1710. #include <iostream>
  1711. #include <fstream>
  1712.  
  1713. using namespace std;
  1714.  
  1715. ifstream f("harta.txt");
  1716.  
  1717. int n,s[100],a[20][20];
  1718.  
  1719. void init(int k)
  1720. {
  1721.     s[k]=0;
  1722. }
  1723.  
  1724. int succesor(int k)
  1725. {
  1726.     if(s[k]<4)
  1727.     {
  1728.         s[k]++;
  1729.         return 1;
  1730.     }
  1731.     return 0;
  1732. }
  1733.  
  1734. int valid(int k)
  1735. {
  1736.     int i;
  1737.     for(i=1;i<k;i++)
  1738.         if(a[i][k]==1 && s[i]==s[k])
  1739.             return 0;
  1740.     return 1;
  1741. }
  1742.  
  1743. int solutie(int k)
  1744. {
  1745.     if(k==n)
  1746.         return 1;
  1747.     return 0;
  1748. }
  1749.  
  1750. void tipar(int k)
  1751. {
  1752.     int i;
  1753.     for(i=1;i<=k;i++)
  1754.         if(s[i]==1)
  1755.             cout<<i<<" ";
  1756.     cout<<endl;
  1757. }
  1758.  
  1759. void bkt(int k)
  1760. {
  1761.     int as,ev;
  1762.     init(k);
  1763.     while(k>0)
  1764.     {
  1765.         do
  1766.         {
  1767.             as=succesor(k);
  1768.             if(as==1)
  1769.                 ev=valid(k);
  1770.         }while(as==1 && ev==0);
  1771.         if(as==1)
  1772.             if(solutie(k)==1)
  1773.                 tipar(k);
  1774.         else
  1775.         {
  1776.             k++;
  1777.             init(k);
  1778.         }
  1779.         else
  1780.             k--;
  1781.     }
  1782. }
  1783.  int main()
  1784. {
  1785.     int i,j;
  1786.     f>>n;
  1787.     for(i=1;i<=n;i++)
  1788.         for(j=1;j<=n;j++)
  1789.             f>>a[i][j];
  1790.     bkt(1);
  1791.  
  1792.     return 0;
  1793. }
  1794.  
  1795. //                                 --------MULTIMILE ELEMETELOR VECTORULUI CU SUMA S---------
  1796.  
  1797. #include <iostream>
  1798.  
  1799. using namespace std;
  1800.  
  1801. int n,s[100],v[100],S;
  1802.  
  1803. int suma(int k)
  1804. {
  1805.     int i,s1=0;
  1806.     for(i=1;i<=k;i++)
  1807.         s1+=v[s[i]];
  1808.     return s1;
  1809. }
  1810.  
  1811. void init(int k)
  1812. {
  1813.     s[k]=0;
  1814. }
  1815.  
  1816. int succesor(int k)
  1817. {
  1818.     int i,s1=0;
  1819.     for(i=1;i<k;i++)
  1820.         s1+=v[s[i]];
  1821.     if(s[k]<n && s1<S)
  1822.     {
  1823.         s[k]++;
  1824.         return 1;
  1825.     }
  1826.     return 0;
  1827. }
  1828.  
  1829. int valid(int k)
  1830. {
  1831.     int i;
  1832.     if(k>1)
  1833.         if(s[k-1]>s[k])
  1834.             return 0;
  1835.     for(i=1;i<k;i++)
  1836.         if(s[i]==s[k])
  1837.             return 0;
  1838.     return 1;
  1839. }
  1840.  
  1841. int solutie(int k)
  1842. {
  1843.     if(suma(k)==S)
  1844.         return 1;
  1845.     return 0;
  1846. }
  1847.  
  1848. void tipar(int k)
  1849. {
  1850.     int i;
  1851.     for(i=1;i<=k;i++)
  1852.         cout<<v[s[i]]<<" ";
  1853.     cout<<endl;
  1854. }
  1855.  
  1856. void bkt(int k)
  1857. {
  1858.     int as,ev;
  1859.     init(k);
  1860.     while(k>0)
  1861.     {
  1862.         do
  1863.         {
  1864.             as=succesor(k);
  1865.             if(as==1)
  1866.                 ev=valid(k);
  1867.         }while(as==1 && ev==0);
  1868.         if(as==1)
  1869.             if(solutie(k)==1)
  1870.                 tipar(k);
  1871.         else
  1872.         {
  1873.             k++;
  1874.             init(k);
  1875.         }
  1876.         else
  1877.             k--;
  1878.     }
  1879. }
  1880.  int main()
  1881. {
  1882.     cin>>n>>S;
  1883.     for(int i=1;i<=n;i++)
  1884.         cin>>v[i];
  1885.     bkt(1);
  1886.  
  1887.     return 0;
  1888. }
RAW Paste Data

Adblocker detected! Please consider disabling it...

We've detected AdBlock Plus or some other adblocking software preventing Pastebin.com from fully loading.

We don't have any obnoxious sound, or popup ads, we actively block these annoying types of ads!

Please add Pastebin.com to your ad blocker whitelist or disable your adblocking software.

×