The Diary

Дневникът на Jul

< HomePage
!!! Понеже знам, че много от вас попадат тук търсейки за съвет свързан с хард- и софтуер вижте Компютърни Хитринки за именно тези постове в блога !!!
<- Дневника

Компютърни Хитринки

Сряда, 24 Май 2006

Четейки как всяка година завършващите училище издивяват все повече им се чудя и аз все повече на акъла. Най-голямата заблуда на Абитуриентите е, че си мислят че са свършили и че най тежкото е зад гърба им. Един жезъл са свършили! Това което ги чака е много повече и много по-гадно (освен ако от простотия, тяхна или чужда, не се убият по баловете)от това което е зад тях. Аз си мисля, че преди три години когато аз бях абитуриент, по-скоро съжелявах че училището свършва от колкото да се радвам. Но хора всякакви. И все пак да ни е честит 24 Май! На всички настоящи и бивши ученици, студенти и всички други научни дейци (като мен хехехе).

Днес се захванах да сгазя Google Code Jam състезанието ама явно съм излязъл от форма. За да не го пиша пак ще копилам тук съдържанието на мейла до кица относно конкурса. На който ще му е интересно той съдържа и описание и разбор на задачите. Предварително се извинявам за шльокавицата, тя е тук само заради мизерния 7-битов енкодинг на някой сървъри.

...uchastvah online na "Google Code Jam" - sustezanie po informatika organizirano ot Google. No sum poizlqzal ot forma - za zadachite imah 1 chas te bqha samo 2 i to sravnitelno mnogo lesni. No ne mi stigna vremeto da predam vtorata, teoretichnoto i reshenie i prakticheskata realizaciq na C++ bqha gotovi no ne ostana vreme da izchistq greshkite v neq, taka che na dali shte mina na sledvashtiq krug. Sega shte se opitam da vi pratq usloviqta do kolkoto si gi spomnqm za da moje da gi davate po kontrolni ili dori mislq che sa dosta dobri za 1vi krug na olimpiadata (pone purvata, vtorata moje bi e malko nad tova nivo) i t.n. Izobshto purvata e mnogo mnogo lesna a vtorata e mnogo pod nivoto na nashata nac. olimpiada. Bi minala nai mnogo na vtori krug.

1. Dadena e pravougulna matrica ot bukvi s razmeri m x n. da se opredeli minimalniq broi simvoli v neq koito trqbva da se promenqt za da moje vseki red i stulb da stane palindrom (da se chete ednakvo otpred nazad i obratno).

Primer :
ABC
DCD
ALM

Otgovor :
3

Obosnovka:
ABA
DCD (promenili sme purvi red treta bukva i treti red 2ra i 4ta bukva)
ABA

Komentar:

Ideqta na zadachata e che vseki 4 bukvi razpolojeni simetrichno sprqmo centura trqbva da sa ednakvi za da se obrazuva palindrom. Toest gledame kakvi sa tezi bukvi i broi broq na razlichnite. Estestveno nai dobre e da priravnim kum tazi bukva koqto se sreshta nai-mnogo naprimer ako imame ACDA za 4 takiva bukvi to e dobre Ci D da stanat A. Toest za tazi chetvorka trqbvat 2 smeni. Izobshto smenite sa ravni na broq na razlichnite bukvi minus 1 vinagi. I taka za vsqka chetvorka se sumira. NAi lesno e da se obhodi v dva vlojeni cikula gorniq lqv kvadrant na pravougulnika i za vsqk bukva tam da se izcisli borq na smenite taka slojnosta e (m / 2)*(n / 2) samoto borene na razlichnite bukvi az go realizirah s hesh tablica ot standartnite na C++ std::map za kluch polzvah bukvite a kato stoinost zapisvah kolko puti sum q vidql dosega.

2. Dadeni sa n na broi stancii po edna na vseki asteroid v edno asteroidno pole. Ideqta e da se osushtestvqva komunikaciq m/u vseki dve stancii s pomoshta na specialni luchi, kato dve stancii se orientirat edna kum druga i togava mogat da kominikirat pomejdu si. Edna stanciq moje da izprashta na dadeno razstoqnie, no cenata na tehnikata raste mnogo burzo s razstoqnieto, ot druga strana dve stancii otdalecheni na p kilometra ne e nujno da imat i dvete stancii s obhvat p zashtoto efekta na luchite e kumulativen. Toest ako ednata prashta na p - 100 a drugata na 100 to dvete mogat da komunikirat pomejdu si. Vuprosa e ako se znaet koordinatite na stanciite v triizmernoto prostranstvo (zadadeni kato troiki x,y,z) da se opredeli minimalnata cena na vsichki suorajeniq. Ili s drugi dumi po dadeni broi i koordinati na vscihki stancii da se izvede duljinata na lucha na nai-slabata stanciq. Ako sushtestvuvat nqkolko ekvivalentni resheniq za se izvede rezultata ot tova reshenie koeto ima nai-kus maksimalen luch (ako i po tozi kriterii nqma ednoznachno reshenie da se izvede tova s nai-kus vtori max. luch i t.n.).

Primer:
4
0 0 0
0 0 3
0 4 0
0 4 3

Otgovor:
2.5

Obosnovka:
*-------*
|.\_....|
|4..\_5.|
|.....\.|
*-------*
3

Toest trqbva luch s duljina 2.5 v vseki dve diagonalno protivopolojni stancii za da mogat da se vijdat. A Ako mahnem edna ot chetirite shte trqbva 2 stancii s luch s dujina 2.5 (v vurhovete na hipotenuzata) i ostanalata stanciq moje da mine s luch s duljina 1.5 Toest otgovora bi bil 1.5

Komentar:

Tuk ima malko poveche ideq. Purvo izchislqvam vsichki dvoiki razstoqniq m/u vseki dve stancii. Posle vzemam nai-dulgoto razstoqnie i prisvoqvam na dvete stancii v kraishtata mu duljina na lucha razstoqnieto razdeleno na 2. Sledva pak izchislqvane na razstoqnieto m/u vseki dve stancii (no veche kato otchitam che ima 2 stancii koito mogat da komunikarat na nqkakvo razsotqnie. Toest vseki put za tqh raztoqnieto se smqta kato razstoqnieto bez tehnite duljini na lucha. Pak izbiram nai-dulgoto razstoqnie i go razpredelqm m/u dvete stancii m/u koito e (v sluchai che ednata veche ima prisvoena duljina na lucha cqloto otiva za smetka na drugata (no ochevidno razstoqnieto koeto e ostanalo trqbva da e po kuso ot polovinata ot predishnot nai-dulgo inache bihme izbrali tazi dvoika na predhodnata stupka). Tova se povtarq dokato vsqka stanciq poluchi luch. I izvejdame rezulatata poluchen na poslednata stupka kato kraen rezultat. Estestveno tova reshenie ne moga da potvurdq che e vqrno zashtoto kakto kazah ne mojah da predam tazi zadacha navreme za da bude ocenena.

The Diary

Компютърни Хитринки

Коментари

Коментари

Коментари

Коментари