Pomoc pri zadatku? C

[MILANAG]

Ulaz:

U prvom redu standardnog ulaza nalazi se broj n (1 ,100000) koji predstavlja broj domina. U sledecih n redova se nalazi visina svake domine (1, 200). Rastojanje izmedu susednih domina je 1. Da bi jedna domina oborila drugu, rastojanje izmedu njih mora biti (strogo) manje od visine te domine.

Izlaz:

Na standardni izlaz treba ispisati broj domina koje ce pasti ako se gurne prva domina.
npr za ulaz 6 2 3 1 2 1 1 izlaz je 5




Mucim se vec par dana... ako neko ima ideju ili vidi gde ja gresim bila bih mu jako zahvalna kad bi mi pomogao
Inace evo moj kod:


#include<stdio.h>

int main(){
int n; /* broj domina */
int i, j;
int d[100]; /*niz duzina domina*/
int max=1;
int pom=1;

printf("Unesite broj domina:\n");
scanf("%d", &n);
if(n==0){
printf("Ne postoji nijedna domina!\n");
return 0;
}

printf("Unesite redom duzine domina:\n");
for(i=0; i<n; i++){
scanf("%d", &d);
}

for(i=0; i<n; i=i+pom){

if(d>1){
max+=d-1;

for(j=i; j<max; j++){
if((d[j]+j-1)>=max){
max=d[j]+j;
pom=j+1;
}
}
else pom=1;
}
}
else break;
}

if(max>n)
max=n;

printf("Sruseno je %d domina\n", max);

return 0;
}

 

[hirajgoagain]

je l samo susedne ili svaka sa svakom

 

[Vlado]

Još sam prošle godine učio programiranje, zaboravio sam dosta, ali ću sada da vidim detaljno zadatak, nadam se da ću ti moći pomoći. BTW, ako radiš u visual studiu, izbaci ti tačno u kome je redu greška... Na prvi pogled se čini da je dobro. Šta ti je dole ispisalo, koliko grešaka imaš u programu?

 

[Vlado]

Previše je ovo kompleksno za moje SREDNJOŠKOLSKO znanje iz programiranja. Rado bih ti pomogao, ali stvarno ne znam, sorry.

 

[MILANAG]

pokrenem ja program ali ne daje dobre rezultate... tj za neke primere izbaci dobro dok za druge ne npr ako imam 6 domina visine 3 1 3 1 1 1 onda mi izbaci dobro i za jos dosta primera ali sam nasla primer ako imam 9 domina gdje su visine 4 1 1 2 3 1 1 1 ne izbaci dobro, bas se mucim :/ ne znam ni sta da popravim ni gde gresim

Inace, ne samo susedne, treba da izbaci broj palih domina kad prvu gurnes.

Hvala vam

 

[programmer^]

Samo jedno pitanje, nije mi bas skroz jasno
Ako je visina 1, jel to znaci da ta domina nece da srusi sledecu posto visina nije veca od rastojanja izmedju?
A za svaku visinu koja je veca od 1 domina ce da srusi sledecu?

 

[MILANAG]

Pa da, ako je visina veca od jedan onda sledeca domina sigurno pada, a ako je 1 (radi se samo na celim brojevima) onda ona ne obara sledecu...

 

[programmer^]

Ali kako je onda u prvom primeru gde imas da su visine 6 2 3 1 2 1 1, izlaz 5?
Trebalo bi da domina sa visinom 3 srusi dominu sa visinom 1 i da tu stane, mislim pokusavam da skapiram... xD

 

[programmer^]

#include <stdio.h>

int main() {
    int n;
    
    printf("Unesite broj domina: ");
    scanf("%d", &n);
    
    int domine[n], i;
    
    printf("Unesite visine domina:\n");
    for (i=0; i < n; i++)
        scanf("%d", &domine[i]);
        
    for (i=0; i < n; i++)
        if (domine[i] == 1)
           break;
    
    if (i == n)
       printf("Sruseno je %d domina", n);
    else 
         printf("Sruseno je %d domina", i+1);
         
    return 0;
}

Ovo je neki kod za koji ja mislim da bi trebalo da radi
Ispisvace 3 u prvom primeru, zato sto ce prva sa visinom 2 da srusi drugu sa visinom 3, i druga ce da srusi trecu sa visinom 1 i tu ce da stane
Ja sam tako skapirao zadatak

 

[MILANAG]

u ovom primeru 6 2 3 1 2 1 1 gdje je izlaz 5 ovaj prvi broj 6 predstavlja broj domina pa tek onda idu visine... Tvoj kod ne radi na svim primerima, slozenije je malo od toga, najveca fora je u primerima gdje npr domina visine 5 rusi sledece 4 domine a npr druga domina od te 4 je veca od 5tice pa onda onda rusi neke domine zajedno sa tom prvo + jos neke...
Hvala u svakom slucaju

 

[MILANAG]

P.s domina visine 3 rusi dve domine bez obzira sto je iza nje prva 1, jer je ona dovoljno visoka da udari i ispred jedinice dominu...

 

[programmer^]

A ok, sad sam skapirao sta treba xD
Uradicu pa cu postaviti kod malo kasnije

 

[programmer^]

Evoo

#include <stdio.h>

int main() {
    int n;
    
    printf("Unesite broj domina: ");
    scanf("%d", &n);
    
    int domine[n];
    
    printf("Unesite visine domina:\n");
    for (int i=0; i < n; i++)
        scanf("%d", &domine[i]);
    
    if (domine[0] == 1)
       printf("Srusena je 1 domina");        
    else {
         int max=domine[0]-1;
         
         for (int i=1; i < n; i++) {
             if (i <= max)
             { 
                if (i+domine[i]-1 > max)
                   max=i+domine[i]-1;
             }
             
             else
                 break; 
         }
         
         if (max < n)
            printf("Sruseno je %d domina", max+1);
         else printf("Sruseno je %d domina", n);
    }
    
    return 0;
}

Ja mislim da je to to, proveravao sam i radilo mi je za sve, ali proveri i ti za svaki slucaj

 

[chaami]

Nisam baš siguran da je dozvoljeno kreirati dužinu niza na osnovu korisničkog unosa bez alociranja memorije.
ISO C90 ni ne dozvoljava tako nešto a ni na takmičenjima se ne prihvata, bez obzira što tvoj kompajler to uspeva da odradi. U konkretnom zadatku imamo mogućnost da unesemo do 100.000 domina, što je malo previše za stek. Sledeći program bi bio ispravna varijanta. Varijabilni niz pravimo tako što kreiramo pokazivač za koji nakon korisničkog unosa alociramo potrebnu memoriju.

#include <stdio.h>
#include <stdlib.h>

int main()
{
    int* domine;
    int i,n,hi=0;

    printf("Unesite broj domina: ");
    scanf("%d", &n);
    domine = (int*) malloc(n*sizeof(int));
    printf("Unesite visine domina:\n");
    for (i=0; i < n; ++i) scanf("%d", &domine[i]);
    for (i=0; i < (n-1); ++i)
    {
        if (hi<domine[i]) hi=domine[i]-1;
        else --hi;
        if (hi<1)break;
    }
    printf("Sruseno je %d domina", i);
    system("PAUSE");
    return 0;
}

 

[MILANAG]

Mislim da je to - to... Hvala ti do neba, sad kad vidim tvoj kod zao mi je sto nisam sama uspela Jos jednom, hvala ti

 

[MILANAG]

Nisam baš siguran da je dozvoljeno kreirati dužinu niza na osnovu korisničkog unosa bez alociranja memorije.
ISO C90 ni ne dozvoljava tako nešto a ni na takmičenjima se ne prihvata, bez obzira što tvoj kompajler to uspeva da odradi. U konkretnom zadatku imamo mogućnost da unesemo do 100.000 domina, što je malo previše za stek. Sledeći program bi bio ispravna varijanta. Varijabilni niz pravimo tako što kreiramo pokazivač za koji nakon korisničkog unosa alociramo potrebnu memoriju.

#include <stdio.h>
#include <stdlib.h>

int main()
{
    int* domine;
    int i,n,hi=0;

    printf("Unesite broj domina: ");
    scanf("%d", &n);
    domine = (int*) malloc(n*sizeof(int));
    printf("Unesite visine domina:\n");
    for (i=0; i < n; ++i) scanf("%d", &domine[i]);
    for (i=0; i < (n-1); ++i)
    {
        if (hi<domine[i]) hi=domine[i]-1;
        else --hi;
        if (hi<1)break;
    }
    printf("Sruseno je %d domina", i);
    system("PAUSE");
    return 0;
}

Hvala i tebi inace imas negde propust u kodu tj. ne radi za sve primere. Ali sto se tice alociranja memorije hvala sto si mi skrenuo paznju popravicu to.

 

[chaami]

Hvala i tebi inace imas negde propust u kodu tj. ne radi za sve primere. Ali sto se tice alociranja memorije hvala sto si mi skrenuo paznju popravicu to.

U pravu si ... umesto for (i=0; i < (n-1); ++i) treba for (i=0; i < n; ++i);
i na kraju umestoprintf("Sruseno je %d domina", i); treba printf("Sruseno je %d domina", i+1);

 

[Вук Вучко]

Nisam baš siguran da je dozvoljeno kreirati dužinu niza na osnovu korisničkog unosa bez alociranja memorije.
ISO C90 ni ne dozvoljava tako nešto a ni na takmičenjima se ne prihvata, bez obzira što tvoj kompajler to uspeva da odradi. U konkretnom zadatku imamo mogućnost da unesemo do 100.000 domina, što je malo previše za stek. Sledeći program bi bio ispravna varijanta. Varijabilni niz pravimo tako što kreiramo pokazivač za koji nakon korisničkog unosa alociramo potrebnu memoriju.

#include <stdio.h>
#include <stdlib.h>

int main()
{
    int* domine;
    int i,n,hi=0;

    printf("Unesite broj domina: ");
    scanf("%d", &n);
    domine = (int*) malloc(n*sizeof(int));
    printf("Unesite visine domina:\n");
    for (i=0; i < n; ++i) scanf("%d", &domine[i]);
    for (i=0; i < (n-1); ++i)
    {
        if (hi<domine[i]) hi=domine[i]-1;
        else --hi;
        if (hi<1)break;
    }
    printf("Sruseno je %d domina", i);
    system("PAUSE");
    return 0;
}

U pravu si, evo na primer u Dev Cpp je uspesno kompajliran kod, medjutim mislim da na takmicenjima ne priznaju bez dinamickog alociranja...
Cak u bilo koju literaturu da pogledas, videces da nije dozvoljen onaj nacin alociranja, vec je objasnjen princip dinamickog alociranja memorije.

 

[programmer^]

Ma znam ja za sve to, ali idem na takmicenja i dozovoljeno je onako kako sam ja uradio
Jeste da sam ja osnovna skola, ali sam isao i na takmicenje za srednje i sve je bilo dozvoljeno
Slazem se ja da je bolje to sto ste vi rekli, ali samo kazem da i ovo nije pogresno

 

[chaami]

Ma znam ja za sve to, ali idem na takmicenja i dozovoljeno je onako kako sam ja uradio
Jeste da sam ja osnovna skola, ali sam isao i na takmicenje za srednje i sve je bilo dozvoljeno
Slazem se ja da je bolje to sto ste vi rekli, ali samo kazem da i ovo nije pogresno

Ne bi bilo pogrešno da je neki manji niz u pitanju, ili neka manja matrica a ne niz od 100000 elemenata
Problem kod C varijabilnih nizova je što potrebnu memoriju alociraju na steku i postoji mogućnost da će da rade čak i ako na njemu nema dovoljno mesta, ali će i da puknu kada dođe do njegovog probijanja. Sa druge strane, slobodna memorija je mnooogo veća od steka i kad je alociraš ukoliko nema dovoljno memorije vratiće ti NULL pointer tako da možeš kulturno da zatvoriš program uz obaveštenje da nema dovoljo memorije. A to će se desiti tek ukoliko je potrebno alocirati memoriju za par milijardi elemenata . Pazi da ti ne uđe u naviku da alociraš bilo kakve velike nizove na steku.

 

[Миша]

А зашто морате да снимите све висине? Ја сам прилично убеђен да не морате.

Ал` ћу тек у јуну имати времена да се вратим на тему.

(измена)
У ствари, занима ме, да л` се рачуна и прва домина међу пале и да л` у примеру онда пада први` пет и то је то. `Фала.

 

[2paca.zwaka]

Imao sam ja sors negdje, nisam snimao sve domine msm, ako nadjem postavicu

 

[chaami]

А зашто морате да снимите све висине? Ја сам прилично убеђен да не морате.

Ал` ћу тек у јуну имати времена да се вратим на тему.

(измена)
У ствари, занима ме, да л` се рачуна и прва домина међу пале и да л` у примеру онда пада први` пет и то је то. `Фала.

Ne da si ubeđen, nego si milion% u pravu . Ne treba da se snima ništa.Ne treba nikakav niz, već se može direktno obrađivati ulaz kao što bi se obrađivao i niz.
Ali ja i dalje mislim da velike nizove ne treba gurati na stek

 

[chaami]

Imao sam ja sors negdje, nisam snimao sve domine msm, ako nadjem postavicu

Nešto ovako ... otprilike ...

#include <stdio.h>
#include <stdlib.h>

int main()
{
    int i,n,ulaz,hi=0;

    printf("Unesite broj domina: ");
    scanf("%d", &n);
    printf("Unesite visine domina:\n");
    for (i=0; i < n; ++i)
    {
        scanf("%d", &ulaz);
        if (hi<ulaz) hi=ulaz;
        if (hi<2){++i;break;}
        --hi;
    }
    printf("Sruseno je %d domina", i);
    system("PAUSE");
    return 0;
}

 

[Миша]

Тако некако. Ако сам добро разумео правила, то би изгледало овако:

#include <stdio.h>

int solve(FILE* in) {
  int n, reach, i, h;
  fscanf(in, "%d", &n);
  fscanf(in, "%d", &reach);
  
  for(i=1; i<n; i++) {
    fscanf(in, "%d", &h);
    if(i >= reach) {
      break;
    }
    if(i+h > reach) {
      reach = i + h;
    }
  }

  return i;
}

int main(void) {
  int result = solve(stdin);
  printf("%d", result);
  return 0;
}

Не дајте се ометати игром са stdin.