Diskuze: Zoradenie akcií

Neaktivní uživatel

Člen

Neaktivní uživatel:18.10.2017 23:00

Zdravím,
snažil som sa nato prísť sám, ale pri poslednom kroku by som potreboval poradiť Nechcem Vás oberať o veľa času, pomôže mi každý názor. Ide o jednoduché zoradenie poľa, ktoré musí spĺňať isté kritéria. Prikladám vzorový príklad vstupu a výstupu.
Na prvom riadku vstupu dostaneme vždy 3 čísla, ktoré znázorňujú počet rôznych možných akcií, počet závislostí medzi nimi a počet polí, ktoré budeme musieť usporiadať. Tak, ako idú zaradom som ich nazval n, m, q.
Nasleduje m riadkov( popisujúcich konkrétne závislosti). Dvojice, ktoré následujú nás informujú o kritériách zoradenia každého poľa. V poli po čísle akcie na ľavej strane už nikdy nemôže nasledovať akcia na pravej strane.
Následuje q riadkov, každý začína číslom, predstavujúcim počet akcií v poli, a pole samotné je naplnené číslami akcií v rozmedzí 1 až n.
Žiadne číslo na vstupe neprekračuje 100 000. Môžeme predpokladať, že každé pole sa dá týmto spôsobom zoradiť. Vypíšem len už zoradené polia. Konkrétny popis som urobil v kóde. Problém je, že na vzorovom priklade mii to funguje, ale nie je to správne riešenie. Vychádzal som z toho, že prechádzam pole zľava doprava a akcie na týchto miestach zoraďujem podľa pozorovania zavislosti a nasledujúcich akcií.

import java.util.Scanner;

class SpravnePoradie {

        public static void main(String[] args) {

                Scanner sc=new Scanner(System.in);

                int n, m, q;
                n= sc.nextInt();
                m=sc.nextInt();
                q=sc.nextInt();

                int[] A = new int[m];
                int[] B = new int[m];

                //naplnenie poli A,B
                for(int i=0; i< m; i++){
                        A[i]= sc.nextInt();     //po cisle A na i-tom riadku
                        B[i]= sc.nextInt();     //uz nemoze nasledovat cislo B na i-tom riadku
                }

                //naplnenie poli s akciami
                for(int i=0; i<q; i++){
                        int pocet_akcii = sc.nextInt();
                        int[] akcie = new int[pocet_akcii];
                        int vymena;

                        //naplnenie pola akcie qi-teho riadku
                        for(int x=0; x<pocet_akcii;x++){
                                akcie[x] = sc.nextInt();
                        }

                        //algoritmus
                        for(int j=0; j<pocet_akcii; j++){       //prechadza akcie
                                for(int k=0; k<m; k++){ //prechadza vsetky zavislosti medzi akciami
                                        if(akcie[j] == A[k] && akcie[j] != akcie.length-1){     //ak sa nachadza akcia v poli A && este nie je posledna
                                                for(int l=j+1; l<pocet_akcii; l++){     //tak hlada ci blokovane cislo je medzi zvysnymi akciami
                                                        if(B[k] == akcie[l]){   //ak sa blokovane cislo nachadza medzi akciami
                                                                //ak ano, tak jednoducho im vymeni poradia, ak nie tak nemusi menit
                                                                vymena = akcie[l];
                                                                akcie[l] = akcie[j];
                                                                akcie[j] = vymena;
                                                                break;  //dalej nemusi hladat
                                                        }
                                                }
                                                break;  //dalej nemusi hladat
                                        }
                                }
                                System.out.print(akcie[j]+" ");
                        }
                        System.out.println();
                }
        }
}

Odpovědět

18.10.2017 23:00

Neaktivní uživatelský účet

Petr

Člen

Petr:20.10.2017 15:40

Promin ale v tady tomto se neda orientovat.

nacti vsechna vstupni data pred vsemi cykly ze vstupniho souboru, cist to ze standardniho vstupu je extremne neprehledne a nachylne na chyby
dej sem ukazkovy vstupni soubor a ukazkovy vystup
kdyz uz musis pouzivat tolik promennych tak je nejak rozumne pojmenuj, m, n, q, i, x, j, k, l nejsou vhodne jmena, nic to nerika o tom co ta promenna vyjadruje a je v tom pak sileny gulas
zjevne potrebujes seradit nejake pole polozek, to se dela tak ze si nactes polozky do nejakeho listu a pak pouzijes napriklad Collections.sort:

https://docs.oracle.com/…ections.html - konkretne tuto metodu public static <T> void sort(List<T> list, Comparator<? super T> c), ktere predhodis list a komparator a ona ti to seradi.

Nahoru Odpovědět

20.10.2017 15:40

Neaktivní uživatel

Člen

Neaktivní uživatel:20.10.2017 15:58

Pardon uvedomujem si, že v tom je možno chaos. Ukážkový príklad vstupu a výstupu som preto priložil pod kód vo forme obrázku. Jednotlivé hodnoty som už vysvetlil hore, ale dokážem to aj jednoduchšie. Tú metódu si ešte musím naštudovať. Angličtina by nemala predstavovať problém:)

Nahoru Odpovědět

20.10.2017 15:58

Neaktivní uživatelský účet

Petr

Člen

Petr:20.10.2017 18:20

Jestli se mohu zeptat to je neco do skoly a nebo neco pro vlastni potrebu / do prace? Pokud je to druhy pripad pak bych zvolil uplne jiny druh vstupu - napr. json, yaml. Vystup mi taky neprijde velmi pouzitelny. K samotnemu razeni:
tady jsou priklady pouziti toho Collections.sort
https://stackoverflow.com/…an-arraylist
Obecne bych to cele prepsal Ted jak to mas vlastne michas nacitani vstupu se samotnym razenim dat. Prvne by jsi mel precist cely vstup, poukladat si data do nejakych struktur a pak s nimi pracovat.

Editováno 20.10.2017 18:21

Nahoru Odpovědět

20.10.2017 18:20

Neaktivní uživatel

Člen

Neaktivní uživatel:20.10.2017 18:50

Je to nejaká súťažná úloha, čiže vstup musí byť bohužiaľ tento ale rozhodne mi ide o pochopenie problému a jeho riešenia a nie o umiestnenie(umiestnenie je len číslo, ale znalosť je cennosť). Ďakujem, našiel som si k tomu teóriu, tak si zatiaľ urobím poznámky. Malo by to fungovať tak, že podľa prvého čísla q-teho riadku zistí veľkosť dátovej štruktúry, do ktorej bude ukladať čísla zvyšku riadku(nepotrebujeme poznať všetky riadky naraz). Akonáhle sa jedno z čísel nachádza na zozname A, tak potrebujeme zistiť či za týmto číslom nasleduje číslo zo zoznamu B(na tom istom indexe). Ak áno, tak ich musíme prehodiť (zadanie úlohy proste hovorí, že po čísle A už nikdy nesmie nasledovať B...). Teraz mi doplo, že musíme kontrolovať aj toto vymenené číslo rovnakým spôsobom ako to predchádzajúce.

Nahoru Odpovědět

20.10.2017 18:50

Neaktivní uživatelský účet

Jirka Jr

Člen

Jirka Jr:21.10.2017 12:28

to vypada na nalezeni algoritmu, ktery bude nejmin zdrzovat realtime obchodovani

vitez bude vyznamenan pochvalou a zadavatel bude mit k dispozici nejrychlejsi algoritmus zajistujici miliardy :-)

Nahoru Odpovědět

21.10.2017 12:28

B42P6

Člen

B42P6:21.10.2017 16:49

KSP? :-P Hneď mi bola tá úloha povedomá.
Nebudem ti tu pomáhať s riešením, ale ak ti mám dať tip, tak si skús vytvoriť pár vlastných vstupných súborov, či už cez nejaký iný program, alebo ručne, potom bude ľahšie nájsť problém. ;-)

Predtým ako začneš programovať nejaký algoritmus si skús nejaký vstup vyriešiť týmto algoritmom ručne na papier, ak máš chybu v základnej myšlienke algoritmu, v kóde budeš hľadať túto chybu tažko. :-)

P.S. Ak ti ide o skúsenosti a nie o umiesntenie, na konci každého kola sú zverejnené vzorové riešenia, aj s možnosťou nesútažneho otestovania programov

Nahoru Odpovědět

21.10.2017 16:49

'long long long' is too long for GCC

Neaktivní uživatel

Člen

Neaktivní uživatel:21.10.2017 17:10

Samozrejme, že to je ono. Veď som povedal narovinu, že to je súťažná úloha a poskytnuté riešenia si preštudujem. Nemusíš mi pomáhať. Ak máš pocit akéhosi ukrivdenia, že ma zaujíma, ako by postupovali v riešení iní, ako uvedie vzorové riešenie, tak sa ospravedlňujem a viac od teba nežiadam čas.

Nahoru Odpovědět

21.10.2017 17:10

Neaktivní uživatelský účet