Saptamana trecuta a fost data tot o problema usoara. Desi eu vroiam sa fie o alta problema acolo, in cauza omisiunii unei inmultiri s-a transformat intr-una si mai usoara. Am fost chiar mirat cand am vazut ca numai doua persoane au raspuns. Se pare ca acest concurs intra intr-o perioada de declin. Cum nici noi nu mai avem idei de probleme prea multe, este posibil ca acest concurs sa se incheie inainte de finalul lui martie. Revenind, celor doi participanti din saptamana trecuta li se ofera un punct bonus pentru ca au fost singurii. Unul dintre ei, Liviu, a participat pentru prima data la concurs si, cum am promis saptamana trecuta, mai primeste jumatate de punct in plus. Din punct de vedere al solutionarii problemei Ciprian a gasit solutia cea mai eleganta dar nu a facut o oarecare verificare – inutila tinand cont de datele problemei. In total el acumuleaza 2p. Liviu a dat o solutie frumos argumentata dar care nu a fost perfecta deoarece implica si valori complexe. Cum nu am precizat deloc daca se permit sau nu asemenea valori i se ofera 0,75p pentru solutie. In total, el acumuleaza 2,25p. Clasamentul actual este:
- Ciprian 9p
- Laura ( si-a sters blog-ul
) 9p (8,5) - Dadatroll (dadatroll): 5p
- Liviu (logica betivului) 2p (2,25)
- Alex B 2p (1,5)
- Andrada 2p (1,5)
- CDG 2p (1,5)
- Lothlorien: 1p
- Iulia: 1p
- Alex (Seviyor): 1p
- Adrian: 1p
Problema de saptamana asta este una care a aparut de mult: se da un teren dreptunghiular, impartit in patratele de latura 1. Fie N si M numarul patratelelor de pe lungime si latime. Un copil sta in patratul x,y (x pe lungime). El porneste pe o diagonala (sa zicem ca d=1,2,3 sau 4 in functie de directia in care pleaca: 1 spre NE, 2 spre NW, 3 spre SW, 4 spre SE). Ne intereseaza in ce colt D ajunge (D are aceeasi semnificatie ca d: D=3 inseamna ca ajunge in coltul din sud-vest). In momentul in care ajunge la o margine se considera ca acest copil isi schimba directia de deplasare in acelasi mod in care si-ar schimba-o o raza de lumina (adica prin reflexie, la unghi identic cu cel de incidenta). Se cere dependenta functiei D=D(N,M,x,y,d). Pentru cate un punct bonus se cere raspunsul la intrebarile: exista patrate x,y din care s-ar parcurge tot terenul? Dar din care s-ar parcurge un drum egal cu lungimea diagonalei plus unu? Discutiile se vor face in functie de N,M.
Si tot ca un punct bonus, o problema care aparent nu are nici o legatura: se cere codul sursa al unui program care nu citeste nimic de la tastatura sau fisier si-si autoafiseaza codul sursa.
Si jumate de punct bonus celui care descopera legatura intre aceste doua probleme.
Bafta.
PS: pentru moderare includeti unul dintre cuvintele: program, diagonala, x, y, N, M, d, D, da , nu, copil, legatura
Later edit: am adaugat cateva detalii la comentarii, sper sa fie utile (adica sunt, sper sa va si foloseasca)
Pai daca N=3 si M=5 si X=3 si Y=1 si d=1 => D=1 si parcurgem tot terenul.
Pai daca N=M=3 si X=1 si Y=2 si d=1 => ne invartim in cerc (paralelogram de fapt) si tot nu reusim sa determinam un D… sau nu m-am prins eu prea bine ce ai vrut sa zici.
Da, exista cazuri in care nu iesim din careu prin nici un colt si Laura l-a sesizat. In acest caz, va rog sa atribuiti singuri si valoarea lui D corespunzatoare lui (in asa fel incat sa fie usor de scris functia ceruta).
Pe exemplul ei, am nevoie de o functie D astfel incat
D(3,3,3,1,1)=1 si
D(3,3,1,2,1)=? unde substituiti ? cu ce valoare vreti, diferita de 1,2,3 sau 4
Printre alte probleme – semnalate de Iulia – am descoperit ca nu am precizat cum se aleg coordonatele: va las placerea sa le alegeti cum va convine pentru a obtine o formula mai simpla (in fond trecerea de la un set de coordonate la altul nu este decat o translatie si o simetrie).
O alta problema este faptul ca exista doua moduri de a privi patratelele. Va rog sa folositi modul expus aici (numerele din patrat semnfica ordinea in care vor fi parcurse):
_________….
| | 2| | |….
————–….
|3 | | 1 | |…
—————-…
| | 4 | | |…
………………….
Daca ar fi plecat din 2 in aceeasi directie s-ar fi obtinut o situatie invalida, includeti si acest caz in formula (deci va trebui sa gasiti doua valori pentru D diferite de 1,2,3 si 4, una care sa semnfice un ciclu infinit si alta care sa semnifice o situatie invalida)
salut
n-am mai scris de mult pe aici si acu nu scriu cu intentia de a da vreo ezolvare la o anumita problena; am sa incerc totusi in vacanta asta sa vrezolv cate ceva
da sa lasam problemele caci oricum avem parte de ele in fiecare zi. doresc sa te felicit pentru rezultatele foarte bune obtinute la examene(petru<> poate fi foarte mandru de tine si pe buna dreptate). iti urez un viitor semestru si mai bun dar cu mai multe impliniri pe plan extrauniversitar caci de acum acolo se vor calcula aptitudinile noastre.
Eu nu prea inteleg cum e parcurgerea. In exemplul dat de tine eu as fi zis ca parcurgerea este asa:
_________….
| 3 | 2 | | |….
————–….
| 4 | | 1 | 7 |…
—————-…
| | 5 | 6 | |…
………………….
Deci nu o situatie imposibila. Nu prea inteleg. Astept detalii pe Y!M
.
Reiau parcurgerea. De data asta fac un fel de ASCII art: x inseamna celula goala si un numar inseamna ordinea de parcurgere.
x2xx…
3×1x…
x4xx…
xx5x…
……….
…. semnifica faptul ca nu este reprezentat un teren complet.
Si un caz invalid:
x1xx…
……… cand se incearca sa se mearga spre NE sau NW. E doar ceva legat de conventie. Daca nu va convine puteti conveni si altfel dar precizati conventia in care ati lucrat pentru a nu genera confuzii.
#include
#include
char *iulia=”#include%c#include%cchar *iulia=%c%s%c;%cint main()%c{%cprintf(iulia,10,10,34,iulia,34,10,10,10,10,10,10);%cgetch();%creturn 0;%c}”;
int main()
{
printf(iulia,10,10,34,iulia,34,10,10,10,10,10,10);
getch();
return 0;
}
long live google!!!….insa…legatura cu problema nu am gasit-o….am personalizat programul si l-am facut sa suporte getch()…ca asa imi place mie:P
ups….se pare ca stdio.h si conio.h au disparut insa intelegi tu
iata si functia care calculeaza D
#include
#include
int t(int i, int j, int n, int m){
if( (i==1) && (j==m) ) return 1;
if( (i==1) && (j==1) ) return 2;
if( (i==n) && (j==1) ) return 3;
if( (i==n) && (j==m) ) return 4;
return 5;
}
void mut(int *i, int *j, int *d, int n, int m){
int v[5]={0,-1,-1,1,1};
int u[5]={0,1,-1,-1,1};
if((*j==1)&&(*d==3)) *d=4;
else if ((*j==1)&&(*d==2)) *d=1;
else if((*j==m)&&(*d==4)) *d=3;
else if ((*j==m)&&(*d==1)) *d=2;
else if ((*i==1)&&(*d==2)) *d=3;
else if ((*i==1)&&(*d==1)) *d=4;
else if((*i==n)&&(*d==4)) *d=1;
else if((*i==n)&&(*d==3)) *d=2;
*i=*i+v[*d];
*j=*j+u[*d];
}
int D(int a, int b, int d, int n, int m){
int k,s1,s2,s3;
if(d==t(a,b,n,m)) return d;
k=d;
mut(&a,&b,&k,n,m);
s1=a; s2=b; s3=k;
do{
if (t(a,b,n,m)!=5) return t(a,b,n,m);
mut(&a,&b,&k,n,m);
}while((a!=s1)||(b!=s2)||(k!=s3));
return 5;
}
int main (){
int a[50][50];
int i,j,n,m,k,d;
printf(”dati numarul de linii si coloane ale matricii”);
scanf(”%d%d”,&n,&m);
for(k=1;k<=4;k++){
d=k;
printf(”\npentru cazul %d:\n”,k);
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
a[i][j]=D(i,j,d,n,m);
for(i=1;i<=n;i++){
printf(”\n”);
for(j=1;j<=m;j++)
printf(”%d “,a[i][j]);
}
}
getch();
return 0;
}
…inclusa intr- un program…..nu ai specificat dak e o functie matematica sau una de program
o observatie: daca N-1 si M-1 sunt prime intre ele nu exista patrate din care dak pleci intr-o directie oarecare sa intri intr-un ciclu infinit…