Check alle échte Black Friday-deals Ook zo moe van nepaanbiedingen? Wij laten alleen échte deals zien

Vlaamse Programmeerwedstrijd: oplossing van de vraag.

Pagina: 1
Acties:

  • 430xlkod
  • Registratie: Januari 2007
  • Laatst online: 05-07 23:11
Oké, eerst en vooral: deze wedstrijd is reeds afgelopen. Ik open dit topic enkel om tot een oplossing te komen omdat ik er zelf nieuwsgierig naar ben. Als dit niet geliefd is door de admins, dan mag hij per direct gesloten worden.

Oké, het vraagstuk is hier te lezen: http://www.vlaamseprogram...rent/opgaves/2/cijfer.pdf .

Hoe wij het hadden opgelost:
C#:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
private static TextReader stdin = System.Console.In;
        private static TextWriter stdout = System.Console.Out;
        private static StringBuilder totaal = new StringBuilder();

        static void Main(string[] args)
        {
            int aantal = int.Parse(stdin.ReadLine());
            for (int i = 0; i < aantal; i++)
            {
                int getal = int.Parse(stdin.ReadLine());
                for (int x = 1; x <= getal; x++)
                {
                    
                    totaal.Append(x.ToString());
                }
                String uitkomst = totaal.ToString().Substring(getal - 1, 1);
                stdout.WriteLine(uitkomst);
            }
        }


Echter kregen we steeds een 'OutOfMemoryException' wat ik wel wist dat ging gebeuren maar we hebben het niet opgelost gekregen. Mede door die reden ben ik wel gebrand op hoe we dit hadden moeten aanpakken.

We hebben ook geprobeerd de exception op te vangen, bij te houden waar we waren en dan de StringBuilder te clearen (null) en terug verder te gaan, maar dit wou hij ook niet doen.

Zin om mee te brainstormen?

  • RobIII
  • Registratie: December 2001
  • Niet online

RobIII

Admin Devschuur®

^ Romeinse Ⅲ ja!

(overleden)
Waarom zou je in godsnaam die héle string vasthouden? Een naïeve benadering zou met diezelfde lus werken en gewoon de string lengte van die alle voorgaande strings bijhouden. Meer dan een tellertje of 2 heb je niet nodig (en wat gefrot met tellertje.Tostring().Length :X ). Echter, je weet dat er 9 cijfers met lengte 1 zijn (<10) zijn, daarna 90 cijfers met lengte 2 (<100), dan 900 cijfers met lengte 3 (< 1000) etc. Daarmee alleen al kun je toch veel slimmer de lengte berekenen dan domweg een teller van 1 tot "opgave" laten lopen?

Misschien moet je Back to Basics eens lezen voor wat inzichten. Gelezen? Mooi, dan kan ik je nu zonder blikken of blozen uitmaken voor "Shlemiel" ;) Bedenk eens waarom je de eerste paar tiental/hondertal/miljoenen/whatever tekens in die stringbuilder überhaupt voor nodig hebt/bewaart? Die kun je toch meteen "wegmikken" nadat je hun lengte "gemeten" hebt? Sterker: er komt geen string noch stringbuilder aan te pas, noch hoef je in een dergelijke implementatie meer dan een "paar bytes" geheugen op te snoepen. In jouw implementatie ga je afhankelijk van de opgave al snel vele megabytes of nog grotere ordes aan geheugen vreten voor niets. En dan laat ik dus nog buiten beschouwing dat dit wel een héél erge brute-force methode is (ofwel: O(n)). Dit moet prima in ~ O(log n) (of misschien wel minder?) op te lossen zijn.

[ Voor 102% gewijzigd door RobIII op 20-04-2012 23:57 ]

There are only two hard problems in distributed systems: 2. Exactly-once delivery 1. Guaranteed order of messages 2. Exactly-once delivery.

Je eigen tweaker.me redirect

Over mij


  • Soultaker
  • Registratie: September 2000
  • Laatst online: 02:44
Dit moet prima in ~ O(log n) (of misschien wel minder?) op te lossen zijn.
Minder dan O(log k) kan niet omdat de grootte van de invoer al O(log k) is (exact floor(log(k)/log(10)) + 2 karakters, om precies te zijn) maar dat is inderdaad de juiste tijdcomplexiteit.

Je kunt wel met een gesloten formule het aantal cijfers van het getal waarvan je het cijfer print bepalen, maar waarschijnlijk is het makkelijker om een lusje te gebruiken.

Dit is trouwens A007376 in de Online Encyclopedia of Integer Sequences. Daar heb je tijdens de wedstrijd waarschijnlijk geen toegang toe, maar daarin kun je achteraf dit soort reeksen wel opzoeken.

[ Voor 48% gewijzigd door Soultaker op 21-04-2012 00:45 ]


  • 430xlkod
  • Registratie: Januari 2007
  • Laatst online: 05-07 23:11
RobIII schreef op vrijdag 20 april 2012 @ 23:07:
Waarom zou je in godsnaam die héle string vasthouden? Een naïeve benadering zou met diezelfde lus werken en gewoon de string lengte van die alle voorgaande strings bijhouden. Meer dan een tellertje of 2 heb je niet nodig (en wat gefrot met tellertje.Tostring().Length :X ). Echter, je weet dat er 9 cijfers met lengte 1 zijn (<10) zijn, daarna 90 cijfers met lengte 2 (<100), dan 900 cijfers met lengte 3 (< 1000) etc. Daarmee alleen al kun je toch veel slimmer de lengte berekenen dan domweg een teller van 1 tot "opgave" laten lopen?
Dat het niet de juiste benadering was had ik zelf ook al door natuurlijk.
We hebben datgene wat je daar opnoemt ook proberen te implementeren echter waren we al even bezig (ook met andere opgaves) en zag ik op een gegeven moment alles door elkaar :) .
In elk geval kan je doen zoals jij zegt, lengte van het getal opvragen en dan al kan je een heleboel laten vallen. Ik ga het nogmaals proberen :) .
EDIT:
Tevens, als je dit leest dan noem ik jou: "ben-je-zelf-nooit-ook-ooit-begonnen" :+ . No offence.

[ Voor 4% gewijzigd door 430xlkod op 21-04-2012 12:34 ]


  • RobIII
  • Registratie: December 2001
  • Niet online

RobIII

Admin Devschuur®

^ Romeinse Ⅲ ja!

(overleden)
430xlkod schreef op zaterdag 21 april 2012 @ 12:33:
Tevens, als je dit leest dan noem ik jou: "ben-je-zelf-nooit-ook-ooit-begonnen" :+ . No offence.
Jazeker ben ik ooit begonnen, maar mijn "geluk" is dat ik toen nog niet de luxe had van GB's aan geheugen, meerdere cores op meerdere GH'zen en een compleet .Net framework onder m'n reet e.d. Ik moest 't doen met <64k en ~1Mhz, dan liet je 't dus wel uit je hoofd om met een dergelijke oplossing op de proppen te komen :P Dingen als 2^32 deden alleen al -tig alarmbellen afgaan. Those were the days O+ Je werd gedwongen om te zoeken naar efficiëntere manieren en daar profiteer ik elke dag nog van. Neemt niet weg dat 't ook een "last" kan zijn, soms denk je te lang na over iets terwijl je, als je het gewoon pragmatisch had aangepakt en de "luxe" van tegenwoordig gewoon benut had, in 10 minuten coden klaar had kunnen zijn met misschien een ietwat minder efficiënte implementatie die net zo goed met een juist antwoord op de proppen komt binnen de gestelde eisen (in dit geval bijvoorbeeld de tijd die je applicatie in de wedstrijd krijgt). Dat is ook precies de reden waarom Soultaker (terecht) aangeeft dat een lusje waarschijnlijk net zo makkelijk is. En dat neemt ook niet weg dat, inderdaad, iedereen ooit ergens is begonnen. Ik reken je dan verder ook niets aan en dat is dan ook precies de reden waarom ik je verwijs naar Back to Basics; juist een generatie zoals "jij" heeft vaak een "gat" in de kennis zitten omdat jullie vaak helemaal niet gedwongen zijn om op dat niveau over zaken na te denken terwijl dat wel zou moeten en je die basics dus eigenlijk wel zou moeten kennen, ook al zijn ze hedentendage misschien niet altijd helemaal relevant meer ;) No offence :)
Back when I was a boy, we carved our own IC's out of wood.
:+

[ Voor 8% gewijzigd door RobIII op 21-04-2012 13:30 ]

There are only two hard problems in distributed systems: 2. Exactly-once delivery 1. Guaranteed order of messages 2. Exactly-once delivery.

Je eigen tweaker.me redirect

Over mij


  • Snobbieh
  • Registratie: Juli 2009
  • Laatst online: 22-11 13:01
Met Substring moet dit toch ook perfect kunnen... (als je dan toch .NET gebruikt)

I7 2600K - 8GB - M550 256GB - GTX 670


  • EXX
  • Registratie: Juni 2001
  • Laatst online: 24-11 14:35

EXX

EXtended eXchange

RobIII schreef op zaterdag 21 april 2012 @ 12:58:
[...]

Jazeker ben ik ooit begonnen, maar mijn "geluk" is dat ik toen nog niet de luxe had van GB's aan geheugen, meerdere cores op meerdere GH'zen en een compleet .Net framework onder m'n reet e.d. Ik moest 't doen met <64k en ~1Mhz, dan liet je 't dus wel uit je hoofd om met een dergelijke oplossing op de proppen te komen :P Dingen als 2^32 deden alleen al -tig alarmbellen afgaan.
Hear, hear!

Ik heb bij dit soort opdrachten ook soms de neiging om voor de lol eens keihard een oplossing in Z80 Assembly in te sturen >:) ;) Alleen met de I/O heb je dan een beetje een probleem (je weet niet wat voor een OS calls daarvoor aanwezig zijn, of je moet gewoon ervan uitgaan dat je onder CP/M draait) :P.

For it is the doom of men that they forget...           Huidige en vroegere hardware specs         The Z80 is still alive!


  • Soultaker
  • Registratie: September 2000
  • Laatst online: 02:44
EXX schreef op zaterdag 21 april 2012 @ 13:09:
Ik heb bij dit soort opdrachten ook soms de neiging om voor de lol eens keihard een oplossing in Z80 Assembly in te sturen >:)
Is voor deze opdracht nog verre van eenvoudig bij gebrek aan vermenigvuldiging, deling of 32-bit integers op de Z80.

[ Voor 21% gewijzigd door Soultaker op 21-04-2012 14:18 ]


  • ValHallASW
  • Registratie: Februari 2003
  • Niet online
RobIII schreef op vrijdag 20 april 2012 @ 23:07:
Echter, je weet dat er 9 cijfers met lengte 1 zijn (<10) zijn, daarna 90 cijfers met lengte 2 (<100), dan 900 cijfers met lengte 3 (< 1000) etc. Daarmee alleen al kun je toch veel slimmer de lengte berekenen dan domweg een teller van 1 tot "opgave" laten lopen?
Het kost wel wat puzzelen op de off-by-ones, maar na twee enveloppen volschrijven kwam ik hierop:

Python:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
import itertools


def getCijfer(i):
    dec = i - 1
    for blok in itertools.count(1):
        step = (9 * 10**(blok-1)) * blok
        if step > dec:
            break
        dec -= step
    
    ncijfers = blok

    num = dec / ncijfers

    for blok in range(ncijfers):
        num += (9 * 10**(blok-1))
    num += 1
    
    num = str(num)
    return int(num[dec % ncijfers])
    
known = {15: 2, 2022: 0, 1410169200: 1, 2147483646: 2}
for i, o in known.iteritems():
    print i,o,getCijfer(i)


Nee, geen commentaar ;-)

  • RobIII
  • Registratie: December 2001
  • Niet online

RobIII

Admin Devschuur®

^ Romeinse Ⅲ ja!

(overleden)
Geen idee of 't klopt, maar zo op 't oog lijkt 't wel op wat ik in gedachte had :)
Als je met meer bekende data wil testen of je implementatie klopt dan kun je hier kijken (invoer / uitkomst).

There are only two hard problems in distributed systems: 2. Exactly-once delivery 1. Guaranteed order of messages 2. Exactly-once delivery.

Je eigen tweaker.me redirect

Over mij


  • Tharulerz
  • Registratie: April 2009
  • Laatst online: 10-04 05:16
Onze oplossing van het probleem (hebben ook meegedaan):
Java:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int cases = Integer.parseInt(scanner.nextLine());
        for (int i = 0; i < cases; i++) {
            String next = scanner.nextLine();
            int getal = Integer.parseInt(next.trim());
            int uitkomst = 0;

            for (int j = 0; j < 10; j++) {
                double temp = (j + 1) * (9 * Math.pow(10, j));
                if (getal > temp) {
                    getal -= temp;
                } else {
                    int mod = getal % (j + 1);
                    double x = Math.ceil(getal / (j + 1)) - 1;

                    double pow = Math.pow(10, j);
                    double v = pow + x;

                    int v1 = (int) v;
                    String ans = "" + v1;
                    if(mod == 0){
                        ans = ans.substring(ans.length() - 1);
                    } else {
                        char a = ans.charAt(mod-1);
                        ans = a + "";
                    }
                    System.out.println(ans);
                    break;
                }

            }

        }
    }


Oplossing was volledig juist, enkel faalde het algoritme op 1 input omdat we op regel 16 een cast naar (double) vergeten waren en 1 van de 50 input getalleen een verkeerde afronding gaf (in java).

  • Soultaker
  • Registratie: September 2000
  • Laatst online: 02:44
Interessante definitie van "volledig juist" hou jij er op na. :P

  • Tharulerz
  • Registratie: April 2009
  • Laatst online: 10-04 05:16
Soultaker schreef op zaterdag 21 april 2012 @ 19:50:
Interessante definitie van "volledig juist" hou jij er op na. :P
Buh, details! :)

  • 430xlkod
  • Registratie: Januari 2007
  • Laatst online: 05-07 23:11
RobIII schreef op zaterdag 21 april 2012 @ 12:58:
[...]

Jazeker ben ik ooit begonnen, maar mijn "geluk" is dat ik toen nog niet de luxe had van GB's aan geheugen, meerdere cores op meerdere GH'zen en een compleet .Net framework onder m'n reet e.d. Ik moest 't doen met <64k en ~1Mhz, dan liet je 't dus wel uit je hoofd om met een dergelijke oplossing op de proppen te komen :P Dingen als 2^32 deden alleen al -tig alarmbellen afgaan. Those were the days O+ Je werd gedwongen om te zoeken naar efficiëntere manieren en daar profiteer ik elke dag nog van. Neemt niet weg dat 't ook een "last" kan zijn, soms denk je te lang na over iets terwijl je, als je het gewoon pragmatisch had aangepakt en de "luxe" van tegenwoordig gewoon benut had, in 10 minuten coden klaar had kunnen zijn met misschien een ietwat minder efficiënte implementatie die net zo goed met een juist antwoord op de proppen komt binnen de gestelde eisen (in dit geval bijvoorbeeld de tijd die je applicatie in de wedstrijd krijgt). Dat is ook precies de reden waarom Soultaker (terecht) aangeeft dat een lusje waarschijnlijk net zo makkelijk is. En dat neemt ook niet weg dat, inderdaad, iedereen ooit ergens is begonnen. Ik reken je dan verder ook niets aan en dat is dan ook precies de reden waarom ik je verwijs naar Back to Basics; juist een generatie zoals "jij" heeft vaak een "gat" in de kennis zitten omdat jullie vaak helemaal niet gedwongen zijn om op dat niveau over zaken na te denken terwijl dat wel zou moeten en je die basics dus eigenlijk wel zou moeten kennen, ook al zijn ze hedentendage misschien niet altijd helemaal relevant meer ;) No offence :)
Ik geef je volledig gelijk en zou het ook willen kunnen om op die (oude) wijze te denken. Maar we krijgen het in eerste instantie het al niet aangeleerd op school. Dit vind ik zelf zoiezo al een groot gat, omdat we op school met oefeningen, opdrachten en noem maar op gewoon variabelen declareren zonder erbij stil te staan wat dit doet op performance, geheugengebruik en noem maar op. Mocht ik de kans zien om dit aan te kaarten bij hun zodanig dat ze hier wat dieper op zouden ingaan dan deed ik dat ook. Maar dankzij de luxe die wij hebben, de generatie die het nu leert dus, denken wij niet op deze wijze. Ik wist ook bij voorbaat al toen ik het probleem las dat het uitwerken ervan geen probleem ging zijn, maar wel een algoritme vinden die efficient was. Omdat we daar dus niets van wisten kregen we het ook niet opgelost.
Maargoed, ik ga nog verder proberen :) .
Snobbieh schreef op zaterdag 21 april 2012 @ 13:06:
Met Substring moet dit toch ook perfect kunnen... (als je dan toch .NET gebruikt)
Die hadden we ook gebruikt :) .
Tharulerz schreef op zaterdag 21 april 2012 @ 19:02:
Onze oplossing van het probleem (hebben ook meegedaan):
Java:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int cases = Integer.parseInt(scanner.nextLine());
        for (int i = 0; i < cases; i++) {
            String next = scanner.nextLine();
            int getal = Integer.parseInt(next.trim());
            int uitkomst = 0;

            for (int j = 0; j < 10; j++) {
                double temp = (j + 1) * (9 * Math.pow(10, j));
                if (getal > temp) {
                    getal -= temp;
                } else {
                    int mod = getal % (j + 1);
                    double x = Math.ceil(getal / (j + 1)) - 1;

                    double pow = Math.pow(10, j);
                    double v = pow + x;

                    int v1 = (int) v;
                    String ans = "" + v1;
                    if(mod == 0){
                        ans = ans.substring(ans.length() - 1);
                    } else {
                        char a = ans.charAt(mod-1);
                        ans = a + "";
                    }
                    System.out.println(ans);
                    break;
                }

            }

        }
    }


Oplossing was volledig juist, enkel faalde het algoritme op 1 input omdat we op regel 16 een cast naar (double) vergeten waren en 1 van de 50 input getalleen een verkeerde afronding gaf (in java).
Oké nice! Welke plaats hadden jullie gehaald (gewoon ter zijde :) ).

  • ValHallASW
  • Registratie: Februari 2003
  • Niet online
430xlkod schreef op zaterdag 21 april 2012 @ 23:11:
Ik geef je volledig gelijk en zou het ook willen kunnen om op die (oude) wijze te denken. Maar we krijgen het in eerste instantie het al niet aangeleerd op school. Dit vind ik zelf zoiezo al een groot gat, omdat we op school met oefeningen, opdrachten en noem maar op gewoon variabelen declareren zonder erbij stil te staan wat dit doet op performance, geheugengebruik en noem maar op.
Het is niet op een 'oude' wijze denken en het is al helemaal niet een denkwijze die je op school kunt leren. Het gáát namelijk helemaal niet om 'variabelen declareren zonder na te denken over performance'. Het gaat om een stap verder denken dan wat er in de opgave staat - namelijk het analyseren en abstraheren van een probleem.

In feite is het belangrijkste bij dit soort problemen vooral géén computer te pakken maar een bierviltje (of een envelop, of ....) en daar gewoon te gaan puzzelen. Zogauw je de structuur dan uitgeplozen hebt dan is het implementeren van een oplossing vijf minuten werk.

Het mooie van informatica (en dat is wel de luxe die je nu meer hebt dan vroeger) is dat je het niet helemaal hoeft uit te werken - het is in de basis een wiskundig probleem, maar je kunt er voor kiezen om een deel niet functioneel maar juist imperatief uit te werken (zoals het herhaalde aftrekken/optellen in mijn implementatie - dat is ongetwijfeld met wat meer gepuzzel wiskundig netter uit te werken).

  • RobIII
  • Registratie: December 2001
  • Niet online

RobIII

Admin Devschuur®

^ Romeinse Ⅲ ja!

(overleden)
ValHallASW schreef op zondag 22 april 2012 @ 00:31:
Het gaat om een stap verder denken dan wat er in de opgave staat - namelijk het analyseren en abstraheren van een probleem.
Juistem. En dat is, no offence, bij heel veel mensen iets wat je niet (of heel moeilijk) kunt léren. Dat moet je gewoon liggen / aanleg voor hebben / talent / noem-'t-iets. Zo kan de één heel goed een bal in de juiste richting schoppen of de ander en heerlijke maaltijd bereiden of... you-name-it. En sommige mensen zit 't programmeren gewoon wel of niet in 't bloed (waarmee ik niet op iemand specifiek in dit topic doel overigens; het gaat me om de algemeenheid).

There are only two hard problems in distributed systems: 2. Exactly-once delivery 1. Guaranteed order of messages 2. Exactly-once delivery.

Je eigen tweaker.me redirect

Over mij


  • 430xlkod
  • Registratie: Januari 2007
  • Laatst online: 05-07 23:11
Oké, I get the point. En het is inderdaad iets waar je aanleg voor moet hebben. Enkel heb ik al gemerkt dat ik er niet helemaal aanleg voor heb (of toch niet in die mate dat het nuttig is voor een case zoals een wedstrijd).
Anyways, ik ga wel verder brainstormen op dit probleem en kijken dat ik het zelf oplos. Oplossing van Tharulerz houd ik achterwege als 'backup' :) .

  • dingstje
  • Registratie: Augustus 2002
  • Laatst online: 02-01-2024
RobIII schreef op zondag 22 april 2012 @ 01:57:
[...]

Juistem. En dat is, no offence, bij heel veel mensen iets wat je niet (of heel moeilijk) kunt léren. Dat moet je gewoon liggen / aanleg voor hebben / talent / noem-'t-iets. Zo kan de één heel goed een bal in de juiste richting schoppen of de ander en heerlijke maaltijd bereiden of... you-name-it. En sommige mensen zit 't programmeren gewoon wel of niet in 't bloed (waarmee ik niet op iemand specifiek in dit topic doel overigens; het gaat me om de algemeenheid).
Heeft er uiteraard wel mee te maken, maar toch ook voor een groot stuk met oefening/ervaring. Er zullen wellicht wel genieën zijn die de mogelijke oplossingen zo kunnen bedenken en meteen ook de efficiëntie ervan kunnen bepalen alsof het niks is, maar voor de meeste stervelingen is het ploeteren, aanmodderen en proberen. Na een tijdje heb je wel een aantal reflexen opgebouwd om bij een bepaald type probleem een aantal dingen te gaan nagaan/uitproberen. En dat is voor iemand die de bal in de juiste richting kan schoppen of iemand die een heerlijke maaltijd kan berieden niet anders: situatie inschatten, herkennen, begrijpen, juist op reageren, even tijd nemen voor feedback en die ervaring meenemen voor de volgende keer :)

If you can't beat them, try harder


  • EXX
  • Registratie: Juni 2001
  • Laatst online: 24-11 14:35

EXX

EXtended eXchange

Soultaker schreef op zaterdag 21 april 2012 @ 14:18:
[...]

Is voor deze opdracht nog verre van eenvoudig bij gebrek aan vermenigvuldiging, deling of 32-bit integers op de Z80.
Dat is nou net de uitdaging. ;) Gewoon alles als BCD opslaan en verrekenen, is mijn eerste ingeving. Of een paar routines schrijven waarmee je 32 bits berekeningen kunt doen, dat is ook niet zo ingewikkeld.

For it is the doom of men that they forget...           Huidige en vroegere hardware specs         The Z80 is still alive!


  • Soultaker
  • Registratie: September 2000
  • Laatst online: 02:44
430xlkod schreef op zondag 22 april 2012 @ 15:37:
Enkel heb ik al gemerkt dat ik er niet helemaal aanleg voor heb (of toch niet in die mate dat het nuttig is voor een case zoals een wedstrijd).
Het is een kwestie van interesse, aanleg en oefening. Het feit dat je er na de wedstrijd nog een topic over opent doet me vermoeden dat je het wel interessant vindt. Als je gemotiveerd bent, kun je jezelf veel aanleren. RobIII heeft misschien meer programmeerervaring dan jij, maar hij is in een ver verleden ook als n00b begonnen op een Commodore64 of iets vergelijkbaars.

Ik zeg dus liever: blijf gewoon oefenen zolang je het zelf leuk vindt.

  • Soultaker
  • Registratie: September 2000
  • Laatst online: 02:44
BUMP!

Ik probeerde die andere VPW problemen op te lossen als voorbereiding voor de Google Code Jam en ik kom er bij één probleem niet uit, vandaar dat ik dit topic hergebruik om een second opinion te vragen.

Het gaat om het probleem “gevangen” (probleemstelling in PDF hier); nota bene één van de makkelijksten. Ik vermoed zelfs dat de testdata gewoon verkeerd is, maar aangezien volgens de uitslagen één team een correcte oplossing had ingestuurd, is het mogelijk dat ik iets over het hoofd zie.

De eerste testcase die foutgaat is:
7 3 4 2 1 5 6 7

(De eerste 7 geeft aan dat er zeven getallen volgen; die laatste zeven getallen zijn de cijfers op de kaarten.) Volgens mij worden kaarten 5, 3, 2 en 1 gevangen (in die volgorde) en daarna zijn we klaar. De officiële uitvoer is echter 5, 3, 2, 1, 6, 4, 7 (en dan is alles gevangen); oftewel ná de 1 kan de 6 gevangen worden. Ik zie absoluut niet hoe dat mogelijk is; ook niet als ik het met de hand uitteken. Heeft iemand een idee hoe dit te verklaren is?

  • ValHallASW
  • Registratie: Februari 2003
  • Niet online
Soultaker schreef op maandag 30 april 2012 @ 15:24:
Heeft iemand een idee hoe dit te verklaren is?
Als je bij het tellen de waarde n hebt bereikt, is de volgende waarde
voor de teller terug 1.
De volgorde is dus: 5,3,2,1,6 (13), 4 en dan 7 (want er is nog maar één kaart over).

[ Voor 16% gewijzigd door ValHallASW op 30-04-2012 15:36 ]


  • Soultaker
  • Registratie: September 2000
  • Laatst online: 02:44
Dat was het inderdaad; ik stopte nadat ik 7 had gehad. Slecht gelezen; stom van me. 8)7
Bedankt, ValHallASW!
Pagina: 1