Főoldal
Előadások
Feladatok
Archívum
Kutatás
Történet
1nf0
Elérhetőségek
FGyE
Támogatóink
2%
Képek
Feladatok

 

A megoldásokat a bittologatok@cs.ubbcluj.ro címre várjuk!

2. A Farkas Gyula Szakkollégium feladatai (2004-)

2.4. Matematika és informatika feladatok a 2005/2006-os tanévre:

*

2.3. Feladat: 2005. február 25.

Adott egy n csúcsú iranyított súlyozott gráf. Határozzunk meg egy minnél kisebb összköltségű hamiltoni láncot! Hamiltoni láncnak nevezünk egy olyan utat, mely a gráf tetszőleges csúcsából indul és minden csúcsot egyszer és csakis egyszer érint.

Bemeneti adatok: Az UGYNOK.IN állomány első sorában szerepel a gráf csúcsainak n és éleinek m száma. A következő m sor mindegyikében egy számhármas található (szóközökkel elválasztva): az első szám a kiindulási csúcsot jelzi, a második az érkezési csúcsot és a harmadik az él költségét.

Kimeneti adatok: Az UGYNOK.OUT állomány első sorába írjuk ki a megtalált legrövidebb hamiltoni lánc összköltségét. A kovetkező sorba pontosan n számot írjunk szóközzel elválasztva, mely a bejárt csúcsokat írja le, a bejárás sorrendjében.

Pontosítások: 1 <= n <= 1000; 1 <= m <= 10000.

Pontozás: Minden teszt esetében a legjobb megoldás kapja az elérhető maximális pontszámot, a többi program arányosan kevesebbet.

Határidő: 2005. április 21. 24 óra

*

2.2. Feladat: 2005. január 14.

A MOCSAR.IN állomány első sorában adottak 2<=N,M<=100 számok, melyek egy mátrix sorainak, illetve oszlopainak számát jelölik. A következő N sor mindegyikében M szám található szóközzel elválasztva, melyek értéke 0 vagy 1 lehet. Ez a mátrix egy mocsár térképét írja le, a 0 mocsaras vidéket, az 1 száraz területet jelöl.
A feladatunk lefedni a mocsarat minél több 1x2-es méretű betonlappal úgy, hogy a lefedés után fennmaradó mocsaras vidékek száma a minimális legyen. A betonlapokat elforgathatjuk.
A MOCSAR.OUT állomány első sorába írjuk ki a lefektetett betonlapok számát, majd a következõ sorokba minden betonlap által elfoglalt pozíciók koordinátáit, soronként négy számot, melyek rendre a sor és oszlop koordinátái az adott betonlap által lefedett két mezőnek.
Több optimalis megoldás esetén elég az egyiket kiíratni.
Példa:
MOCSAR.IN
4 5
0 0 1 1
0 0 0 0
0 1 0 0
1 1 1 0
MOCSAR.OUT
4
1 1 1 2
2 1 2 2
2 3 2 4
3 3 3 4
Time Limit : 1 mp

Határidő: 2005. február 25. 18 óra

*

2.1. Feladatok: 2004. november 12.

  • Matematika: A matematika feladatok letőlthetők *innen*.
  • Informatika:
    1. (Alkalmazás) Készítsük el az előadáson bemutatott effektek egyikét!
    2. (Algoritmika) A FAKT.IN állományból olvassuk be a 0<=N<=100 000 egész számot. A FAKT.OUT állományba írassuk ki rendre N! első számjegyét, utolsó számjegyét és számjegyeinek számát.
    Példa:
    FAKT.IN
    5
    FAKT.OUT
    1 0 3
    Time Limit: 1 sec.
    Pontozás: a kimeneti állománybeli számok helyes értéke rendre 40%, 10% és
    50%-át jelentik a pontszámnak

Határidő: 2004. november 26. 18 óra

Pontozás: letőlthető *innen*.

*

1. A Bittologatók feladatai (2002-2003)

1.3. Feladat: 2002. november 6.

Két matematikus (abszolút logikával rendelkeznek) ül egy padon. Arra sétál egy harmadik, mindkettőjük fülébe súg valamit, majd hangosan így szól: "Neked, első, megsúgtam két szám összegét, neked, második, megsúgtam ugyanannak a két számnak a szorzatát. Bármit beszélhettek egymással, csak a súgott számokat nem árulhatjátok el. Találjátok ki, hogy melyik a két szám, melynek összegét, illetve szorzatát megsúgtam." A két matematikus egyedül maradt a padon és gondolkozni kezdtek. Kis idő múlva megszólal az első:

- Én rájöttem arra, hogy te nem tudhatot meg, hogy mi volt az a két szám.
- Köszönöm, hogy szóltál, most már megvan a két szám, de te sem tudhatod meg, hogy melyek ezek. - válaszolta némi gondolkodás után a második.
- Köszönöm, hogy szóltál, most már én is tudom, hogy melyek ezek a számok! - felelte pár perc múlva az első matematikus.

(a.) Írjunk programot, amely a 3..100 intervallumban megkeresi a matematikus állításai alapján ezeket a számokat. (b.) Növeljük az intervallum felső határát, és próbáljunk szabályt keresni az újabb megoldások gyakoriságára, illetve a számok közötti összefüggésre.

Az a program nyer, amely leggyorsabban oldja meg a fenti feladatokat!

Határidő: 2002. november 20. 18 óra

Nyeremény: 1 díj: Könyvcsomag.

Nyertes: nem érkezett megoldás

*

1.2. Feladat: 2002. október 23.

Az 1..(2n) intervallumban írjuk fel az összes szám négyzetét, majd rendezzük őket párokba úgy, hogy egy-egy pár tagjainak összege prímszám legyen!

a12 + b12 = x1 , ahol x1 prím.
. . .
an2 + bn2 = xn , ahol xn prím.

Határidő: 2002. november 6. 18 óra

Nyeremény: 1 díj: Könyvcsomag.

Nyertes: nem érkezett megoldás

*

1.1. Feladat: 2002. október 9.

Írjunk algoritmust, mely 10 percnél kevesebb idő alatt 300 000 000-ig megkeresi a prímszámokat és soronként kiírja egy szövegállománba. A szövegállomány utolsó sorába írjuk be azt, hogy hány prímszámot találtunk.

Határidő: 2002. október 23. 18 óra

Nyeremény: 1 díj: SuSe Linux 7.2 install kit.

Nyertes: Deé Zsombor (informatika magiszteri)