Középiskolai Matematikai és Fizikai Lapok
Informatika rovattal
Kiadja a MATFUND Alapítvány
Már regisztráltál?
Új vendég vagy?

Fórum: Informatika kömal

  [1]    [2]    [3]    [4]    [5]    [6]    [7]    [8]    [9]    [10]    [11]    [12]    [13]    [14]  

Szeretnél hozzászólni? Jelentkezz be.
[289] Róbert Gida2014-11-14 14:25:19

Lejárt S91. feladatnál valami roppant gyenge tesztek lehettek. Igazából sokkal gyorsabb megoldást én sem tudok, mint a közölt, az &tex;\displaystyle O(n*S^2)&xet;-es megoldásnál nagyjából 360 milliós méretű tömböt kéne kiszámolni, ami 1 másodperc alatt nehézkesen fut le (&tex;\displaystyle S=6000,n=60&xet; esetén, használva az &tex;\displaystyle A\le B\le C&xet; trükköt).

De kb. még egy kilencszeres gyorsítás érhető el: az optimum ugyanis legfeljebb &tex;\displaystyle \frac S3+max(a_i)&xet;: haszáljunk mohó algoritmust, minden lépésben az kapja az ajándékot, aki eddig a legkisebb összértékben kapott (az optimum egyébként legalább &tex;\displaystyle \frac S3&xet;, de ez nem kell). Memóriában pedig elég &tex;\displaystyle O(S^2)&xet;.

[288] Róbert Gida2014-05-14 18:25:17

Régebben néhány versenyükön indultam, most nem vagyok aktív tag.

Előzmény: [287] Bélus, 2014-05-14 17:02:54
[287] Bélus2014-05-14 17:02:54

Topcoderezel?

Előzmény: [286] Róbert Gida, 2014-05-14 12:33:05
[286] Róbert Gida2014-05-14 12:33:05

Lejárt S89. megoldása: http://ideone.com/vJP729

[285] Róbert Gida2014-03-13 19:54:55

Nem tudom miért kell állandóan ilyen korán kirakni a megoldásokat.

Lejárt S87. megoldása: http://ideone.com/v5kOi1. Ránézésre rövidebb, mint a közölt.

[284] Róbert Gida2014-03-08 19:55:13

Nem sikerült megértened a feladatot.

Előzmény: [283] ferrari13, 2014-03-08 19:13:48
[283] ferrari132014-03-08 19:13:48

Mégegyszer próbálkozom, mert az előbb valamiért nem írta ki rendesen:

Egy segítséget szeretnék kérni az "i341" feladathoz.

Az M-01 megálló gondolom az első megálló, mivel oda 0 mp alatt ér oda, és ez csak akkor lehetséges, ha onnan indul.

Lesz mondjuk 4 felszálló, de ebből rögtön 0,4 le is száll (10 százalék), tehát aki felszáll, az száll le, mivel nincs még fent senki előtte.

A másik lehetőség, hogy már kezdetben van egy bizonyos számú ember a villamoson, de azt viszont nem írta a feladat.

[282] ferrari132014-03-08 18:31:30

Egy segítséget szeretnék kérni az "i341" feladathoz.

Az M-01 megálló gondolom az első megálló, mivel oda 0 mp alatt ér oda, és ez csak akkor lehetséges, ha onnan indul.

Az 1. járat esetén lesz 4 felszálló, de 10

A másik lehetőség, hogy már kezdetben van egy bizonyos számú ember a villamoson, de azt viszont nem írta a feladat.

[281] Weisz Ágoston2014-01-23 18:52:02

Igen, ez a lényeg. Ha érdekel a többi feladat, azokra is szívesen várok megoldásokat ;)

Előzmény: [280] Róbert Gida, 2014-01-16 10:38:46
[280] Róbert Gida2014-01-16 10:38:46

Valóban! Meg is találtam:

http://ideone.com/RJw0CN

Előzmény: [279] Weisz Ágoston, 2014-01-15 12:43:00
[279] Weisz Ágoston2014-01-15 12:43:00

Az ötlet jó. Van lineáris megoldás is ;)

Előzmény: [278] Róbert Gida, 2014-01-14 20:21:22
[278] Róbert Gida2014-01-14 20:21:22

Lejárt s85. gyors megoldása, némi magyarázattal:

http://ideone.com/ktBxy7

[277] Weisz Ágoston2013-12-30 12:55:50

Igen, különböző, tehát 3 értékes részsorozata van: a jelölésben az intervallum kezdete és vége fog szerepelni: (1, 1), (2, 2), (1, 2) a 3 különböző értékes részsorozat.

Előzmény: [276] Kurokawa, 2013-12-30 11:13:19
[276] Kurokawa2013-12-30 11:13:19

S. 85. Különbözőnek számít-e, az a két értékes részsorozat, amelyek elemei rendre megegyeznek, de az elhelyezkedésük különböző az eredeti sorozatban? Például az (1, 1) sorozatnak 3 vagy csak 2 értékes részsorozata van, ha C=1?

[275] Weisz Ágoston2013-10-30 08:36:30

Nem kell nagy szám aritmetikát programozni hozzá. Minden belefér a standard int-be (32 bites).

Előzmény: [274] ferrari13, 2013-10-28 17:50:12
[274] ferrari132013-10-28 17:50:12

Az "S" feladatnál a törés ára (o1,o2...,s1,s2...) értéke mennyi lehet maximálisan?

[273] Róbert Gida2013-10-11 21:08:42

Lejárt S82 megoldása némi megjegyzéssel: http://ideone.com/cfZHQ9. Tényleg gyors megoldás, nagyjából az input-output annyi időbe telik (scanf/printf-fel), mint maga az algoritmus. c++ algoritmusait, vagy lassabb rendezéseket sem használok, hogy mindenhol gyorsítsak. Bár remélem ezt gyors gépre rakjátok, nálam n=1000000-nál csak az input-output elvesz nagyjából 0.75 másodpercet (ha "NEM" a válasz, akkor persze ez kevesebb). (Persze scanf/printf-nél is van gyorsabb eljárás.)

[272] Fodor Zsolt2013-10-08 21:43:42

Azokat is, akik a válaszra válaszoltak, sőt, akik ezekre válaszoltak, stb.

Előzmény: [271] ferrari13, 2013-10-08 20:48:19
[271] ferrari132013-10-08 20:48:19

Az i325-ös feladatnak a 7-es részében "kik szerepelnek az innen induló levélfolyamban feladóként" feladatra csak azokat kell nézni, akik arra a levélre válaszoltak, vagy azokat is, akik a válaszra válaszoltak?

Példa: Be: 4-es levél a négyes levélre (10. levélként) érkezett egy válasz a 2-es levélküldőtől, majd 11. levélként érkezett egy válasz a 10-es levélre az 1-es levélküldőtől. Ilyenkor csak a 2-est vagy az 1-est is ki kell írni?

[270] Fodor Zsolt2013-10-06 22:14:10

A feladat végén szerepel egy zárójeles mondat: "Azonos levélszám esetén is elegendő 5 sort megjeleníteni."

Tehát pontosan 5 elemű listának kell lennie. Nem számít, hogy ki kerül bele a listába a holtversenyesek közül.

Előzmény: [269] Pacman, 2013-10-06 17:57:47
[269] Pacman2013-10-06 17:57:47

Kérdése az i325 feladat 5. alfeladatára vonatkozna. Hogy viselkedjen a kimenet, ha több levelező van holtversenyben, mint a még ki nem osztott helyek száma a ranglistán?

[268] Fodor Zsolt2013-10-01 14:07:29

Köszönöm, hogy jelezted a hibát.

Sajnos nem voltam elég figyelmes, a feladatban a 8. részhez kapcsolódó példa valóban hibás.

Az első sor helyesen: 1 ( 2 ( 5 6 ) 4 )

Előzmény: [267] Tegzes Tamás, 2013-09-29 10:24:10
[267] Tegzes Tamás2013-09-29 10:24:10

Kérdésem az I325. feladat 8. részére vonatkozik. A zárójelezés nem teljesen világos a számomra. A közzétett példa kimenetetben van, ahol az egy levélre érkezett válaszok sorszámai közös zárójelbe (5 és 6) kerülnek, míg van ahol külön zárójelbe (2 és 4). Mikor melyiket kell használni?

[266] Siegler Gábor2013-06-07 18:15:12

Az 1 betűs szavak rendezett tulajdonságúak.

Előzmény: [265] kataklizma, 2013-06-04 17:49:05
[265] kataklizma2013-06-04 17:49:05

Az I322-es feladat 4-es részében értelmezhető az 1 betűs szavak betűjének ábécé sorrendben léte?

  [1]    [2]    [3]    [4]    [5]    [6]    [7]    [8]    [9]    [10]    [11]    [12]    [13]    [14]