Note de curs, clasele 9-12, 14 iunie 2013
Ca să încheiem perfect un an fantastic (puneți voi ghilimele unde considerați necesar), la ultima lecție vom avea un turneu! Trebuie să implementați un program care să se bată cu programele colegilor voștri într-un sistem campionat (fiecare cu fiecare). Strategiile pot fi ușor sau greu de implementat, fiind limitate doar de imaginația voastră.
Descrierea concursului
Pe Insula FarmPolis, locuitorii duc o viață simplă. Natura i-a binecuvântat cu pixeli roditori și ei trebuie doar să culeagă acești pixeli folosind un dispozitiv special de forma unui șoarece cu o roată. Este o îndeletnicire magică: nu cere deloc inteligență și totuși locuitorii nu se plictisesc deloc de ea! Uneori sunt așa mulți pixeli de cules, că locuitorii apelează la cunoscuții lor pentru ajutor. Teoretic, ajutorul este reciproc: A lucrează azi pe tarlaua lui B, iar B îi întoarce serviciul cu prima ocazie. Practic, însă, locuitorii au personalități foarte diferite. Unii cooperează, dar alții preferă să trișeze. În loc să întoarcă ajutorul primit, ei se duc să joace jocul lor favorit, League of DotaCraft.
Formal, o interacțiune între doi locuitori A și B se desfășoară în N reprize. Înainte de fiecare repriză, A și B stabilesc, simultan, independent și secret, dacă vor să coopereze sau să trișeze în acea repriză. Câștigurile lor pentru acea repriză sunt descrise în tabelul următor.
| B cooperează | B trișează | |
|---|---|---|
| A cooperează | A și B primesc câte 3 monede fiecare | A nu primește nimic; B primește 5 monede |
| A trișează | A primește 5 monede; B nu primește nimic | A și B primesc câte 1 monedă fiecare |
Câștigurile totale într-o interacțiune sunt, desigur, sumele câștigurilor în cele N reprize. Iată un exemplu pentru N = 5.
| repriza | strategia lui A | strategia lui B | câștigul lui A | câștigul lui B |
|---|---|---|---|---|
| 1 | cooperează | cooperează | 3 | 3 |
| 2 | cooperează | trișează | 0 | 5 |
| 3 | trișează | cooperează | 5 | 0 |
| 4 | trișează | trișează | 1 | 1 |
| 5 | cooperează | trișează | 0 | 5 |
| Total | 9 | 14 |
De-a lungul unui an, fiecare locuitor al Insulei interacționează exact o dată cu fiecare alt locuitor. La sfârșitul anului, jucătorul cu cele mai multe monede adunate câștigă.
Misiunea voastră este să programați personalitatea unui locuitor al Insulei.
Detalii tehnice
Partea de arbitraj și de raportare a clasamentului este deja făcută pentru voi. Voi trebuie să scrieți doar un program, în C sau C++, care să decidă strategiile pentru o singură interacțiune.
Programul va citi date de la intrarea standard (stdin / cin) și va scrie date la ieșirea standard (stdout / cout). Formatul este următorul:
- Citește N, numărul de reprize.
- Afișează strategia pentru prima repriză (1 pentru a coopera, 2 pentru a trișa)
- Citește strategia adversarului pentru prima repriză (1 dacă a cooperat, 2 dacă a trișat)
- ... ... ... ... ... ... ... ...
- Afișează strategia pentru a N-a repriză (1 pentru a coopera, 2 pentru a trișa)
- Citește strategia adversarului pentru a N-a repriză (1 dacă a cooperat, 2 dacă a trișat)
Subliniem că programul vostru nu știe cu care dintre ceilalți locuitori interacționează.
Restricții
- Important! După fiecare linie afișată, trebuie să goliți bufferul de ieșire printr-una din comenzile fflush(stdout) sau cout.flush(), în funcție de stilul de scriere folosit. Dacă nu faceți aceasta, arbitrul care coordonează interacțiunile nu va primi datele pe care voi le-ați tipărit, iar programul vostru va depăși timpul permis.
- N <= 200 (dar constant pentru toate interacțiunile)
- Limită de timp: 1 secundă pentru întreaga interacțiune
- Limită de memorie: 1024 KB
Exemplu
Iată codul-sursă pentru un program care joacă absolut aleator.
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
int main(void) {
int n, response, i;
srand(time(NULL));
scanf("%d", &n);
for (i = 0; i < n; i++) {
printf("%d\n", 1 + rand() % 2);
fflush(stdout); // Neapărat!
scanf("%d", &response);
}
}
Desigur, strategia voastră poate fi mai complexă de atât și poate ține cont de reacțiile adversarului.
Website
Site-ul pentru arbitrare + clasament este http://catalin.francu.com/farmpolis/www/ Fiți îngăduitori, este făcut foarte din scurt și nu va arăta niciodată prea bine.
Site-ul este interactiv. Odată ce trimiteți un program, el va interacționa cu toate celelalte programe, iar clasamentul va fi actualizat. Puteți trimite mai multe versiuni, dar numai ultima dintre ele va conta în clasamentul final.
