Novo

Forum kao aplikacija na telefonu

Dodajte forum na početni ekran i koristite ga kao aplikaciju, sa menijem na dnu ekrana.

Zadaci za savezno takmičenje iz informatike, Novi Sad, 6 juni 1992

Re: Zadaci za savezno takmičenje iz informatike, Novi Sad, 6 juni 1992 15.12.2024. u 17:51 · pre 23 meseca #2
Prvi nije definisao format fajla. Verovatno pretpostavlja neki standard koji se ucio u to vreme u skoli.
U svakom slucaju, ako zanemarimo nacin citanja, pretpostavljam da mozes samo da na pocetku izracunas sumu brojeva od 1 do 1000000 po formuli n(n+1)/2 i onda citajuci brojeve iz fajla samo oduzimas i na kraju ti ostane onaj koji nije u fajlu.
Drugi.. Me mrzi :)
Re: Zadaci za savezno takmičenje iz informatike, Novi Sad, 6 juni 1992 15.12.2024. u 19:04 · pre 23 meseca #3
Davno je bilo, a ako se dobro secam, bio sam (verovatno pogresno) pretpostavio da nema toliko velike promenjive da drzi taj max zbir, pa sam simulirao to sabiranje/oduzimanje u nizu. Jbg... Ali ideja je bila bas ta koju si naveo.

Moglo je da se radi u Pascalu ili C jeziku. Secam se da sam se mucio da nadjem editor i da kompajliram program na tom PC-ju, jer sam kod kuce radio na Commodore Amiga 500 C kompajlerima (Lattice C i Aztec C).



Re: Zadaci za savezno takmičenje iz informatike, Novi Sad, 6 juni 1992 15.12.2024. u 19:31 · pre 23 meseca #4
C ima long long koji je 64bit integer i moze da prihvati taj zbir.
No, kad malo bolje razmislis, i ne moras imati ceo zbir. Mozes sabirati i oduzimati u istom prolasku kroz petlju.
Code (c):

long result = 0;
for (int i = 1; i < 1000001; i++)
{
    result += i;
    result -= numberFromFile;
}
 


To je naravno sporije (mada u odnosu na citanje iz fajla zanemarljivo) ali mozes da upotrebis ako hoces manji tip.
Re: Zadaci za savezno takmičenje iz informatike, Novi Sad, 6 juni 1992 15.12.2024. u 20:03 · pre 23 meseca #9
Citat:
X Files:
Ne znam odakle mi to za velicinu tipa. Te 1992 godine C standard bio C89, i mislim da nije bilo nista preko 32bit long int. Ali ne mogu da tvrdim.

Moguce. Ja sam pogledao na wikipediji. Sa C-om nisam nista radio.. Veoma dugo :)
Re: Zadaci za savezno takmičenje iz informatike, Novi Sad, 6 juni 1992 15.12.2024. u 20:07 · pre 23 meseca #10
Sad sam priupitao ChatGPT-ja... To je ovo sto je scoolptor rekao - XOR!

// netestirano, samo kopirano

Code (c):

#include <stdio.h>

int main() {
    FILE *file;
    long int number;
    long int xor_full_range = 0;
    long int xor_file = 0;
   
    // XOR all numbers from 1 to 1000000
    for (long int i = 1; i <= 1000000; i++) {
        xor_full_range ^= i;
    }
   
    // Open the file containing the numbers
    file = fopen("numbers.txt", "r");
    if (file == NULL) {
        perror("Error opening file");
        return 1;
    }

    // XOR all numbers in the file
    while (fscanf(file, "%ld", &number) != EOF) {
        xor_file ^= number;
    }
   
    // Close the file
    fclose(file);
   
    // The missing number is the XOR of the full range XORed with the file numbers
    long int missing_number = xor_full_range ^ xor_file;
   
    printf("The missing number is: %ld\n", missing_number);

    return 0;
}
 
Re: Zadaci za savezno takmičenje iz informatike, Novi Sad, 6 juni 1992 15.12.2024. u 20:11 · pre 23 meseca #11
U to doba sam dosta radio sa masinskim jezicima, moguce da mi je XOR-ovanje i bilo palo na pamet, ali nisam bas umeo da primenim u ovu svrhu. XOR sam koristio za neke inverzije bitova i graciku prezentaciju trepereceg teksta, tipa PRESS ANY KEY TO CONTINUE...
Re: Zadaci za savezno takmičenje iz informatike, Novi Sad, 6 juni 1992 15.12.2024. u 20:18 · pre 23 meseca #12
Code:

long int xor_full_range = 0;
   
// XOR all numbers from 1 to 1000000
for (long int i = 1; i <= 1000000; i++) {
    xor_full_range ^= i;
}


moze da se optimizuje:

Code:

long int xor_full_range = 1000000;


Potpis
Low-level high-standard engineering.
Re: Zadaci za savezno takmičenje iz informatike, Novi Sad, 6 juni 1992 16.12.2024. u 01:18 · pre 23 meseca #13
Može i bez XOR-a.

Dovoljno je vršiti sabiranja po modulu 1000000. Naravno, XOR je brži.

Code (c):

long s = 0;

for (long i = 0; i < 999999; ++i) {
    s += i;
    s += 1000000-num_from_file;
    s %= 1000000;
}

long result = s + 1;


Ovde je long iskoriščen da bi se osiguralo da ima bar 32 bita. Tada je int imao 16 bita. U principu je korišćen Turbo Pascal. On je imao LongInt sa 32 bita.

https://turbopascal.org/wp-con...on_7.0_Language_Guide_1992.pdf
Potpis
Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.
Re: Zadaci za savezno takmičenje iz informatike, Novi Sad, 6 juni 1992 16.12.2024. u 11:43 · pre 23 meseca #15
Huh, ja sam išao na ta takmičenja, i 1992. godine sam bio u srednjoj školi, ali se nešto ne sećam da sam išao u Novi Sad. Čudno. Poznat mi je prvi zadatak, ali drugog se ne sećam. Trenutno nisam niguran ni kako bih ga rešio. Možda za svaku osobu da pratimo u kojim sve gradovima bi mogla da završi u koraku X, ali kako znati kada stati? Da li posle N, ili 2N, ko zna...
Re: Zadaci za savezno takmičenje iz informatike, Novi Sad, 6 juni 1992 16.12.2024. u 12:10 · pre 23 meseca #16
Ovaj drugi je baš zeznut.
Recimo, pretpostavimo da imamo 2 grada i dve osobe, ali u različitim gradovima.
Pošto u svakom potezu moraš da pomeriš sve osobe, te dve osobe bi stalno išle u onaj drugi grad, i nikada se ne bi srele u istom gradu.
Slična situacija je i sa 4 grada 1-2-3-4, dve osobe, jedna u 1 jedna u 4, nikada se ne bi srele.

Ovako, na prvi pogled, deluje mi da dve osobe mogu da se sretnu u istom gradu, samo ako je udaljenost izmeću dve osobe paran broj.
Možda?

Uzgred, najkarći put između bilo koja dva grada je trivijalno da se nađe, ali pitanje je da li bi osobe trebale da biraju najkraći put, ili bi bilo potrebno da idu napred-nazad, da bi se srele u istom gradu.
Re: Zadaci za savezno takmičenje iz informatike, Novi Sad, 6 juni 1992 16.12.2024. u 12:36 · pre 23 meseca #17
Drugi zadatak je verovatno nešto sa grafovima, dakle teorijsko računarstvo sa primenom na konkretan problem.

Prvi zadatak može na više načina, pitanje je da li postoji ograničenje memorije, ako to nije problem, učista se ceo fajl u memoriju, kreira heš tabela... ali, svakako je brže sa XOR, pošto se radi o INT brojevima, posebno što se verovatno čita linija po linija iz fajla, odnosno broj po broj.

Uopšteno, kad su u pitanju takvi problemi, u obe knjige "Programming Pearls" dati su primeri rešavanja nekih praktičnih problema, jedan od njih je bio da se sortira 27000 brojeva, pri čemu u memoriju može istovremeno da se smesti samo 1000 brojeva. Nekome možda to izgleda kako zezanje iz današnje perspektive, ali taj algoritam je kasnije našao primenu kod Big Data, kao i mnogi drugi.
Potpis
Blessed are those who can laugh at themselves, for they shall never cease to be amused.
Re: Zadaci za savezno takmičenje iz informatike, Novi Sad, 6 juni 1992 16.12.2024. u 12:45 · pre 23 meseca #18
Citat:
Mihajlo Cvetanović:
Huh, ja sam išao na ta takmičenja, i 1992. godine sam bio u srednjoj školi, ali se nešto ne sećam da sam išao u Novi Sad.

Nije tada bilo ni interneta, uglavnom se kroz casopise saznavalo ko je ko, ali se secam da je Jozef Kratica bio u organizaciji (čuveni autor "nerešivih zadataka"), a secam se da je na takmicenju bio i Ranko Lazić, koji je bio napisao i neku knjigu o programiranju na C jeziku.

Re: Zadaci za savezno takmičenje iz informatike, Novi Sad, 6 juni 1992 16.12.2024. u 12:49 · pre 23 meseca #19
Drugi bi bio zeznut da ima samo dva ili tri sata da se reši na takmičenju, ne bi ga ni načeo, a ovako ..

ma kako bili raspoređeni gradovi ako je topologija takva da su bar tri grada raspoređeni "u trougao" na primer a, b, i c, i povezani međusobno, uvek svi mogu da se nađu u istom gradu, jer recimo mogu oni iz a da idu u b, i obrnuto, dok ne pričekaju sve iz svih gradova, i onda u jednom potezu nađu se u gradu c.

Nezgodno je ako bi svi gradovi bili poređani na jednoj liniji, uslov da svaki bude povezan sa susednim je i dalje ispoštovan, mogli bi da se svi sretnu u istom gradu ako između bilo koje dve osobe postoji neparan broj gradova u kome nema niko u tom trenutku (ili udaljenost između dve osobe paran broj, kao kod djoka_I), ako postoji bar jedna situacija da je paran broj gradova u kojima nema niko u tom trenutku između dve osobe - nikad se svi ne sretnu u istom gradu.

I još ako su gradovi poređani u prsten, i svaki povezan sa dva susedna, ako je broj gradova u prstenu paran, isto kao prethodno, mora između bilo koje dve osobe da bude neparan broj praznih gradova da bi uspeli da se nađu svi u istom gradu. Ako je broj gradova u prstenu neparan, onda uvek mogu da se nađu u istom gradu, jer ako ne mogu na jednom kraju prstena, upite se u suprotnim smerovima pa se nađu na onom drugom "kraju" prstena .. ako nisam nešto smandrljao.

I na sve to još najkraće i najracionalnije trase ..
Re: Zadaci za savezno takmičenje iz informatike, Novi Sad, 6 juni 1992 16.12.2024. u 22:10 · pre 23 meseca #20
Da dam ideju za rešavanje drugog.

1. Odrediti komponente povezanosti grafa. Ako se na početku ne nalaze svi ljudi u istoj komponenti povezanosti, onda se ne mogu sresti. U suprotnom obrisati sve gradove koji se nalaze van komponente povezanosti u kojoj su ljudi na početku, kao i puteve u kojima je bar jedan od krajeva takav grad i preći na sledeći korak.

2. Ako se svi mogu sresti u jednom gradu, onda mogu nakon toga svi zajedno da odu u bilo koji drugi grad. Prema tome, odgovor na pitanje da li se mogu sresti u gradu X ne zavisi od izbora grada X.

Izabrati jedan od gradova (recimo onaj u kome se nalazi pr i čovek) i ispitati udaljenosti svih ljudi od tog grada. Ako su sve udaljenosti iste parnosti, onda je sretanje u tom gradu moguće za onoliko koraka koliko je najudaljeniji čovek udaljen od njega. Recimo, svi idu najkraćim putem u taj grad, pri čemu oni koji stignu ranije od nekog drugog, nakon što su stigli u taj grad najpre pređu iz tog grada u susedni, a potom se vrate i na taj način "čekaju" ostale. U suprotnom (ako ima udaljenosti iste parnosti), preći na sledeći korak.

3. Ako je jedno lice udaljeno paran broj koraka, a drugo lice udaljeno neparan broj koraka, onda da bi se sreli, jedno lice treba da stigne u taj grad putem iste dužine kao drugo lice, odnosno putem čija je dužina različita od parnosti najkraćeg puta. Dakle, ta osoba ima dva puta do tog grada različite parnosti, pa ako bi jednim od ta dva puta otišla u taj grad, a drugim se vratila, napravila bi ciklus neparne dužine. Obrnuto, ako postoji put neparne dužine, onda svaka osoba može otići do grada tog ciklusa, "obrnuti krug" i vratiti se na početno mesto i onda najkraćim putemmotići do grada u kome se svi sreću, čime "koriguje" parnost svog puta, pa je onda sretanje moguće.

Prema tome, treba ispitati da li postoji ciklus neparne dužine i to nam daje odgovor na pitanje da li se mogu sresti u istom gradu.

Ako postoji ciklus neparne dužine koji više od jednom prolazi kroz isti čvor, onda taj ciklus sadrži podciklus. Ako je taj podciklus neparne dužine, onda je on kraći ciklus neparne dužine, a ako je taj podciklus parne dužine, onda njegovim izbacivanjem iz većeg ciklusa dobijamo manji ciklus (od većeg ciklusa) koji je takođe neparne dužine. Najkraći ciklus neparne dužine ne prolazi dva puta kroz isti grad.

Najkraći ciklus neparne dužine nema dužinu manju od 3, niti veću od m=(n-1)/2*2+1 jer je to najveći neparan broj koji nije veći od n. Ako neki grad pripada tom clikusu, on pripada ciklusu dužine ne veće od m. Ako grad X ne pripada tom ciklusu, onda se iz njega može stići najkraćim putem dužine k koja nije veća od n-m do tog ciklusa, recimo grada Y, pa napraviti ciklus dužine m, pa se onda vratiti istim putem dužine k iz grada Y u grad X. Grad X pripada ciklusu dužine ne veće od 2*k+m<=2*(n-m)+m=2*n-m<=2*n-3.

Kako ispitati postojanje ciklusa neparne dužine? Izaberemo jedan grad X. Formiramo niz P dužine n takav da je P[ i ] bulovska vrednost koja nam govori da li se u određenom koraku osoba iz mesta X može naći u i-tom gradu. Recimo da je X nulti grad. Onda je na početku P[0]=true i P[ i ]=false za ostale vrednosti i jer na početku niz P opisuje stanje nakon 0 koraka. Ako niz u nekom trenutku opisuje skup gradova u kojima se osoba mogla naći nakon j koraka, onda se skup gradova u kojima se osoba mogla naći posle j+1 koraka određuje kao skup svih gradova koji su susedni nekom od gradova u kome je osoba mogla biti nakon j koraka. To radimo najviše 2n-3 puta, a zaustavljamo se kada nakon neparnog broja koraka grad X bude u skupu gradova opisanim sa P.

Dakle svaka osoba može da koriguje parnost svog puta gubljenjem vremena sa najviše 2n-3 koraka, nakon čega joj treba najviše n-1 koraka da stigne u grad susreta, pa se svi mogu sresti u istom gradu u najviše 3n-4 koraka.

4. Ako je sretanje moguće, ono je moguće u najviše 3n-4 koraka za n>=3 (da bi postojao ciklus neparne dužine), odnosno n-1 koraka u suprotnom. Najkraći putevi se određuju na sledeći način: Za svaku osobu se formura po jedan niz nalik na niz P iz prethodne tačke. To je zapravo matrica. Onda se to računa za svaku osobu kao niz P. Stajemo u koraku kada skupovi gradova u kojima se osobe mogu naći obuhvataju jedan isti grad (imaju neprazan presek). Da bismo pamtili puteve, trebaće nam zapravo trodimenzioni niz.

Potpis
Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.
Sviđa mi se1
Odgovori
Prijavite se da biste odgovorili u ovoj temi.PrijavaRegistracija

Premeštanje teme