Difference between revisions of "Clasa a VII-a lecția 37 - 18 iun 2020"

From Algopedia
Jump to navigationJump to search
(Created page with "== Problema Exodul marțienilor == Problema [http://varena.ro/problema/exod exodul marțienilor] cere să simulăm o evacuare a planetei Marte ce se face după anumite reguli....")
 
(One intermediate revision by the same user not shown)
Line 1: Line 1:
== Problema Exodul marțienilor ==
+
= Lecție =
Problema [http://varena.ro/problema/exod exodul marțienilor] cere să simulăm o evacuare a planetei Marte ce se face după anumite reguli.
 
  
Vom mai vorbi despre astfel de probleme, ce fac parte dintr-o categorie pe care am denumit-o ''simulare'', deoarece ni se cere să simulăm un scenariu, exodul marțienilor către cele două planete.
+
Felicitări lui Mircea Rebengiuc care a cîștigat concursul cu programul ''the-flood-of-bash''.
  
Problema nu este una foarte grea din punct de vedere informatic. Ea pune probleme din punct de vedere matematic și anume cere să calculăm formula unei sume a lui Gauss modificate. Ideea de a pune concurenții la informatică să găsească formule matematice complexe în timpul unui concurs de informatică nu mi se pare foarte fericită. Și totuși iată că această problemă s-a dat. Să vedem cum am putea-o aborda.
+
== Concurs: jocul Flood Wars - rezultate oficiale ==
 +
''Notă: din cauza unor defecțiuni tehnice turneul a fost oprit prematur. Au fost jucate trei turnee complete, pe trei table diferite, pe fiecare tablă jucîndu-se 25 de runde. A mai fost jucat și un turneu incomplet, pe o a patra tablă, în care s-au desfășurat 22 runde din totalul de 25.
  
=== Soluție forță brută ===
+
Rezultatele concursului de Flood Wars sînt următoarele:
Să pornim la drum cu o soluție complet nematematică.
 
  
==== Punctul unu ====
+
Număr total de jocuri jucate: 2522.
Vom simula etapele. Vom avea o buclă în care vom calcula numărul de nave ce pleacă spre fiecare planetă în acea etapă. Vom scădea din numărul de oameni de pe Marte numărul de oameni plecați cu navele. Ne oprim cînd nu mai putem încărca oameni.
 
 
 
==== Punctul doi ====
 
Pentru a calcula mărimea navelor (cîți oameni poate o navă să transporte) astfel încît evacuarea planetei Marte să se facă în fix <code>p</code> etape putem proceda direct: considerăm <code>k&nbsp;=&nbsp;1</code>. Apoi simulăm execuția a <code>p</code> etape, întocmai ca la punctul anterior. Dacă nu am depășit numărul de oameni pe Marte, trecem la <code>k&nbsp;=&nbsp;2</code> și reluăm: executăm din nou cele <code>p</code> etape. Apoi trecem la <code>k&nbsp;=&nbsp;1</code> și așa mai departe pînă ce depășim numărul de oameni de pe Marte. Ultimul <code>k</code> ce a "funcționat" este răspunsul.
 
 
 
Iată o soluție bazată pe aceste idei:
 
 
 
<syntaxhighlight>#include <stdio.h>
 
#include <math.h>
 
 
 
int main() {
 
  FILE *fin, *fout;
 
  long long n, p1, k1, marte, ka, ki, tka, tki;
 
  int k, p;
 
 
 
  fout = fopen( "exod.out", "w" );
 
  fin = fopen( "exod.in", "r" );
 
  fscanf( fin, "%lld%d%d", &n, &k, &p );
 
  fclose( fin );
 
 
 
  marte = n;
 
  ka = ki = 0;
 
  p1 = 1;
 
  tka = k;
 
  tki = 2 * k;
 
  while ( tka + tki <= marte ) {
 
    marte -= (tka + tki); // transportam oamenii de pe marte
 
    ka += tka;            // transportam oamenii pe ka
 
    ki += tki;            // transportam oamenii pe ki
 
    p1++; // marim etapa
 
    if ( tka > tki ) {
 
      tka += k;
 
      tki = tka + k;
 
    } else {
 
      tki += k;
 
      tka = tki + k;
 
    }
 
  }
 
  p1--; // numarul corect de etape
 
  fprintf( fout, "%lld %lld %lld %lld\n", p1, marte, ka, ki );
 
 
 
  k1 = 0;
 
  marte = 1;
 
  while ( marte >= 0 ) {
 
    k1++;
 
    marte = n;
 
    ka = ki = 0;
 
    tka = k1;
 
    tki = 2 * k1;
 
    for ( p1 = 1; p1 <= p; p1++ ) {
 
      marte -= (tka + tki); // transportam oamenii de pe marte
 
      ka += tka;            // transportam oamenii pe ka
 
      ki += tki;            // transportam oamenii pe ki
 
      if ( tka > tki ) {
 
        tka += k1;
 
        tki = tka + k1;
 
      } else {
 
        tki += k1;
 
        tka = tki + k1;
 
      }
 
    }
 
  }
 
 
 
  fprintf( fout, "%lld\n", k1-1 );
 
  fclose( fout );
 
 
 
  return 0;
 
}</syntaxhighlight>
 
 
 
=== Soluție forță brută optimizată ===
 
Soluția forță brută rezolvă destul de eficient punctul unu, dar foarte ineficient punctul doi. Ea va repeta execuția tuturor celor <code>p</code> etape de <code>k</code> ori, ceea ce poate duce la un număr foarte mare de operații atunci cînd <code>k</code> și <code>p</code> sînt foarte mari. De aceea soluția va pica testele mari. Oare putem să facem mai puține calcule la acest punct?
 
 
 
Să presupunem că navele transportă un singur om, adică <code>k</code> este 1. În acest caz, după ce simulăm execuția celor <code>p</code> etape să presupunem că vom transporta <code>m</code> marțieni. Ce se întîmpla dacă mărim dimensiunea navelor la 2, adică <code>k</code> devine 2? Deoarece vom avea exact aceleași nave care pleacă, dar fiecare este dublă, rezultă că vom transporta <code>2*m</code> marțieni. Dar dacă <code>k</code> este 3? Desigur vom transporta <code>3*m</code> marțieni. Atunci cînd vom avea <code>k</code> maxim vom transporta <code>k*m</code> marțieni. Dacă l-am mări pe <code>k</code> cu încă unu am depăși numărul de oameni de pe Marte, în cele <code>p</code> etape de transport.
 
 
 
Dar cine este <code>k</code> maxim? El va fi acel <code>k</code> astfel încît el să fie maxim și <code>k*m<=n</code>. De aici rezultă că <code>k=n/m</code>.
 
 
 
Cum modificăm algoritmul pentru punctul doi? Vom calcula mai intîi <code>m</code> în mod similar cu punctul unu, considerînd că navele transportă un singur om. Apoi vom calcula <code>k</code> împărțind <code>n</code> la <code>m</code>.
 
 
 
Iată o soluție îmbunătățită bazată pe acest algoritm:
 
 
 
<syntaxhighlight>#include <stdio.h>
 
#include <math.h>
 
 
 
int main() {
 
  FILE *fin, *fout;
 
  long long n, p1, k1, marte, ka, ki, tka, tki;
 
  int k, p;
 
 
 
  fout = fopen( "exod.out", "w" );
 
  fin = fopen( "exod.in", "r" );
 
  fscanf( fin, "%lld%d%d", &n, &k, &p );
 
  fclose( fin );
 
 
 
  marte = n;
 
  ka = ki = 0;
 
  p1 = 1;
 
  tka = k;
 
  tki = 2 * k;
 
  while ( tka + tki <= marte ) {
 
    marte -= (tka + tki); // transportam oamenii de pe marte
 
    ka += tka;            // transportam oamenii pe ka
 
    ki += tki;            // transportam oamenii pe ki
 
    p1++; // marim etapa
 
    if ( tka > tki ) {
 
      tka += k;
 
      tki = tka + k;
 
    } else {
 
      tki += k;
 
      tka = tki + k;
 
    }
 
  }
 
  p1--; // numarul corect de etape
 
  fprintf( fout, "%lld %lld %lld %lld\n", p1, marte, ka, ki );
 
 
 
  // calculam in marte numarul de oameni transportati in p etape pentru k = 1
 
  marte = 0;
 
  ka = ki = 0;
 
  p1 = 1;
 
  tka = 1;
 
  tki = 2;
 
  for ( p1 = 1; p1 <= p; p1++ ) {
 
    marte += (tka + tki); // transportam oamenii de pe marte
 
    ka += tka;            // transportam oamenii pe ka
 
    ki += tki;            // transportam oamenii pe ki
 
    if ( tka > tki ) {
 
      tka += 1;
 
      tki = tka + 1;
 
    } else {
 
      tki += 1;
 
      tka = tki + 1;
 
    }
 
  }
 
  k1 = n / marte; // calculam k1 maxim astfel incit k1 * marte <= n
 
 
 
  fprintf( fout, "%lld\n", k1 );
 
  fclose( fout );
 
 
 
  return 0;
 
}</syntaxhighlight>
 
 
 
=== Soluție elegantă ===
 
Ca în multe alte cazuri, soluția elegantă este cea bazată pe matematică. Din păcate această matematică s-ar putea să nu vă fie accesibilă, ea studiindu-se riguros abia în clasa a zecea. Fiind vorba de o sumă a lui Gauss modificată este posibil să o puteți deduce singuri, deși mi se pare un exercițiu prea greu pentru a îl face în timpul concursului, mai ales că nu este unul de matematică.
 
  
 
{| class="wikitable"
 
{| class="wikitable"
!Etapa
+
!Loc
!Marțieni către Ka
+
!Program
!Marțieni către Ki
+
!Programatori
!Total marțieni pînă acum
+
!Scor
 
|-
 
|-
 
| 1
 
| 1
| k
+
| the-flood-of-bash-v5
| 2k
+
| Mircea Rebengiuc
| 1k+2k
+
| 267
 
|-
 
|-
 
| 2
 
| 2
| 4k
+
| flood-curse-v4
| 3k
+
| Tudor Mușat
| 1k+2k+3k+4k
+
| 249
 
|-
 
|-
 
| 3
 
| 3
| 5k
+
| ourmine-v1
| 6k
+
| Nicolas Teodorescu
| 1k+2k+3k+4k+5k+6k
+
| 222
 
|-
 
|-
 
| 4
 
| 4
| 8k
+
| kalanera-v2
| 7k
+
| Ana Petcu
| 1k+2k+3k+4k+5k+6k+7k+8k
+
| 216
 
|-
 
|-
 
| 5
 
| 5
| 9k
+
| terminator-v4
| 10k
+
| Teodor Togan
| 1k+2k+3k+4k+5k+6k+7k+8k+9k+10k
+
| 213
 +
|-
 +
| 6
 +
| thinker-destroyer-v3
 +
| Alex Nicu & Bogdan Petrescu
 +
| 208
 +
|-
 +
| 7
 +
| alphazero-v1
 +
| Mihai Voicu
 +
| 205
 +
|-
 +
| 8
 +
| uor-v3
 +
| Luca Ilie & Tudor Ghica
 +
| 198
 +
|-
 +
| 9
 +
| bob-reborn-v2
 +
| Yusuf Fares & Armin Asgari
 +
| 171
 +
|-
 +
| 10
 +
| trickster-v2
 +
| Albert Aizic
 +
| 168
 +
|-
 +
| 11
 +
| destroyers-v1
 +
| Vlad Burac & Alexandru Hossu
 +
| 147
 +
|-
 +
| 12
 +
| nexus-v1
 +
| Rareș Iordache
 +
| 136
 +
|-
 +
| 13
 +
| chameleon-v1
 +
| Teodor Tatomir
 +
| 117
 +
|-
 +
| 14
 +
| emu-v4
 +
| Remus Rughiniș
 +
| 103
 +
|-
 +
| 15
 +
| clone-wars-v3
 +
| Ecaterina Ștefănescu
 +
| 93
 +
|-
 +
| 16
 +
| luck-of-the-sea-v2
 +
| Lucian Badea
 +
| 87
 +
|-
 +
| 17
 +
| andrews-ark-v1
 +
| Andrei Calotă
 +
| 72
 +
|-
 +
| 17
 +
| taf-v1
 +
| Victor Nicola & Mihai Mocanu
 +
| 72
 +
|-
 +
| 19
 +
| peeves-v3
 +
| Ilinca Marcu
 +
| 66
 +
|-
 +
| 20
 +
| greedy-v4
 +
| Radu Dobre
 +
| 51
 +
|-
 +
| 21
 +
| byoprg-v1
 +
| Tudor Grecu
 +
| 48
 +
|-
 +
| 21
 +
| leprechaun-v3
 +
| David Stancu
 +
| 48
 +
|-
 +
| 23
 +
| alleks-bot-v2
 +
| Alexandru Benescu
 +
| 39
 +
|-
 +
| 24
 +
| phoenix-v2
 +
| Vlad Dimulescu
 +
| 18
 
|}
 
|}
  
Observăm că numărul total de marțieni transportați seamănă cu o sumă a lui Gauss. Să deducem relația matematică între numărul etapei, '''p''' și numărul de marțieni transportați pînă la acea etapă, inclusiv acea etapă. Observăm că în etapa '''p''' vom transporta
+
Rezultatele jocurilor individuale:
  
: m = 1k + 2k + 3k + 4k + ... + (2p-1)k + 2pk
+
<pre>
 +
Results on board 'board1'
  
Dacă îl dăm factor comun pe '''k''' vom obține o sumă a lui Gauss:
+
  ID        Nume Program    0    1    2    3    4    5    6    7    8    9  10  11  12  13  14  15  16  17  18  19  20  21  22  23  24  25
  
: m = k &middot; (1 + 2 + 3 + 4 + ... + (2p - 1) + 2p)
+
  0        alleks-bot-v2    0  114  74  170  182  176  554  392  294  -88  340 -176  770  302  248 -200  -10  278 1010  268  -83 -144  -24 -148  36 -134
: m = k &middot; Gauss(2p)
+
  1         alphazero-v1  702    0  572  556  938  534  444  580  812  327  828  396  894  796  508  150  326  726 1060  688  466  204  330  237  654  370
: m = k &middot; 2p(2p + 1) / 2
+
  2       andrews-ark-v1  368  -14    0  46  848  88  308  374  508  136  390  96  412  240  230  22  -60  834  926  494  -60 -168  -6  46  40  -10
: m = k &middot; p(2p + 1)
+
  3       bob-reborn-v2  482  172 -2500    0  868  692  748 -2500  684  252 1020  291  926  952  368  58  172  922 1050  638  382  172  224 -2500  368  262
 +
  4           byoprg-v1  288  216  292  282    0  114  180    8  162  34  378  256  328  126  -62  -62  30  752  598  472  188  -58  104  -66  172  -26
 +
  5        chameleon-v1  376  -20  246 2500  712    0  312  328  724  -20  382  46  794  590  88  -66  -28  524  630  470  192  -94  -20  72  162  48
 +
  6        clone-wars-v3  218  128  432  58  738  538    0  616  558  -18  256    2  754  638  346  70  58  644  966  410  150  -6  26 -122  228  258
 +
  7        destroyers-v1  274  98  568  302  624  378  310    0  584  186  536  98  866  834  184  -18  180 1058  754  734  116  -80  152  12  392  268
 +
  8              emu-v4  362  124  340  368  796  242  604  190    0  82  630  284  572  344  92  -42  284  398  766  276  446 -122  298  62  110  -20
 +
  9      flood-curse-v4  694  738 1076  496 1062  786  778  466 1144    0  972  682  998  966  672  186  794  960 1030  850  534  280  790  369  766  502
 +
  10            greedy-v4  566  -24  400  26  672  68  380  122  424  -92    0 -192  672  414  156  26  -38  614  656  90  312  -66  -38 -154    8  284
 +
  11          kalanera-v2  350  312  782  654  940  592  554  834  482  304 1040    0  874  898  472  102  494  696 1310  794  458  286  388  70  554  314
 +
  12        leprechaun-v3  558  -90  474  100  334  208  376  462  526 -100  376  -70    0  440  170 -214 -148  494  808  316 -206  -88  90  32  -40  276
 +
  13  luck-of-the-sea-v2  600  134  526  -14  644  474  332  138  412  30  794  134  218    0  44 -212  154  364  950  578  144    2  152  -60  -2  130
 +
  14            nexus-v1  680  18  630  348  804  426  456  504  484  -76  634  -78  540  598    0    2   18  804  830  506  -32  -22  18  -32  222  164
 +
  15              noe-v4  1050  700 1012  638 1374  680  782  786  790  728  990  666  892  754  812    0  590 1274 1172  678  670  728  590  518  698  882
 +
  16          ourmine-v1  630  784  720  558  946  568  620  560  630  176  982  418 1014  788  500  296    0  670 1066  616  352  158  368  232  380  370
 +
  17            peeves-v3  664  88  734  136  474  264  340  312  566 -252  786  134  218  342  176  22  132    0  792  584  146 -164  156  110  -50  156
 +
  18          phoenix-v2  306  -66  192  -64  958  152 -104  36  328 -322  414  -98  280  102 -100 -118 -276  514    0  318  82 -196 -274 -270  -4  140
 +
  19              taf-v1  502  72  268  172  336  354  428  336  472  148  580  36  490  292  350  -76  238  676  700    0  62  46  274  55  94  358
 +
  20        terminator-v4  728  332  778  622  894  710  396  674  458  174  714  448  878  742  600  188  524  830 1046  944    0  164  300  206  652  312
 +
  21 the-flood-of-bash-v5  830  744  864 2500 1102  954  820  874 1150  546  996  948  862  734  830  324  638 1078 1010  872  614    0  638  440  836  702
 +
  22 thinker-destroyer-v3  562  448  722  654  946  592  302  558  562  126  832  410 1014  746  500  140  308  670 1072  644  268  158    0  294  442  564
 +
  23            timus-v1  845  966  906  722 1016 1044  824 1044 1114  596 1150  670  930  880  964  434  570 1249 1096  766  580  592  916    0  556  546
 +
  24        trickster-v2  682  -68  374  504  558  682  558  416  454  92  510  138  804  560  518  124  -70  874 1076  698  356  74  -70  30    0  410
 +
  25              uor-v3  704  194  796  266 1042  790  772  424  594  524  966  132 1018  994  522  46    6 1132 1142  536  406  362  176  104  402    0
  
Cunoscînd numărul de oameni transportați în '''p''' etape putem acum rezolva cele două puncte ale problemei.
 
  
==== Punctul unu ====
+
Results on board 'board2'
La primul punct avem formula
 
  
: m = k &middot; p(2p + 1)
+
  ID        Nume Program    0    1   2    3    4    5    6    7    8    9  10  11  12  13  14  15  16  17  18  19  20  21  22  23  24  25
  
În această formulă cunoaștem '''m''' și '''k''' și ni se cere '''p'''. În fapt nu cunoaștem '''m''' ci un număr posibil mai mare, anume '''n''', astfel încît relația corectă va fi:
+
  0        alleks-bot-v2    0 -242  142 -650  92 -156  -54 -484  -70 -554    0 -574  148 -134 -380 -572 -382  190  76 -172 -418 -606 -358 -678 -292 -772
 +
  1        alphazero-v1  672    0  646  40  768  534  474  188  320  100  602  16  852  512  468 -294  126  292  542  408  -20 -256  138  -10  168  106
 +
  2      andrews-ark-v1  278  -98    0 2500  368  130  236 -368 -238 -386  92 -310  -16 -172 -170 -618 -152  34  308 -208 -164 -582 -278 -710  46 -254
 +
  3        bob-reborn-v2  598  208  440    0  626  492  272  242  318  -46 -2500  218  696  506  266 -190 -290  330  476  492  58 -278  26 -230  348  28
 +
  4            byoprg-v1    94 -374  188 -516    0 -394  -10 -554 -382 -410  36 -458  112  76 -156 -624 -470  -32  316 -206 -372 -424 -530 -616 -690 -482
 +
  5        chameleon-v1  169 -384 -146 -210  452    0  274 -254  -26 -496  542 -314  496  336  100 -440 -388  214  500  -8  -70 -432 -388 -172  -66 -328
 +
  6        clone-wars-v3  106 -224  96 -412  424  132    0 -210 -346 -204  308 -358  478  208  -26 -544 -320  48  264 -214  -54 -500 -308 -630 -464 -330
 +
  7        destroyers-v1  326  137  486  272  528  433  528    0  238  10  458 -102  544  368  324 -298  84  300  446  122  -80 -228  -82 -208  42 -108
 +
  8              emu-v4  320 -198  386 -450  184  32  174 -306    0 -414  402 -126  428  -38    2 -438 -188  406  -12  116 -184 -306 -162 -212 -250 -286
 +
  9      flood-curse-v4  628  312  62    2  718  478  140  242  380    0  882  440  914  692  406 -152  334  546  850  332  224  -64  312  -73  500  162
 +
  10            greedy-v4    34 -412 -126 -474  230 -184  182 -234 -348 -632    0 -434  398 -210 -236 -588 -436  60  102 -230 -500 -604 -412 -538 -392 -538
 +
  11          kalanera-v2  922  108  660  26  714  380  548  104  90  60  512    0  568  518  282 -234  -32  386  588  312  164  -86 -248  -22  324  126
 +
  12        leprechaun-v3  398 -348  204 -404  168  66 -348 -646 -150 -482    8 -394    0  152 -242 -628 -450  128  144 -172 -232 -434 -524 -514 -512 -392
 +
  13  luck-of-the-sea-v2  462 -416  90 -120  338  130  10 -312  114 -214  594 -132  62    0  278 -256 -378  92  216  166 -396 -370 -378 -228  80 -282
 +
  14            nexus-v1  494 -254  244 -130  452  250  -44  74 -168 -210  456 -104  456  146    0 -302 -364  406  238  96  -20 -320 -362  -60  -42 -162
 +
  15              noe-v4  746  342  678  278  786  662  554  528  578  386  692  356  854  600  432    0  688  656  710  304  488  148  336  156  426  228
 +
  16          ourmine-v1  597  100  662  82  732  484  520  104  138  152  548  386  806  348  236    6    0  378  608  374  48  -4  174  46  212  10
 +
  17            peeves-v3  224 -758 -220 -690  464  364  16  -80  70 -1096  24 -946  10  378 -150 -1300 -650    0  348  50 -670 -1588 -740 -1320 -860 -832
 +
  18          phoenix-v2  106 -310 -242 -480 -164 -484 -456  -84  46 -594 -426 -510  338 -428 -282 -508 -518 -140    0 -420 -186 -738 -438 -406  -78 -338
 +
  19              taf-v1  310 -318  -90 -250  334  -2  180 -190  -44 -290  468 -186  98  42  -90 -316 -278  214  200    0 -194 -374 -278 -170 -118 -180
 +
  20        terminator-v4  747  306  494  360  650  450  624  240  272  68  740  292  566  510  486 -178  -16  344  662  476    0  -72  82  -14  300  -98
 +
  21 the-flood-of-bash-v5  560  350  348  202  790  560  456  324  426  274  826  258  804  634  592 -108  272  694  680  410  310    0  366  148  406  150
 +
  22 thinker-destroyer-v3  630  194  646  -80  606  478  572  74  138 -324  540  134  732  430  482 -386  82  374  624  418 -142 -318    0  -12  228    0
 +
  23            timus-v1  833  327  746  361  880  468  622  416  536  220  690  404  794  422  418  100  620  638  852  590  466  298  586    0  336  230
 +
  24        trickster-v2  560  -48  448  -96  670  340  338  184    0 -206  532  34  934  108  -96 -470 -186  506  390  212  84 -286 -250 -282    0  76
 +
  25              uor-v3  378  68  378  34  624  328  404  126  -2 -242  544  28  976  88  326 -444  -2  256  568  126  152 -260  78    8  208    0
  
: n &ge; k &middot; p(2p + 1)
 
  
Desfacem parantezele și obținem:
+
Results on board 'board3'
  
: n &ge; 2 &middot; k &middot; p<sup>2</sup> + k &middot; p
+
  ID        Nume Program    0    1    2   3    4    5    6    7    8    9  10  11  12  13  14  15  16  17  18  19  20  21  22  23  24  25
  
Dacă scădem din expresia din dreapta acel k &middot; p atunci partea dreaptă se micșorează deci vom avea relația:
+
  0        alleks-bot-v2    0 -490  332 -214  278 -381  -22  10  -64 -172  -52  -44  430 -100  146 -450 -302  162  128  112 -436 -314 -302 -205 -234 -402
 +
  1        alphazero-v1  624    0  456  178  502  174  678  366  626  102  484  36  606  537  384 -110  -74  834  600  98  114 -254  -90  22  850  102
 +
  2      andrews-ark-v1  -74 -346    0  134  72 -138  358  -70  52 -222  102  -18  426  142  528 -570 -274  130  314  -50 -296 -518 -274 -678  228  32
 +
  3        bob-reborn-v2  184 -2500  422    0  536  400 -2500  227 -2500  -44  910  48 -2500  344  666 -298  12  834  876  776  467  244    8 -214  494  114
 +
  4            byoprg-v1  284 -542  118 -500    0 -136  -8  -52  380 -232 -108 -462  496  -48  362 -578 -740  20  344  200 -730 -362 -820 -388 -584 -132
 +
  5        chameleon-v1  311  126  664 -290  376    0  460  336  456  -32  -14  34  366  298  54 -164 -104  310  550  306 -402 -372 -104 -268  352 -282
 +
  6        clone-wars-v3  436  -8  424  174  652  34    0 -256  242  34  424  122  286  232  378 -134  -8  210  452  304    2  18  64  34  406  148
 +
  7        destroyers-v1  320  74  506 -190  728  -4  860    0  360 -166  672  -90  728  730  548  -2  314  652  686  724 -148 -232  -20  -8  442  -12
 +
  8              emu-v4  214 -178 -212  18  184  274  106  398    0 -172  332  -84  534  314  210  -4  -86  188  230 -468  60  110  354 -316  76  -42
 +
  9      flood-curse-v4  728  634  812  418 1030  270  756  489  742    0  898  98  986  722  674 -170  188  820  772  310  369  136  190 -234  568  143
 +
  10            greedy-v4  -312 -410  324 -454  382 -444 -124 -220  206 -232    0 -532    0 -126 -314 -568 -498 -276  326  30 -398 -410 -538 -796 -126 -350
 +
  11          kalanera-v2  596  176 1024    0  958  438  380  155  656  224  864    0  798  566  550 -116  72 1098  716  472  -40  96  222  -20  620  264
 +
  12        leprechaun-v3  -244 -344  -64 -478    2 -314 -200 -270  162 -322  -32 -462    0  108  168 -470 -316  176  -8  52 -368 -324 -316 -688  148 -430
 +
  13  luck-of-the-sea-v2    84 -260  664  -64  634  300  82  50  304 -404  238  -98  596    0  -16 -496 -264  138  354  330 -236 -358 -376 -302 -136  138
 +
  14            nexus-v1  316 -172  586  52  662  200  426  158  416  -24  28 -188  776  454    0 -490  142  -68  752  -26  26 -434  162 -228  362 -120
 +
  15              noe-v4  920  574 1006  576 1110  832 1002  710  798  682  958  620  798  900  790    0  656 1042  964  736  422  474  728  222  768  762
 +
  16          ourmine-v1  638  98  486  226  808  490  384  168  612  90  394  388  652  636  754  80    0 1076  552  760  253  -14  326  66  596  366
 +
  17            peeves-v3  -90 -328  -92 -162  338  196  266  -36  228 -304  468 -140  420  214  -22 -520 -160    0  794  92 -152 -352 -254 -408  -20 -344
 +
  18          phoenix-v2  -1364 -220  440 -218 -2092 -328 -416 -2086 -202 -394 -2074 -416  116  308 -500 -446 -256 -2054    0  -30 -566 -214 -296 -468 -274  146
 +
  19              taf-v1    84 -246  -40 -450  66 -230  -38 -430  34 -564  454 -634  326  270  -36 -716 -262  -30  480    0  60 -446 -398 -556 -118 -208
 +
  20        terminator-v4  666  134  854  364  922  510  764  560  -96 -136  454  206  848  622  724  -98  88 1022  766  460    0 -128  104 -286  176  286
 +
  21 the-flood-of-bash-v5  612  534 1060  512 1090  550  950  494  762  272  718    4  780  760  784    4    4 1050 1062  784    4    0  574 -122  567  336
 +
  22 thinker-destroyer-v3  742  -90  802  498  982  614  614  612  24  100  230  186  956  604  756 -408  34 1068  766  424  70 -248    0 -260  510  122
 +
  23            timus-v1  890    3 1044  622 1036  790  800  724  616  612 1058  684  794  918  610    3  642    3  824  868  634    3    3    0  910  584
 +
  24        trickster-v2  530  86  458  150  362  364  608  476  670  364  422  194  398  358  614 -342 -140  580  838  686  294 -270 -130 -290    0  386
 +
  25              uor-v3  259    3  828  16  592  448  492  564  550  94  556  110  500  494  418    3    2    3  814  748  272    3    3  112  700    0
  
: n > 2 &middot; k &middot; p<sup>2</sup>
 
  
De unde deducem:
+
</pre>
 +
Note:
 +
# S-au acordat 3 puncte pentru victorie, 0 puncte pentru înfrîngere.
 +
# Concurenți: dacă îmi trimiteți o descriere a metodei folosite și, eventual, o poveste despre cum v-a venit ideea și cum s-a născut acest joc, o voi posta aici.
  
: n / (2 &middot; k) > p<sup>2</sup>
+
Puteți vedea aici [[Media:2020-06-17-rezultat-oficial.zip|toate meciurile jucate]], mutare cu mutare.
  
: <math>p < \sqrt {n / (2 \cdot k)}</math>
+
== Jocul Pah-tum - rezultate neoficiale ==
 +
În acest concurs au jucat toate versiunile de programe trimise de voi care nu depășeau prea des timpul de mutare, un program al lui Mircea Rebengiuc trimis în afara concursului, programul invitatului Sebastian Pintilie, unele din programele de antrenament, precum și două programe scrise de mine cîndva pentru concursul ''Programmer of the Month''.
  
Dacă extragem pur și simplu radicalul din acea expresie este posibil să obținem un '''p''' prea mare, care să nu îndeplinească relația originală, deoarece am ignorat un termen în inecuație. De aceea va trebui să îl testăm și, dacă este prea mare, îl decrementăm, astfel:
+
Rezultatele concursului neoficial de Pah-tum sînt următoarele:
  
<syntaxhighlight>  p = sqrt( n/(2*k) );
+
Număr total de jocuri jucate: 18910.
  if ( k * p * (2 * p + 1) > n )
 
    p--;</syntaxhighlight>
 
  
==== Punctul doi ====
+
{| class="wikitable"
La punctul doi avem aceeași formulă:
+
!Loc
 +
!Program
 +
!Programatori
 +
!Scor
 +
|-
 +
|1
 +
|ab990
 +
|Cristian Frâncu
 +
|883
 +
|-
 +
|2
 +
|ab10
 +
|Cristian Frâncu
 +
|868
 +
|-
 +
|3
 +
|supreme-v4
 +
|Luca Ilie
 +
|795
 +
|-
 +
|4
 +
|supreme-v2
 +
|Luca Ilie
 +
|772
 +
|-
 +
|5
 +
|supreme-v3
 +
|Luca Ilie
 +
|754
 +
|-
 +
|6
 +
|newt-a5-v2
 +
|Ilinca Marcu
 +
|727
 +
|-
 +
|7
 +
|newt-a5-v3
 +
|Ilinca Marcu
 +
|717
 +
|-
 +
|8
 +
|hawkeye-v5
 +
|Teodor Tatomir
 +
|706
 +
|-
 +
|9
 +
|creed-v5
 +
|Teodor Togan
 +
|689
 +
|-
 +
|10
 +
|hawkeye-v4
 +
|Teodor Tatomir
 +
|674
 +
|-
 +
|11
 +
|hawkeye-v3
 +
|Teodor Tatomir
 +
|639
 +
|-
 +
|12
 +
|ttco-v3
 +
|Victor Nicola & Mihai Mocanu
 +
|629
 +
|-
 +
|13
 +
|hawkeye-v2
 +
|Teodor Tatomir
 +
|623
 +
|-
 +
|14
 +
|endgame-v2
 +
|Albert Aizic
 +
|623
 +
|-
 +
|15
 +
|sparr-part-4mp
 +
|Cristian Frâncu
 +
|611
 +
|-
 +
|16
 +
|hawkeye-v1
 +
|Teodor Tatomir
 +
|611
 +
|-
 +
|17
 +
|endgame-v1
 +
|Albert Aizic
 +
|586
 +
|-
 +
|18
 +
|robo-kiwi-v2
 +
|Andreea Chivu
 +
|581
 +
|-
 +
|19
 +
|muteb-hapla-v4
 +
|Mircea Rebengiuc
 +
|561
 +
|-
 +
|20
 +
|ttco-v1
 +
|Victor Nicola & Mihai Mocanu
 +
|555
 +
|-
 +
|21
 +
|creed-v4
 +
|Teodor Togan
 +
|533
 +
|-
 +
|22
 +
|robo-kiwi-v1
 +
|Andreea Chivu
 +
|530
 +
|-
 +
|23
 +
|pexy-v3
 +
|Ana Petcu
 +
|521
 +
|-
 +
|24
 +
|muteb-hapla-v3
 +
|Mircea Rebengiuc
 +
|504
 +
|-
 +
|25
 +
|pick-a-cow-v1
 +
|Remus Rughiniș
 +
|498
 +
|-
 +
|26
 +
|creed-v2
 +
|Teodor Togan
 +
|482
 +
|-
 +
|27
 +
|omicroncsi-v1
 +
|Tudor Grecu
 +
|480
 +
|-
 +
|28
 +
|bog-tum-v2
 +
|Bogdan Petrescu
 +
|475
 +
|-
 +
|29
 +
|creed-v3
 +
|Teodor Togan
 +
|470
 +
|-
 +
|30
 +
|bog-tum-v1
 +
|Bogdan Petrescu
 +
|452
 +
|-
 +
|31
 +
|error_404-v2
 +
|David Stancu
 +
|449
 +
|-
 +
|32
 +
|pah-bum-v2
 +
|Alexandru Benescu & Tudor Mușat
 +
|427
 +
|-
 +
|33
 +
|pah-bum-v1
 +
|Alexandru Benescu & Tudor Mușat
 +
|424
 +
|-
 +
|34
 +
|muteb-hapla-v2
 +
|Mircea Rebengiuc
 +
|409
 +
|-
 +
|35
 +
|pexy-v4
 +
|Ana Petcu
 +
|354
 +
|-
 +
|36
 +
|pexy-v5
 +
|Ana Petcu
 +
|344
 +
|-
 +
|37
 +
|play-for-fun-v2
 +
|Andrei Calotă
 +
|343
 +
|-
 +
|38
 +
|creed-v1
 +
|Teodor Togan
 +
|330
 +
|-
 +
|39
 +
|marvel-v1
 +
|Yusuf Fares & Alexandru Nicu
 +
|325
 +
|-
 +
|40
 +
|who-abt-v1
 +
|Sebastian Pintilie
 +
|320
 +
|-
 +
|41
 +
|pexy-v1
 +
|Ana Petcu
 +
|319
 +
|-
 +
|42
 +
|play-for-fun-v1
 +
|Andrei Calotă
 +
|306
 +
|-
 +
|43
 +
|pahtum-master-v1
 +
|Mircea Rebengiuc
 +
|303
 +
|-
 +
|44
 +
|marvel-v3
 +
|Yusuf Fares & Alexandru Nicu
 +
|292
 +
|-
 +
|45
 +
|supreme-v1
 +
|Luca Ilie
 +
|285
 +
|-
 +
|46
 +
|pexy-v2
 +
|Ana Petcu
 +
|251
 +
|-
 +
|47
 +
|enigma-v5
 +
|Ecaterina Ștefănescu
 +
|245
 +
|-
 +
|48
 +
|error_404-v1
 +
|David Stancu
 +
|230
 +
|-
 +
|49
 +
|sparr-part-1mp
 +
|Cristian Frâncu
 +
|212
 +
|-
 +
|50
 +
|marvel-v2
 +
|Yusuf Fares & Alexandru Nicu
 +
|210
 +
|-
 +
|51
 +
|pahtum-pahboom-v1
 +
|Lucian Badea
 +
|190
 +
|-
 +
|52
 +
|pick-a-cow-v2
 +
|Remus Rughiniș
 +
|180
 +
|-
 +
|53
 +
|newt-a5-v1
 +
|Ilinca Marcu
 +
|170
 +
|-
 +
|54
 +
|destroyers-v2
 +
|Alex Hossu & Vlad Burac
 +
|153
 +
|-
 +
|55
 +
|destroyers-v1
 +
|Alex Hossu & Vlad Burac
 +
|144
 +
|-
 +
|56
 +
|bob-v1
 +
|Armin Asgari & Tudor Voicu
 +
|128
 +
|-
 +
|57
 +
|π-soft-v1
 +
|Tudor Ghica & Tudor Popescu
 +
|101
 +
|-
 +
|58
 +
|pick-a-cow-v3
 +
|Remus Rughiniș
 +
|97
 +
|-
 +
|59
 +
|dagwood-v1
 +
|Rareș Iordache
 +
|78
 +
|-
 +
|60
 +
|procrastinator-v1
 +
|Elisa Ipate
 +
|54
 +
|}
  
: m = k &middot; p(2p + 1)
+
Rezultatele jocurilor individuale:
  
De data aceasta cunoaștem '''m''' și '''p''' și ni se cere '''k'''. De fapt nu cunoaștem '''m''' ci un număr ceva mai mare, '''n''', astfel încît relația corectă va fi:
+
Puteți vedea aici [[Media:2019-06-08-pahtum-unofficial-results.zip|toate meciurile jucate]], mutare cu mutare.
  
: n &ge; k &middot; p(2p + 1)
+
== Jocul Pah-tum - comparații între rezultatele oficiale și cele neoficiale ==
 +
Iată rezultatele neoficiale din care am păstrat doar cea mai bună performanță dintre toate versiunile unui program. Prima coloană conține locul în clasamentul neoficial al programelor unice, a doua coloană conține locul în clasamentul original:
  
Deoarece ne trebuie '''k''' vom scrie:
+
{| class="wikitable"
 
+
!Loc neoficial
: n / [p(2p + 1)] &ge; k
+
!Loc oficial
: k &le; n / [p(2p + 1)]
+
!Program
 
+
!Programatori
Punctul doi este mult mai simplu. Îl putem calcula pe '''k''' direct, astfel:
+
!Scor
 
+
|-
<syntaxhighlight>  k1 = n / p / (2 * p + 1);</syntaxhighlight>
+
|1
 
+
|1
Iată o soluție bazată pe aceste idei:
+
|supreme-v4
 
+
|Luca Ilie
<syntaxhighlight>#include <stdio.h>
+
|795
#include <math.h>
+
|-
 
+
|2
int main() {
+
|2
  FILE *fin, *fout;
+
|newt-a5-v2
  long long n, p1, k1, marte, ka, ki, t;
+
|Ilinca Marcu
  int k, p;
+
|727
 
+
|-
  fin = fopen( "exod.in", "r" );
+
|3
  fscanf( fin, "%lld%d%d", &n, &k, &p );
+
|4
  fclose( fin );
+
|hawkeye-v5
 
+
|Teodor Tatomir
  p1 = sqrt( n/(2*k) );
+
|706
  if ( k * p1 * (2 * p1 + 1) > n )
+
|-
    p1--;
+
|4
 
+
|3
  t = k * p1 * (2 * p1 + 1); // oameni transportati de pe marte
+
|creed-v5
  marte = n - t;            // oameni ramasi pe marte
+
|Teodor Togan
  ka = t / (2 * k) * k;      // oameni adusi pe ka
+
|689
  ki = n - marte - ka;      // oameni adusi pe ki
+
|-
 
+
|5
  if ( marte < 0 )
+
|5
    printf( "marte mai mic ca zero: %lld\n", marte );
+
|ttco-v3
 
+
|Victor Nicola & Mihai Mocanu
  k1 = n / p / (2 * p + 1);
+
|629
 
+
|-
  fout = fopen( "exod.out", "w" );
+
|6
  fprintf( fout, "%lld %lld %lld %lld\n%lld\n", p1, marte, ka, ki, k1 );
+
|6
  fclose( fout );
+
|endgame-v2
 
+
|Albert Aizic
  return 0;
+
|623
}</syntaxhighlight>
+
|-
 
+
|7
'''Observație''': remarcați că această soluție nu folosește bucle. Ea face atît de puține calcule încît poate fi executată și "de mînă", sau cu un calculator de buzunar, nu avem propriu zis nevoie de un program sau de un calculator.
+
|8
 +
|robo-kiwi-v2
 +
|Andreea Chivu
 +
|581
 +
|-
 +
|8
 +
|7
 +
|muteb-hapla-v4
 +
|Mircea Rebengiuc
 +
|561
 +
|-
 +
|9
 +
|13
 +
|pexy-v3
 +
|Ana Petcu
 +
|521
 +
|-
 +
|10
 +
|20
 +
|pick-a-cow-v1
 +
|Remus Rughiniș
 +
|498
 +
|-
 +
|11
 +
|9
 +
|omicroncsi-v1
 +
|Tudor Grecu
 +
|480
 +
|-
 +
|12
 +
|10
 +
|bog-tum-v2
 +
|Bogdan Petrescu
 +
|475
 +
|-
 +
|13
 +
|12
 +
|error_404-v2
 +
|David Stancu
 +
|449
 +
|-
 +
|14
 +
|11
 +
|pah-bum-v2
 +
|Alexandru Benescu & Tudor Mușat
 +
|427
 +
|-
 +
|15
 +
|14
 +
|play-for-fun-v2
 +
|Andrei Calotă
 +
|343
 +
|-
 +
|16
 +
|15
 +
|marvel-v1
 +
|Yusuf Fares & Alexandru Nicu
 +
|325
 +
|-
 +
|17
 +
|16
 +
|pahtum-pahboom-v1
 +
|Lucian Badea
 +
|190
 +
|-
 +
|18
 +
|17
 +
|destroyers-v2
 +
|Alex Hossu & Vlad Burac
 +
|153
 +
|-
 +
|19
 +
|18
 +
|bob-v1
 +
|Armin Asgari & Tudor Voicu
 +
|128
 +
|-
 +
|20
 +
|19
 +
-soft-v1
 +
|Tudor Ghica & Tudor Popescu
 +
|101
 +
|-
 +
|21
 +
|21
 +
|dagwood-v1
 +
|Rareș Iordache
 +
|78
 +
|-
 +
|22
 +
|22
 +
|procrastinator-v1
 +
|Elisa Ipate
 +
|54
 +
|}

Revision as of 19:21, 24 June 2020

Lecție

Felicitări lui Mircea Rebengiuc care a cîștigat concursul cu programul the-flood-of-bash.

Concurs: jocul Flood Wars - rezultate oficiale

Notă: din cauza unor defecțiuni tehnice turneul a fost oprit prematur. Au fost jucate trei turnee complete, pe trei table diferite, pe fiecare tablă jucîndu-se 25 de runde. A mai fost jucat și un turneu incomplet, pe o a patra tablă, în care s-au desfășurat 22 runde din totalul de 25.

Rezultatele concursului de Flood Wars sînt următoarele:

Număr total de jocuri jucate: 2522.

Loc Program Programatori Scor
1 the-flood-of-bash-v5 Mircea Rebengiuc 267
2 flood-curse-v4 Tudor Mușat 249
3 ourmine-v1 Nicolas Teodorescu 222
4 kalanera-v2 Ana Petcu 216
5 terminator-v4 Teodor Togan 213
6 thinker-destroyer-v3 Alex Nicu & Bogdan Petrescu 208
7 alphazero-v1 Mihai Voicu 205
8 uor-v3 Luca Ilie & Tudor Ghica 198
9 bob-reborn-v2 Yusuf Fares & Armin Asgari 171
10 trickster-v2 Albert Aizic 168
11 destroyers-v1 Vlad Burac & Alexandru Hossu 147
12 nexus-v1 Rareș Iordache 136
13 chameleon-v1 Teodor Tatomir 117
14 emu-v4 Remus Rughiniș 103
15 clone-wars-v3 Ecaterina Ștefănescu 93
16 luck-of-the-sea-v2 Lucian Badea 87
17 andrews-ark-v1 Andrei Calotă 72
17 taf-v1 Victor Nicola & Mihai Mocanu 72
19 peeves-v3 Ilinca Marcu 66
20 greedy-v4 Radu Dobre 51
21 byoprg-v1 Tudor Grecu 48
21 leprechaun-v3 David Stancu 48
23 alleks-bot-v2 Alexandru Benescu 39
24 phoenix-v2 Vlad Dimulescu 18

Rezultatele jocurilor individuale:

Results on board 'board1'

  ID         Nume Program     0    1    2    3    4    5    6    7    8    9   10   11   12   13   14   15   16   17   18   19   20   21   22   23   24   25

   0        alleks-bot-v2     0  114   74  170  182  176  554  392  294  -88  340 -176  770  302  248 -200  -10  278 1010  268  -83 -144  -24 -148   36 -134
   1         alphazero-v1   702    0  572  556  938  534  444  580  812  327  828  396  894  796  508  150  326  726 1060  688  466  204  330  237  654  370
   2       andrews-ark-v1   368  -14    0   46  848   88  308  374  508  136  390   96  412  240  230   22  -60  834  926  494  -60 -168   -6   46   40  -10
   3        bob-reborn-v2   482  172 -2500    0  868  692  748 -2500  684  252 1020  291  926  952  368   58  172  922 1050  638  382  172  224 -2500  368  262
   4            byoprg-v1   288  216  292  282    0  114  180    8  162   34  378  256  328  126  -62  -62   30  752  598  472  188  -58  104  -66  172  -26
   5         chameleon-v1   376  -20  246 2500  712    0  312  328  724  -20  382   46  794  590   88  -66  -28  524  630  470  192  -94  -20   72  162   48
   6        clone-wars-v3   218  128  432   58  738  538    0  616  558  -18  256    2  754  638  346   70   58  644  966  410  150   -6   26 -122  228  258
   7        destroyers-v1   274   98  568  302  624  378  310    0  584  186  536   98  866  834  184  -18  180 1058  754  734  116  -80  152   12  392  268
   8               emu-v4   362  124  340  368  796  242  604  190    0   82  630  284  572  344   92  -42  284  398  766  276  446 -122  298   62  110  -20
   9       flood-curse-v4   694  738 1076  496 1062  786  778  466 1144    0  972  682  998  966  672  186  794  960 1030  850  534  280  790  369  766  502
  10            greedy-v4   566  -24  400   26  672   68  380  122  424  -92    0 -192  672  414  156   26  -38  614  656   90  312  -66  -38 -154    8  284
  11          kalanera-v2   350  312  782  654  940  592  554  834  482  304 1040    0  874  898  472  102  494  696 1310  794  458  286  388   70  554  314
  12        leprechaun-v3   558  -90  474  100  334  208  376  462  526 -100  376  -70    0  440  170 -214 -148  494  808  316 -206  -88   90   32  -40  276
  13   luck-of-the-sea-v2   600  134  526  -14  644  474  332  138  412   30  794  134  218    0   44 -212  154  364  950  578  144    2  152  -60   -2  130
  14             nexus-v1   680   18  630  348  804  426  456  504  484  -76  634  -78  540  598    0    2   18  804  830  506  -32  -22   18  -32  222  164
  15               noe-v4  1050  700 1012  638 1374  680  782  786  790  728  990  666  892  754  812    0  590 1274 1172  678  670  728  590  518  698  882
  16           ourmine-v1   630  784  720  558  946  568  620  560  630  176  982  418 1014  788  500  296    0  670 1066  616  352  158  368  232  380  370
  17            peeves-v3   664   88  734  136  474  264  340  312  566 -252  786  134  218  342  176   22  132    0  792  584  146 -164  156  110  -50  156
  18           phoenix-v2   306  -66  192  -64  958  152 -104   36  328 -322  414  -98  280  102 -100 -118 -276  514    0  318   82 -196 -274 -270   -4  140
  19               taf-v1   502   72  268  172  336  354  428  336  472  148  580   36  490  292  350  -76  238  676  700    0   62   46  274   55   94  358
  20        terminator-v4   728  332  778  622  894  710  396  674  458  174  714  448  878  742  600  188  524  830 1046  944    0  164  300  206  652  312
  21 the-flood-of-bash-v5   830  744  864 2500 1102  954  820  874 1150  546  996  948  862  734  830  324  638 1078 1010  872  614    0  638  440  836  702
  22 thinker-destroyer-v3   562  448  722  654  946  592  302  558  562  126  832  410 1014  746  500  140  308  670 1072  644  268  158    0  294  442  564
  23             timus-v1   845  966  906  722 1016 1044  824 1044 1114  596 1150  670  930  880  964  434  570 1249 1096  766  580  592  916    0  556  546
  24         trickster-v2   682  -68  374  504  558  682  558  416  454   92  510  138  804  560  518  124  -70  874 1076  698  356   74  -70   30    0  410
  25               uor-v3   704  194  796  266 1042  790  772  424  594  524  966  132 1018  994  522   46    6 1132 1142  536  406  362  176  104  402    0


Results on board 'board2'

  ID         Nume Program     0    1    2    3    4    5    6    7    8    9   10   11   12   13   14   15   16   17   18   19   20   21   22   23   24   25

   0        alleks-bot-v2     0 -242  142 -650   92 -156  -54 -484  -70 -554    0 -574  148 -134 -380 -572 -382  190   76 -172 -418 -606 -358 -678 -292 -772
   1         alphazero-v1   672    0  646   40  768  534  474  188  320  100  602   16  852  512  468 -294  126  292  542  408  -20 -256  138  -10  168  106
   2       andrews-ark-v1   278  -98    0 2500  368  130  236 -368 -238 -386   92 -310  -16 -172 -170 -618 -152   34  308 -208 -164 -582 -278 -710   46 -254
   3        bob-reborn-v2   598  208  440    0  626  492  272  242  318  -46 -2500  218  696  506  266 -190 -290  330  476  492   58 -278   26 -230  348   28
   4            byoprg-v1    94 -374  188 -516    0 -394  -10 -554 -382 -410   36 -458  112   76 -156 -624 -470  -32  316 -206 -372 -424 -530 -616 -690 -482
   5         chameleon-v1   169 -384 -146 -210  452    0  274 -254  -26 -496  542 -314  496  336  100 -440 -388  214  500   -8  -70 -432 -388 -172  -66 -328
   6        clone-wars-v3   106 -224   96 -412  424  132    0 -210 -346 -204  308 -358  478  208  -26 -544 -320   48  264 -214  -54 -500 -308 -630 -464 -330
   7        destroyers-v1   326  137  486  272  528  433  528    0  238   10  458 -102  544  368  324 -298   84  300  446  122  -80 -228  -82 -208   42 -108
   8               emu-v4   320 -198  386 -450  184   32  174 -306    0 -414  402 -126  428  -38    2 -438 -188  406  -12  116 -184 -306 -162 -212 -250 -286
   9       flood-curse-v4   628  312   62    2  718  478  140  242  380    0  882  440  914  692  406 -152  334  546  850  332  224  -64  312  -73  500  162
  10            greedy-v4    34 -412 -126 -474  230 -184  182 -234 -348 -632    0 -434  398 -210 -236 -588 -436   60  102 -230 -500 -604 -412 -538 -392 -538
  11          kalanera-v2   922  108  660   26  714  380  548  104   90   60  512    0  568  518  282 -234  -32  386  588  312  164  -86 -248  -22  324  126
  12        leprechaun-v3   398 -348  204 -404  168   66 -348 -646 -150 -482    8 -394    0  152 -242 -628 -450  128  144 -172 -232 -434 -524 -514 -512 -392
  13   luck-of-the-sea-v2   462 -416   90 -120  338  130   10 -312  114 -214  594 -132   62    0  278 -256 -378   92  216  166 -396 -370 -378 -228   80 -282
  14             nexus-v1   494 -254  244 -130  452  250  -44   74 -168 -210  456 -104  456  146    0 -302 -364  406  238   96  -20 -320 -362  -60  -42 -162
  15               noe-v4   746  342  678  278  786  662  554  528  578  386  692  356  854  600  432    0  688  656  710  304  488  148  336  156  426  228
  16           ourmine-v1   597  100  662   82  732  484  520  104  138  152  548  386  806  348  236    6    0  378  608  374   48   -4  174   46  212   10
  17            peeves-v3   224 -758 -220 -690  464  364   16  -80   70 -1096   24 -946   10  378 -150 -1300 -650    0  348   50 -670 -1588 -740 -1320 -860 -832
  18           phoenix-v2   106 -310 -242 -480 -164 -484 -456  -84   46 -594 -426 -510  338 -428 -282 -508 -518 -140    0 -420 -186 -738 -438 -406  -78 -338
  19               taf-v1   310 -318  -90 -250  334   -2  180 -190  -44 -290  468 -186   98   42  -90 -316 -278  214  200    0 -194 -374 -278 -170 -118 -180
  20        terminator-v4   747  306  494  360  650  450  624  240  272   68  740  292  566  510  486 -178  -16  344  662  476    0  -72   82  -14  300  -98
  21 the-flood-of-bash-v5   560  350  348  202  790  560  456  324  426  274  826  258  804  634  592 -108  272  694  680  410  310    0  366  148  406  150
  22 thinker-destroyer-v3   630  194  646  -80  606  478  572   74  138 -324  540  134  732  430  482 -386   82  374  624  418 -142 -318    0  -12  228    0
  23             timus-v1   833  327  746  361  880  468  622  416  536  220  690  404  794  422  418  100  620  638  852  590  466  298  586    0  336  230
  24         trickster-v2   560  -48  448  -96  670  340  338  184    0 -206  532   34  934  108  -96 -470 -186  506  390  212   84 -286 -250 -282    0   76
  25               uor-v3   378   68  378   34  624  328  404  126   -2 -242  544   28  976   88  326 -444   -2  256  568  126  152 -260   78    8  208    0


Results on board 'board3'

  ID         Nume Program     0    1    2    3    4    5    6    7    8    9   10   11   12   13   14   15   16   17   18   19   20   21   22   23   24   25

   0        alleks-bot-v2     0 -490  332 -214  278 -381  -22   10  -64 -172  -52  -44  430 -100  146 -450 -302  162  128  112 -436 -314 -302 -205 -234 -402
   1         alphazero-v1   624    0  456  178  502  174  678  366  626  102  484   36  606  537  384 -110  -74  834  600   98  114 -254  -90   22  850  102
   2       andrews-ark-v1   -74 -346    0  134   72 -138  358  -70   52 -222  102  -18  426  142  528 -570 -274  130  314  -50 -296 -518 -274 -678  228   32
   3        bob-reborn-v2   184 -2500  422    0  536  400 -2500  227 -2500  -44  910   48 -2500  344  666 -298   12  834  876  776  467  244    8 -214  494  114
   4            byoprg-v1   284 -542  118 -500    0 -136   -8  -52  380 -232 -108 -462  496  -48  362 -578 -740   20  344  200 -730 -362 -820 -388 -584 -132
   5         chameleon-v1   311  126  664 -290  376    0  460  336  456  -32  -14   34  366  298   54 -164 -104  310  550  306 -402 -372 -104 -268  352 -282
   6        clone-wars-v3   436   -8  424  174  652   34    0 -256  242   34  424  122  286  232  378 -134   -8  210  452  304    2   18   64   34  406  148
   7        destroyers-v1   320   74  506 -190  728   -4  860    0  360 -166  672  -90  728  730  548   -2  314  652  686  724 -148 -232  -20   -8  442  -12
   8               emu-v4   214 -178 -212   18  184  274  106  398    0 -172  332  -84  534  314  210   -4  -86  188  230 -468   60  110  354 -316   76  -42
   9       flood-curse-v4   728  634  812  418 1030  270  756  489  742    0  898   98  986  722  674 -170  188  820  772  310  369  136  190 -234  568  143
  10            greedy-v4  -312 -410  324 -454  382 -444 -124 -220  206 -232    0 -532    0 -126 -314 -568 -498 -276  326   30 -398 -410 -538 -796 -126 -350
  11          kalanera-v2   596  176 1024    0  958  438  380  155  656  224  864    0  798  566  550 -116   72 1098  716  472  -40   96  222  -20  620  264
  12        leprechaun-v3  -244 -344  -64 -478    2 -314 -200 -270  162 -322  -32 -462    0  108  168 -470 -316  176   -8   52 -368 -324 -316 -688  148 -430
  13   luck-of-the-sea-v2    84 -260  664  -64  634  300   82   50  304 -404  238  -98  596    0  -16 -496 -264  138  354  330 -236 -358 -376 -302 -136  138
  14             nexus-v1   316 -172  586   52  662  200  426  158  416  -24   28 -188  776  454    0 -490  142  -68  752  -26   26 -434  162 -228  362 -120
  15               noe-v4   920  574 1006  576 1110  832 1002  710  798  682  958  620  798  900  790    0  656 1042  964  736  422  474  728  222  768  762
  16           ourmine-v1   638   98  486  226  808  490  384  168  612   90  394  388  652  636  754   80    0 1076  552  760  253  -14  326   66  596  366
  17            peeves-v3   -90 -328  -92 -162  338  196  266  -36  228 -304  468 -140  420  214  -22 -520 -160    0  794   92 -152 -352 -254 -408  -20 -344
  18           phoenix-v2  -1364 -220  440 -218 -2092 -328 -416 -2086 -202 -394 -2074 -416  116  308 -500 -446 -256 -2054    0  -30 -566 -214 -296 -468 -274  146
  19               taf-v1    84 -246  -40 -450   66 -230  -38 -430   34 -564  454 -634  326  270  -36 -716 -262  -30  480    0   60 -446 -398 -556 -118 -208
  20        terminator-v4   666  134  854  364  922  510  764  560  -96 -136  454  206  848  622  724  -98   88 1022  766  460    0 -128  104 -286  176  286
  21 the-flood-of-bash-v5   612  534 1060  512 1090  550  950  494  762  272  718    4  780  760  784    4    4 1050 1062  784    4    0  574 -122  567  336
  22 thinker-destroyer-v3   742  -90  802  498  982  614  614  612   24  100  230  186  956  604  756 -408   34 1068  766  424   70 -248    0 -260  510  122
  23             timus-v1   890    3 1044  622 1036  790  800  724  616  612 1058  684  794  918  610    3  642    3  824  868  634    3    3    0  910  584
  24         trickster-v2   530   86  458  150  362  364  608  476  670  364  422  194  398  358  614 -342 -140  580  838  686  294 -270 -130 -290    0  386
  25               uor-v3   259    3  828   16  592  448  492  564  550   94  556  110  500  494  418    3    2    3  814  748  272    3    3  112  700    0


Note:

  1. S-au acordat 3 puncte pentru victorie, 0 puncte pentru înfrîngere.
  2. Concurenți: dacă îmi trimiteți o descriere a metodei folosite și, eventual, o poveste despre cum v-a venit ideea și cum s-a născut acest joc, o voi posta aici.

Puteți vedea aici toate meciurile jucate, mutare cu mutare.

Jocul Pah-tum - rezultate neoficiale

În acest concurs au jucat toate versiunile de programe trimise de voi care nu depășeau prea des timpul de mutare, un program al lui Mircea Rebengiuc trimis în afara concursului, programul invitatului Sebastian Pintilie, unele din programele de antrenament, precum și două programe scrise de mine cîndva pentru concursul Programmer of the Month.

Rezultatele concursului neoficial de Pah-tum sînt următoarele:

Număr total de jocuri jucate: 18910.

Loc Program Programatori Scor
1 ab990 Cristian Frâncu 883
2 ab10 Cristian Frâncu 868
3 supreme-v4 Luca Ilie 795
4 supreme-v2 Luca Ilie 772
5 supreme-v3 Luca Ilie 754
6 newt-a5-v2 Ilinca Marcu 727
7 newt-a5-v3 Ilinca Marcu 717
8 hawkeye-v5 Teodor Tatomir 706
9 creed-v5 Teodor Togan 689
10 hawkeye-v4 Teodor Tatomir 674
11 hawkeye-v3 Teodor Tatomir 639
12 ttco-v3 Victor Nicola & Mihai Mocanu 629
13 hawkeye-v2 Teodor Tatomir 623
14 endgame-v2 Albert Aizic 623
15 sparr-part-4mp Cristian Frâncu 611
16 hawkeye-v1 Teodor Tatomir 611
17 endgame-v1 Albert Aizic 586
18 robo-kiwi-v2 Andreea Chivu 581
19 muteb-hapla-v4 Mircea Rebengiuc 561
20 ttco-v1 Victor Nicola & Mihai Mocanu 555
21 creed-v4 Teodor Togan 533
22 robo-kiwi-v1 Andreea Chivu 530
23 pexy-v3 Ana Petcu 521
24 muteb-hapla-v3 Mircea Rebengiuc 504
25 pick-a-cow-v1 Remus Rughiniș 498
26 creed-v2 Teodor Togan 482
27 omicroncsi-v1 Tudor Grecu 480
28 bog-tum-v2 Bogdan Petrescu 475
29 creed-v3 Teodor Togan 470
30 bog-tum-v1 Bogdan Petrescu 452
31 error_404-v2 David Stancu 449
32 pah-bum-v2 Alexandru Benescu & Tudor Mușat 427
33 pah-bum-v1 Alexandru Benescu & Tudor Mușat 424
34 muteb-hapla-v2 Mircea Rebengiuc 409
35 pexy-v4 Ana Petcu 354
36 pexy-v5 Ana Petcu 344
37 play-for-fun-v2 Andrei Calotă 343
38 creed-v1 Teodor Togan 330
39 marvel-v1 Yusuf Fares & Alexandru Nicu 325
40 who-abt-v1 Sebastian Pintilie 320
41 pexy-v1 Ana Petcu 319
42 play-for-fun-v1 Andrei Calotă 306
43 pahtum-master-v1 Mircea Rebengiuc 303
44 marvel-v3 Yusuf Fares & Alexandru Nicu 292
45 supreme-v1 Luca Ilie 285
46 pexy-v2 Ana Petcu 251
47 enigma-v5 Ecaterina Ștefănescu 245
48 error_404-v1 David Stancu 230
49 sparr-part-1mp Cristian Frâncu 212
50 marvel-v2 Yusuf Fares & Alexandru Nicu 210
51 pahtum-pahboom-v1 Lucian Badea 190
52 pick-a-cow-v2 Remus Rughiniș 180
53 newt-a5-v1 Ilinca Marcu 170
54 destroyers-v2 Alex Hossu & Vlad Burac 153
55 destroyers-v1 Alex Hossu & Vlad Burac 144
56 bob-v1 Armin Asgari & Tudor Voicu 128
57 π-soft-v1 Tudor Ghica & Tudor Popescu 101
58 pick-a-cow-v3 Remus Rughiniș 97
59 dagwood-v1 Rareș Iordache 78
60 procrastinator-v1 Elisa Ipate 54

Rezultatele jocurilor individuale:

Puteți vedea aici toate meciurile jucate, mutare cu mutare.

Jocul Pah-tum - comparații între rezultatele oficiale și cele neoficiale

Iată rezultatele neoficiale din care am păstrat doar cea mai bună performanță dintre toate versiunile unui program. Prima coloană conține locul în clasamentul neoficial al programelor unice, a doua coloană conține locul în clasamentul original:

Loc neoficial Loc oficial Program Programatori Scor
1 1 supreme-v4 Luca Ilie 795
2 2 newt-a5-v2 Ilinca Marcu 727
3 4 hawkeye-v5 Teodor Tatomir 706
4 3 creed-v5 Teodor Togan 689
5 5 ttco-v3 Victor Nicola & Mihai Mocanu 629
6 6 endgame-v2 Albert Aizic 623
7 8 robo-kiwi-v2 Andreea Chivu 581
8 7 muteb-hapla-v4 Mircea Rebengiuc 561
9 13 pexy-v3 Ana Petcu 521
10 20 pick-a-cow-v1 Remus Rughiniș 498
11 9 omicroncsi-v1 Tudor Grecu 480
12 10 bog-tum-v2 Bogdan Petrescu 475
13 12 error_404-v2 David Stancu 449
14 11 pah-bum-v2 Alexandru Benescu & Tudor Mușat 427
15 14 play-for-fun-v2 Andrei Calotă 343
16 15 marvel-v1 Yusuf Fares & Alexandru Nicu 325
17 16 pahtum-pahboom-v1 Lucian Badea 190
18 17 destroyers-v2 Alex Hossu & Vlad Burac 153
19 18 bob-v1 Armin Asgari & Tudor Voicu 128
20 19 π-soft-v1 Tudor Ghica & Tudor Popescu 101
21 21 dagwood-v1 Rareș Iordache 78
22 22 procrastinator-v1 Elisa Ipate 54