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)
|
