Programming Challenges

[Belphegor]

Idem da se ubijem momentalno.

[Todors]

Ja imam problem sa učitavanjem podataka na ovaj način iz uputstva.

Nisam uspeo 1. karakter da učitam. Sve ostale učita kako treba, ali mi to ništa ne znači. 1. karakter mi prepoznaje kao neki levi char i kada pokušam da ga parsujem izbaci grešku, jer ga ne prepoznaje kao broj.

Jedino da se ispred svega stavi jedan '\n' ili bilo koji drugi karakter, onda tako hoće da radi.

[EclipsE]

Zašto ne učitavaš int po int? (tačnije, po zadatku su koordinate veće ili jednake od 1 i manje ili jednake 1000, tako da možeš i unsigned short)
Pošto po onome što si ranije pričao, ti si čitao linije kao string a onda verovatno splittovao po spaceu i konvertovao u int

[Todors]

^Bojim se da te ne razumem.

C# ne može da učita int direktno iz konzole kao što može kod C/C++ a,

Već jedino preko metoda Console.Read() i Console.ReadLine(), koje vraćaju string i koje moraju da se parsiraju u vrednost.

Problem je samo 1. karakter i ne znam iz kojeg razloga neće da ga učita.
npr. ako je 1. karakter broj 1, .Net ga kapira kao đ.

Evo sad sam probao da sačuvam onaj .txt kao ansi umesto UTF-8, i onda ga lepo čita.

[Geomaster]

Unicode fajlovi na Windowsu, bar koliko sam primetio, svi imaju bajtove FF FE (Unicode byte order mark) i to je verovatno ono što tvoj kod čita.

[EclipsE]

Todors kaže:

^Bojim se da te ne razumem.

C# ne može da učita int direktno iz konzole kao što može kod C/C++ a,

Did not know that
Damn C#...

[Todors]

Nema veze, i onako big2 test rešava preko sat vremena .

Mislio sam da će ovo ići mnogo brže.

[Belphegor]

Geomaster kaže:

Unicode fajlovi na Windowsu, bar koliko sam primetio, svi imaju bajtove FF FE (Unicode byte order mark) i to je verovatno ono što tvoj kod čita.

UTF-8 ne moraju, btw. da ima BOM ne bi ja ima korektne podatke sa unosom pomocu cin-a. Zavisi mozda kako je on ucitavao one fajlove, da li je ubacivao u neki editor koji automatski dodaje BOM ili sta vec? Mada ne verujem zasto bi to radio. A cudi me da je bas đ jer FEFF ili FFFE ne bi trebalo da predstavljaju ni jedan karakter.

[Todors]

Da budem precizniji, ne đ već ď ili char = -1.

Nešto baguje

Mada mislim da razumem, on ga čuva kao ansi, a učitava kao utf-8, možda je tu problem.

[Belphegor]

-1

Note that you will not get a property value of -1 unless you perform one of the following actions: simultaneously press the Control modifier key and Z console key (CTRL+Z), which signals the end-of-file condition; press an equivalent key that signals the end-of-file condition, such as the F6 function key in Windows; or redirect the input stream to a source, such as a text file, that has an actual end-of-file character.

http://msdn.microsoft.com/en-us/libr...e.read.aspx#Y0

E sad otkud -1/eof na pocetku?

EDIT: E sad je valjda prosao challenge?
Kad se zaj... prvi put.
Evo ga src:

#include <iostream>
#include <vector>
#include <set>
#include <algorithm>

struct coords;
typedef unsigned short int ushort;
typedef unsigned long int ulong;
typedef std::set< coords > my_uq;
ushort X, Y, Z;
ushort*** voxel_matrix;

struct coords
{
    ushort x, y, z;
    ulong lin_inx;

    coords(ushort _x, ushort _y, ushort _z) : x(_x), y(_y), z(_z), lin_inx(x*X*Y+y*X+z) {}

    coords(const coords& o) : x(o.x), y(o.y), z(o.z), lin_inx(o.lin_inx) {}

    coords& operator = (const coords& o)
    {
        x = o.x;
        y = o.y;
        z = o.z;
        lin_inx = o.lin_inx;
        return *this;
    }

    bool operator < (const coords& o) const
    {
        return lin_inx < o.lin_inx;
    }
};

struct greater_size : public std::binary_function<const my_uq&,const my_uq&,bool>
{
    bool operator () (const my_uq& l, const my_uq& r) const
    {
        return l.size() > r.size();
    }
}; 

enum
{
    e_occupied  = 1,
    e_visited   = 2
};

inline bool is_occupied(ushort b)
{
    return b & e_occupied ? true : false;
}

inline bool is_visited(ushort b)
{
    return b & e_visited ? true : false;
}

inline void set_visited(ushort& b)
{
    b |= e_visited;
}

void find_adjacent_voxels(my_uq& sc, const coords& c)
{
    for(int ddx = -1; ddx <= 1; ++ddx)
    {
        for(int ddy = -1; ddy <= 1; ++ddy)
        {
            for(int ddz = -1; ddz <= 1; ++ddz)
            {
                int x = c.x + ddx;
                if(x < 0 || x >= X)
                {
                    continue;
                }
                int y = c.y + ddy;
                if(y < 0 || y >= Y)
                {
                    continue;
                }
                int z = c.z + ddz;
                if(z < 0 || z >= Z)
                {
                    continue;
                }

                coords current(x, y, z);
                
                ushort& vm = voxel_matrix[current.x][current.y][current.z];
                if(!is_visited(vm))
                {
                    set_visited(vm);
                    if(is_occupied(vm))
                    {
                        sc.insert(current);
                        find_adjacent_voxels(sc, current);
                    }
                }
            }
        }
    }

}

int main()
{
    std::cin >> X >> Y >> Z;
    std::vector< my_uq > v_result;
    voxel_matrix = new ushort**[X];
    for(ushort i = 0; i < X; ++i) 
    {
        voxel_matrix[i] = new ushort*[Y];
        for(ushort j = 0; j < Y; ++j)
        {
            voxel_matrix[i][j] = new ushort[Z];
        }
    }

    for(ushort i = 0; i < X; ++i)
    {
        for(ushort j = 0; j < Y; ++j)
        {
            for(ushort k = 0; k < Z; ++k)
            {
                std::cin >> voxel_matrix[i][j][k];
            }
        }
    }

    for(ushort i = 0; i < X; ++i)
    {
        for(ushort j = 0; j < Y; ++j)
        {
            for(ushort k = 0; k < Z; ++k)
            {
                ushort& vm = voxel_matrix[i][j][k];
                if(!is_visited(vm))
                {
                    set_visited(vm);
                    if(is_occupied(vm))
                    {
                        my_uq sc;
                        coords c(i, j, k);
                        sc.insert(c);
                        find_adjacent_voxels(sc, c);
                        v_result.push_back(sc);
                    }
                }
            }
        }
    }

    for(ushort i = 0; i < X; ++i) 
    {
        for(ushort j = 0; j < Y; ++j)
        {
            delete [] voxel_matrix[i][j];
        }
        delete [] voxel_matrix[i];
    }
    delete [] voxel_matrix;

    std::sort( v_result.begin(), v_result.end(), greater_size () );
    std::cout << v_result.size() << std::endl;
    for(std::size_t i = 0; i < v_result.size(); ++i)
    {
        std::cout << v_result[i].size() << std::endl;
    }

    return 0;
}

MG-RAY daj src i ostalo da vidim algo za ovo, zivo me interesuje.

[MG-RAY]

@Belphegor: Da, sada jeste...

Attachovao sam source. C# je u pitanju (fair warning, ima krš delova xD).

Za eventualno brze resenje mozete i ovo da implementirate:
http://en.wikipedia.org/wiki/Connect...onent_labeling

(mene je mrzelo)

Obzirom da si ti pobedio, možeš postaviti sledeći zadatak, ili to prepusti nekom drugom, tvoj izbor... Očigledno da je ovo bilo malo teže nego što sam mislio...

@Todors:

Ne znam odakle si dobio to. Sada sam otvorio .in fajlove u HEX editoru, nijedan nema ništa drugo sem podataka... Pogledaću tvoj source sada na brzaka..

[Belphegor]

Ako nije problem, nek' postavi neko drugi sledeci zadatak?

[EclipsE]

Imam slobodnog vremena tek u četvrtak, i imam neku ideju... mada, ako neko ima ideju i može to da realizuje brzo, nek objavi ovde

[MG-RAY]

Ako neko ima ideju za zadatak, možete je poslati PMom meni / EclipsE-u, ili neka ostavi poruku, da izorganizujemo sve...

Takođe, mislim da bi svi trebali da se složimo oko načina ocenjivanja zadataka. Ideje?

@Todors: Ako ti nije teško, posalji mi svoj source, da vidim u čemu je bio problem.

[Kosinus]

Svaka cast Belphegor-u za resenje i MG-RAY-u za postavljanje zadatka. Evo mog source-a, cisto da ljudi vide da moze da se uradi i na tezi nacin, a plus i da ne radi za sve primere

Link za source jer je predugacak za post.

Radi na primerima Small 1 i 2.

[Todors]

MG-RAY kaže:

Ako neko ima ideju za zadatak, možete je poslati PMom meni / EclipsE-u, ili neka ostavi poruku, da izorganizujemo sve...

Takođe, mislim da bi svi trebali da se složimo oko načina ocenjivanja zadataka. Ideje?

@Todors: Ako ti nije teško, posalji mi svoj source, da vidim u čemu je bio problem.

Naravno da nije problem .

[MG-RAY]

@Todors: Pregledah ti source, imao si jednu liniju viška:

var x = Console.ReadLine().Split(' ');
Time si procitao dimenzije world-a sa ulaza, ali, ispod si uradio ovo:

var voxel = new Voxel(Console.ReadLine().Trim().Split(' '));
Stim sto ti je priogram sada procitao "0 0 0 0 0", umesto dimenzija, obzirom da je to bio sledeći red, tako da je tvoj world bio inicijalizovan na veličinu 0.

Kada iskomentarišeš prvu liniju izgleda da radi.

OK, postavljam novi challenge u sledećoj poruci.

[MG-RAY]

Šipke

Ovo je još jedan algoritmski zadatak. Njegov autor je Belphegor.


Opis:

Kao zaposleni u jednom stovarištu građevinskog materijala dobili ste narudžbinu da isečete određen broj metalnih šipki na određenu dužinu.
"Sirove" šipke sa lega (polica za materijal) uzimate za obradu i one su takođe određene dužine.

Vaš zadatak je da ih isečete tako da se iskoristi što manji broj celih (sirovih) šipki.

Ulaz:


Podaci se čitaju sa standardnog ulaza. Prva linija sadrži pozitivan ceo broj L koji predstavlja dužinu sirove šipke.

U novom redu sledi broj N, koji označava parova podataka sa zahtevima za sečenje imate.

U svakom novom redu se nalazi N parova, C i W, razdvojenih praznim prostorom, gde je:
C - broj komada koji treba iseći, ceo broj.
W - dužina jednog komada, realni broj sa jednim decimalnim mestom.

(pogledati primer za pojašnjenje)


Izlaz:

Na standardnom izlazu ispisati sledeće:
Broj utrošenih šipki.


Ograničenja:
1 <= L <= 100000
1 <= N <= 100000
1 <= C <= 1000
1.0 <= W <= 1000.0

Podatke ne treba validirati.

Test Primeri:
TODO


Primer:

Spoiler za Ulaz:

15
7
4 7.2
8 2.5
9 1.8
2 5.1
7 1.8
1 12.6
5 3.3

Informacije:
Vaše rešenje u obliku .exe fajla postavite na ovde, na forumu.

Scoring:
Programi će biti testirani sa 10 slučajeva, svaki sa progresivno većim podacima.

Više poena dobija program koji je iskoristio što manje šipki.

Vremensko ograničenje je 30 sec.

Rok:
5. Februar, 23:59:59
(javite ako treba da se produži)

[Todors]

MG-RAY kaže:

@Todors: Pregledah ti source, imao si jednu liniju viška:

var x = Console.ReadLine().Split(' ');
Time si procitao dimenzije world-a sa ulaza, ali, ispod si uradio ovo:

var voxel = new Voxel(Console.ReadLine().Trim().Split(' '));
Stim sto ti je priogram sada procitao "0 0 0 0 0", umesto dimenzija, obzirom da je to bio sledeći red, tako da je tvoj world bio inicijalizovan na veličinu 0.

Kada iskomentarišeš prvu liniju izgleda da radi.

OK, postavljam novi challenge u sledećoj poruci.

Ah, nisam gledao koje falove šaljem. Poslao sam pogrešne. Tu sam nešto pokušavao da uradim.
Naravno da znam da tako neće da radi.

[MG-RAY]

I tako je i ovaj challenge završen... Dobio sam samo jedno rešenje, od EclipsE-a, source će biti postavljen na sajtu.

Neka neko postavi sledeći zadatak.