Citat: |
Zadatak: Bomboni (90 bodova)
U dječjem vrtiću "Tulipan" odgajateljica je djeci podijelila bombone. Ali, jao! Neka djeca dobila su manje bombona od drugih. Reći ćemo da je neko dijete uplakano ako svako drugo dijete ima strogo više bombona od njega. Odgajateljica je slaba na suze pa se i sama rasplače kad vidi uplakano dijete. Ona tada posegne za golemom vrećom bombona i uplakanom djetetu udvostruči broj bombona. Na primjer, ako uplakano dijete ima 3 bombona, dobit će još 3 bombona pa će imati 6 bombona. Ako se tada opet pojavi neko uplakano dijete, odgajateljica će učiniti isto, i taj će se postupak ponavljati dok god postoji bilo koje uplakano dijete. Ako u nekom trenutku nijedno dijete više nije uplakano, što znači da nijedno dijete nema manje bombona od svakog drugog djeteta, postupak se zaustavlja. Moguće je i da se postupak ponavlja beskonačno, a u tom će slučaju odgajateljica naručivati nove bombone iz tvornice kad god joj ponestane bombona. (Još nije poznato kako će ih platiti.) Napiši program koji, za dane početne količine bombona svakog djeteta, ispisuje njihove konačne količine bombona ako se postupak zaustavi, ili riječ "INFINITY" ako će postupak trajati beskonačno. ULAZNI PODACI U prvom retku nalazi se prirodan broj N (2≤N≤10), broj djece. U sljedećih N redaka nalaze se prirodni brojevi, manji od 100. To su količine bombona koje su dobila djeca od prvog do N-tog. IZLAZNI PODACI Ako se postupak u nekom trenutku zaustavlja, u jedini redak ispiši završni niz količina bombona, odvojene razmakom. Ako postupak traje beskonačno, ispiši samo riječ "INFINITY". PRIMJERI TEST PODATAKA ulaz 2 5 6 izlaz INFINITY ulaz 5 14 6 8 10 12 izlaz 14 12 16 20 12 |
Kod: |
1. Pronađi minimalni element niza a.
2. Ako je jedinstven, pomnoži minimalni element s 2 i vrati se na korak 1; inače ispiši niz. |
Kod: |
1. Učitaj niz a.
2. Izračunaj h(a). Ako je h(a)=0 ispiši "INFINITY", a inače izvedi algoritam za odplakivanje. |
Kod: |
1. Učitaj m.
2. Izračunaj h(m,m). Ako je h(m,m)=1, onda uđi u beskonačnu petlju, a inače stani. |
Kod: |
#include<stdio.h> #include<math.h> int minimal(int *a,int n) { int min=a[0],i; for (i=0;i<n;i++) if (a[i]<min) min=a[i]; return min; } int visekratnik(int a,int b) { int pom=b; while (a>pom) { pom*=2; } if (a==pom) return 1; return 0; } int check(int *a,int n, int min) { int i; for (i=0;i<n;i++) if(a[i]!=min&&visekratnik(a[i],min)==1) return 0; if (n>2) { int *b=a; for (i=0;i<n;i++) if (b[i]==min) b[i]*=2; int min1=b[0]; for (i=0;i<n;i++) if (b[i]<min1) min1=b[i]; if ((2*min)>=min1) return 0; } return 1; } int unique(int *a,int n, int min) { int br=-1,i; for (i=0;i<n;i++) if (a[i]==min) br++; return br; } void double_min(int *a,int n, int min) { int i; for (i=0;i<n;i++) if (a[i]==min) a[i]*=2; } int main(void) { int n,a[n],i,test=0,min; scanf("%d\n", &n ); for (i=0;i<n;i++) scanf("%d\n", &a[i]); min=minimal(a,n); while(unique(a,n,min)==0) { test=check(a,n,min); if (test==1) break; double_min(a,n,min); min=minimal(a,n); } if (test==1) printf("INFINITY\n"); else for (i=0;i<n;i++) printf("%d ", a[i]); printf("\n"); return 0; } |
output generated using printer-friendly topic mod. Vremenska zona: GMT + 01:00.