[GPC] opgave 3

[wasigh]

Opgave 3: Cijfers en Letters (maar dan alleen Cijfers)

Deze opgave loopt van donderdag 13-12-2001 14:00 tot woensdag 19-12-2001 24:00.

Oplossing via email naar: [e-mail]

LET OP E-MAIL ADRES IS GEWIJZIGD


Vermeld in de titel je nickname en welke taal je gebruikt hebt.

De maximale runtime is 10 minuten tot 6 getallen en 20 minuten voor 7 getallen. Ieder programma dat langer draait om de oplossing te vinden krijgt een 'runtime exceeded exception'.

Denk eraan dat je je inzending zipt, dus source & binary in 1 file aanleveren!!
<hr>
Alle programma's lezen hun input van de stdin en schrijven naar de stdout. Voor programma's met een Gui mag dit ook een textarea zijn. Maar op eigen risico! Als de testset niet in de textarea past is dat jullie probleem.
Als output naar stderr in de console verschijnt wordt het gezien als output naar de stdout.
Je kan erop vertrouwen dat de invoer correct is en deze behoeft dan ook geen foutafvanging.

Veel plezier en succes!
<hr>
Opgave 3: Cijfers en Letters (maar dan alleen Cijfers)

Deze opgave gaat over de TV quiz Cijfers en Letters. Bij deze quiz krijg je
een aantal cijfers en een uitkomst. De bedoeling is dat de kandidaten een
som proberen te vinden, waarbij deze uitkomst gevonden wordt.

Nu doet er een domme tweaker mee die met z'n laptopje daar mag zitten. Deze
gaat dus niet zelf alles verzinnen maar laat het de computer doen. Aan
jullie de taak om een programma voor deze domme tweaker te schrijven (Ik
noem geen namen ... )

Ter illustratie eerst een voorbeeldopgave:

Je krijgt de getallen 1 20 72 5 9 en als antwoord 23.

Een mogelijke som is dan: 1 * 72 / 9 + 20 - 5

Hiervoor geld Vermenigvuldigen/delen gaat voor optellen/aftrekken. Verder
zijn haakjes toegestaan. Alle getallen moeten gebruikt worden.

Het programma krijgt als invoer op de standaard invoer of een text-box de
getallen van de opgave achter elkaar, gescheiden door 1 spatie. Op de tweede
regel staat het antwoord van de opgave.

Als uitvoer staat de som welke het antwoord vormt. Let op dat deze goed moet
zijn en als er dus haakjes nodig zijn moeten die er bij staan.

TestInvoer:
1 2 3 4 5
17

Testuitvoer:
1*4/2+5*3

Meerdere antwoorden zijn vaak mogelijk, maar er hoeft maar 1 gevonden te worden.

Wat overige regels en opmerkingen:

• Alleen gehele getallen worden gebruikt bij de invoer en antwoord. Echter tussendoor zijn wel niet-gehele getallen toegestaan. Bijvoorbeeld (3/4)*4 = 3.
• Het programma moet werken tot maximaal 7 getallen bij de invoer. Bovenstaand voorbeeld werkt met 5 getallen.
• Mocht het programma geen antwoord vinden dan komt de uitvoer "Geen antwoord".
• De maximale runtime is 10 minuten tot 6 getallen en 20 minuten voor 7 getallen.

1: Voor het eerste getal mag geen - staan
2: De maximale uitkomst is 9999999
3: Er worden alleen uitkomsten groter als 0 verwacht
4: Alleen de * / - + en de haakjes mogen gebruikt worden.

[Tom]

en ^ up

[jelmervos]

Succes jongens!

[kvdveer]

Yes!!! een lekker lastige opdracht...

Well done guys!

[wasigh]

Op donderdag 13 december 2001 14:08 schreef kvdveer het volgende:
Yes!!! een lekker lastige opdracht...

Well done guys!

Bedank theSwitch maar

[D2k]

de tussenstand komt nog
daar wordt nog aan gewerkt

[Theswitch]

Veel succes allemaal. Misschien ga ik zelf ook nog wel een uitwerking maken (in perl natuurlijk

[Nielsz]

Volgens mij istie niet zo moeilijk

[D2k]

Op donderdag 13 december 2001 14:18 schreef Nielsz het volgende:
Volgens mij istie niet zo moeilijk

ik zie nog nix in de mail van je anders

hij lijkt niet zo moeilijk
maar is het wel

[RickN]

Mja, dit is een ZEER bekende opgave die in meerdere lijsten met opgaven voor programmeerwedstijden staat. Ik zal vanavond eens een linkje zoeken. Leuke opgave, maar we lopen wel een redelijk groot risco dat iemand al eens met precies deze opgave in aanraking is gekomen.

[Verwijderd]

Even een vraagje .. welke wiskundige bewerkingen moeten/mogen allemaal gebruikt worden ? Moeten we alleen aan de gang met + - / * of ook met sinus tangens wortels machten en dergelijke ?

[jelmervos]

Dit lijkt wel wat op die flippo's met die 4 getallen en dan moest je 21 maken.

[Theswitch]

Op donderdag 13 december 2001 14:22 schreef RickN het volgende:
Mja, dit is een ZEER bekende opgave die in meerdere lijsten met opgaven voor programmeerwedstijden staat. Ik zal vanavond eens een linkje zoeken. Leuke opgave, maar we lopen wel een redelijk groot risco dat iemand al eens met precies deze opgave in aanraking is gekomen.

Hmm ik heb 'm nog nooit eerder gezien moet ik eerlijk zeggen. Ach, ik zeg ook niet dat ik orgineel ben natuurlijk. Maar toch, blijft interresant genoeg lijkt me.

[Theswitch]

Op donderdag 13 december 2001 14:22 schreef eXoR het volgende:
Even een vraagje .. welke wiskundige bewerkingen moeten/mogen allemaal gebruikt worden ? Moeten we alleen aan de gang met + - / * of ook met sinus tangens wortels machten en dergelijke ?

Goed lezen. Alleen +-/*)(

[darthdrinker]

ALPHA/BETA algoritme jee zijn we net mee bezig op school.
Misschien ga ik er ook nog wel mee bezig.
Leuk btw dat jullie dit soort dingen doen, kom hier niet zo vaak maar nu ik dit zie zal ik hier es wat vaker langskomen.
Eindelijk mensen die programmeren 'leuk' vinden en het dan niet over PHP hebben.

[Verwijderd]

Ik zal wel blind zijn maar waar lees jij dat dan ?

Hiervoor geld Vermenigvuldigen/delen gaat voor optellen/aftrekken. Verder
zijn haakjes toegestaan. Alle getallen moeten gebruikt worden.

Hier toch niet ? Zoals ik 't lees wordt er alleen iets gezegd over volgorden van wiskundige bewerkingen, niet over welke wiskundige bewerkingen je mag gebruiken.

[raptorix]

Deze lijkt me ook wel leuk om mee te doen

Vraagje, wat is het maximale getal wat de uitkomst moet worden? In het orginele spel was dit meen ik 999

[Nielsz]

Op donderdag 13 december 2001 14:20 schreef D2k het volgende:

[..]

ik zie nog nix in de mail van je anders

hij lijkt niet zo moeilijk
maar is het wel

Alsof ik niets anders aan mijn hoofd heb

[RickN]

Mag er ook een - voor het eerste getal staan?

en

Kan er om een negatieve uitkomst gevraagd worden?

[wasigh]

1: Voor het eerste getal mag geen - staan
2: De maximale uitkomst is 9999999
3: Er worden alleen uitkomsten groter als 0 verwacht
4: Alleen de * / - + en de haakjes mogen gebruikt worden.

[flat]

aha deze is leuk jongens!

[D2k]

LET OP

extra "voorwaarden/beperkingen"

• 1: Voor het eerste getal mag geen - staan 2: De maximale uitkomst is 9999999 3: Er worden alleen uitkomsten groter als 0 verwacht 4: Alleen de * / - + en de haakjes mogen gebruikt worden.

<edit>
en als vanouds weer 2x

[wasigh]

Op donderdag 13 december 2001 14:38 schreef D2k het volgende:


<edit>
en als vanouds weer 2x

Back to the old times

[Theswitch]

Op donderdag 13 december 2001 14:39 schreef wasigh het volgende:

[..]

Back to the old times

Hehe, sorry dat ik dit niet voorzin had.. Maar jullie ook niet *smile*. Maar we zijn er snel bij dit keer.

[RickN]

Ik heb even gezocht, en heb geen opgave gevonden die exact hetzelfde is als degene die jullie nu hebben opgegeven. Ik heb er wel twee gevonden die er op lijken, één die makkelijker is dan die van jullie en één die denk ik moeilijker is.

Makkelijkere
Moeilijkere

Deze opgaven komen van een site die een soort van eeuwigdurende programmeer wedstrijd houdt en ze houden ook statistieken bij van de inzendingen die ze op elke opgave krijgen. Om een beetje een idee te krijgen van hoe moeilijk deze opgave waarschijnlijk is moet je hier maar eens naar kijken: (Let wel, ik denk dat de mensen die door dit soort sites worden aangetrokken iets meer programmeer ervaring hebben dan de meeste mensen die aan de GPC meedoen!!!)

Makkelijke stats
Moeilijke stats

Deze site heeft een automatische jury, cool hè (Misschien ook iets voor onze jury???)

[wasigh]

Op donderdag 13 december 2001 15:02 schreef RickN het volgende:
Ik heb even gezocht, en heb geen opgave gevonden die exact hetzelfde is als degene die jullie nu hebben opgegeven. Ik heb er wel twee gevonden die er op lijken, één die makkelijker is dan die van jullie en één die denk ik moeilijker is.

Makkelijkere
Moeilijkere

Deze opgaven komen van een site die een soort van eeuwigdurende programmeer wedstrijd houdt en ze houden ook statistieken bij van de inzendingen die ze op elke opgave krijgen.
Om een beetje een idee te krijgen van hoe moeilijk deze opgave waarschijnlijk is moet je hier maar eens naar kijken: (Let wel, ik denk dat de mensen die door dit soort sites worden aangetrokken iets meer programmeer ervaring hebben dan de meeste mensen die aan de GPC meedoen!!!)

Makkelijke stats
Moeilijke stats

Deze site heeft een automatische jury, cool hè (Misschien ook iets voor onze jury???)

De online judge van ACM ken ik wel
alleen accepteerden ze een jaar geleden geen java

(GPC is trouwens gebaseerd op de ACM wedstrijdenn waar ik met mijn "team wasigh" reeds 2 keer aan mee heb gedaan )

[RickN]

Op donderdag 13 december 2001 15:05 schreef wasigh het volgende:

[..]

De online judge van ACM ken ik wel
alleen accepteerden ze een jaar geleden geen java

(GPC is trouwens gebaseerd op de ACM wedstrijdenn waar ik met mijn "team wasigh" reeds 2 keer aan mee heb gedaan )

Dan weet je dus waarschijnlijk ook wel wat het betekent dat bij een opgave slechts 32 van de 517 inzendingen geaccepteerd zijn

[D2k]

Op donderdag 13 december 2001 15:15 schreef RickN het volgende:

[..]

Dan weet je dus waarschijnlijk ook wel wat het betekent dat bij een opgave slechts 32 van de 517 inzendingen geaccepteerd zijn

dat de opgave lastiger is dan verwacht

[RickN]

Op donderdag 13 december 2001 15:15 schreef ik het volgende:

[..]

Dan weet je dus waarschijnlijk ook wel wat het betekent dat bij een opgave slechts 32 van de 517 inzendingen geaccepteerd zijn

Volgens mij betekent het:

"Abandon all hope, ye who" tries to solve this problem.....

[wasigh]

Op donderdag 13 december 2001 15:37 schreef RickN het volgende:

[..]

Volgens mij betekent het:

"Abandon all hope, ye who" tries to solve this problem.....

tja, "deze opgave is echt simpel!" - willen we niet meer horen (en dan hebben jullie opgave 4 nog niet gezien )

[RickN]

Dan maar weer even een inhoudelijke vraag (en doe me please please please een lol door er JA op te antwoorden)

Mogen er in je resultaat expressie overbodige haakjes staan???

B.V.

(3+5)*(7-4-1)=16

wordt dan

((3)+(5))*(((7-4)-1))=16 ook goed gerekend???

[Theswitch]

Op donderdag 13 december 2001 15:45 schreef RickN het volgende:
Dan maar weer even een inhoudelijke vraag (en doe me please please please een lol door er JA op te antwoorden)

Mogen er in je resultaat expressie overbodige haakjes staan???

B.V.

(3+5)*(7-4-1)=16

wordt dan

((3)+(5))*(((7-4)-1))=16 ook goed gerekend???

Ask de jury!

[raptorix]

ok probeer dees dan maar eens op te lossen met jullie tooltjes

1 8 9 9
1

[Theswitch]

Op donderdag 13 december 2001 16:04 schreef raptorix het volgende:
ok probeer dees dan maar eens op te lossen met jullie tooltjes

1 8 9 9
1

[possible spoiler]

[raptorix]

Op donderdag 13 december 2001 16:07 schreef Theswitch het volgende:

[..]

nice mijn voorbeeld was niet helemaal goed

...............

[Verwijderd]

Op donderdag 13 december 2001 16:01 schreef Theswitch het volgende:

[..]

Haakjes elimineren uit een antwoord is toch niet zo moeilijk?

Deze opmerking in combinatie met je volgende posting lijkt mij een flinke spoiler. Zit namelijk op hetzelfde spoor als die snelle gast met zijn veranderde naam (sorry voor deze kromme benaming, maar zie je naam ff niet nu...) en dan zie ik een gedeelte van de oplossing als ik de postings combineer...

[Theswitch]

Heb de possible spoilers aangepast. Zal m'n mond wel dichthouden de rest van de dag Maar toch, 't lijft nog steeds geen triviaal programma om te schrijven hoor.

[Verwijderd]

Op donderdag 13 december 2001 16:13 schreef Theswitch het volgende:
Heb de possible spoilers aangepast. Zal m'n mond wel dichthouden de rest van de dag Maar toch, 't blijft nog steeds geen triviaal programma om te schrijven hoor.

Nee, dat hoor je mij ook niet zeggen hoor dacht ff dat ik de oplossing had, maar het laatste voorbeeld nekt me ff...
Maar ik zal eruit komen!

[Orphix]

Zo dit is toch een stukje pittiger!
Tenminste, ik weet zo snel ff geen oplossing
Dat de beste mogen winnen

[Verwijderd]

Ach, de oplossing is heel gemakkelijk (*knip*). Alleen moet ie wel binnen de gestelde tijd de oplossing geven. Dat is een stuk moeilijker

[RickN]

Op donderdag 13 december 2001 18:15 schreef Doekman het volgende:
Ach, de oplossing is heel gemakkelijk *spoiler*. Alleen moet ie wel binnen de gestelde tijd de oplossing geven. Dat is een stuk moeilijker

Vind je dit zelf nou ook geen spoiler

[D2k]

OOK DEZE KEER WORDEN MENSEN DIE DENKEN MET SPOILERS TE KUNNEN KOMEN VERZOCHT EERST CONTACT OP TE NEMEN MET DE JURY.
GEPOSTE SPOILERS ZULLEN GETRASHT/GE-EDIT WORDEN

[Twilight Burn]

Zo, heb um bijna zover dat ik um kan gaan testen
Ik durf trouwes te wedden dat niemand zo'n ranzige code heeft als ik

[Verwijderd]

Heb gister es ff over mijn oplossing nagedacht maar dat zou meer dan 191.000.000 iteraties inhouden

[D2k]

Op vrijdag 14 december 2001 08:59 schreef eXoR het volgende:
Heb gister es ff over mijn oplossing nagedacht maar dat zou meer dan 191.000.000 iteraties inhouden

dat lijkt me idd wat veel tijd in beslag nemen

[RickN]

Lijkt het nou maar of is dit topic en eigenlijk de hele GPC een beetje aan het afsterven???

[dusty]

Op vrijdag 14 december 2001 08:59 schreef eXoR het volgende:
Heb gister es ff over mijn oplossing nagedacht maar dat zou meer dan 191.000.000 iteraties inhouden

Slimmere logartime gebruiken

[Verwijderd]

Op vrijdag 14 december 2001 11:10 schreef RickN het volgende:
Lijkt het nou maar of is dit topic en eigenlijk de hele GPC een beetje aan het afsterven???

Nee hoor

[RickN]

Op vrijdag 14 december 2001 11:16 schreef Joshua30 het volgende:

[..]

Nee hoor

Idd, jouw opmerking brengt echt weer leven in de brouwerij

[dusty]

Op vrijdag 14 december 2001 11:17 schreef RickN het volgende:
Idd, jouw opmerking brengt echt weer leven in de brouwerij

Iedereen zit waarschijnlijk hard te denken hoe ze hun programma het snelst de oplossing kunnen laten berekenen.

[wasigh]

er zijn idd minder reacties als eerst...
tijd voor de grote klapper dUSTY

[D2k]

Op vrijdag 14 december 2001 11:19 schreef dusty het volgende:

[..]

Iedereen zit waarschijnlijk hard te denken hoe ze hun programma het snelst de oplossing kunnen laten berekenen.

ik ga misschien zelf pogen een php oplossing te maken
als ik ergens dit weekend de tijd voor vindt iig

[D2k]

Op vrijdag 14 december 2001 11:26 schreef wasigh het volgende:
er zijn idd minder reacties als eerst...
tijd voor de grote klapper dUSTY

jah ik hoop dat dusty eens wat instuurt en alles en iedereen kwa snelheid en schoonheid verpletterd

[Munters]

Ik ben zo oud dat ik het programma nog wel ken.
Maar daar hoefde je geen gebruik te maken van alle getallen.

Dus met de reeks
1 3 5 7
8

mocht het antwoord best
1 + 7
zijn.

Ik neem aan dat er ook geldt dat ieder getal precies 1 x voor moet komen?

[D2k]

Op vrijdag 14 december 2001 11:37 schreef Munters het volgende:
Ik ben zo oud dat ik het programma nog wel ken.
Maar daar hoefde je geen gebruik te maken van alle getallen.

Dus met de reeks
1 3 5 7
8

mocht het antwoord best
1 + 7
zijn.

Ik neem aan dat er ook geldt dat ieder getal precies 1 x voor moet komen?

genau, das stimmt

[Verwijderd]

En van het rijtje:
1 2 3 4 5
357

mag je zeker geen
12+345

van maken (sorry jury, maar ik vind het zo'n heldere opgave dat ik even moet stangen).

[D2k]

Op vrijdag 14 december 2001 13:00 schreef Doekman het volgende:
En van het rijtje:
1 2 3 4 5
357

mag je zeker geen
12+345

van maken (sorry jury, maar ik vind het zo'n heldere opgave dat ik even moet stangen).

tuurlijk mag jij dat

en dan ga je bij ome D2k in het rijtje met foute inzenders

[D2k]

<teaser mode=high>
ik ben bezig met een bijzonder leuk iets als mogelijke afsluitende opgave
</teaser mode>

[roelio]

Op vrijdag 14 december 2001 14:01 schreef D2k het volgende:
<teaser mode=high>
ik ben bezig met een bijzonder leuk iets als mogelijke afsluitende opgave
</teaser mode>

ooh baby!

[dusty]

Op vrijdag 14 december 2001 14:01 schreef D2k het volgende:
<teaser mode=high>
ik ben bezig met een bijzonder leuk iets als mogelijke afsluitende opgave
</teaser mode>

Als ut goed is heb ik de mijne vandaag of morgen af.. ( De opdracht die ik had bedacht )

[D2k]

Op vrijdag 14 december 2001 16:26 schreef dusty het volgende:

[..]

Als ut goed is heb ik de mijne vandaag of morgen af.. ( De opdracht die ik had bedacht )

nice
ik heb nog een andere in gedachten

[Twilight Burn]

Hmm, heb um nu af, maar hij is veel te langzaam 6 nummers gaat goed, maar voor 7 heb ik 3 uur nodig, toch ff kijken of ik um wat in kan korten

[Dash2in1]

Op vrijdag 14 december 2001 21:22 schreef Twilight Burn het volgende:
Hmm, heb um nu af, maar hij is veel te langzaam 6 nummers gaat goed, maar voor 7 heb ik 3 uur nodig, toch ff kijken of ik um wat in kan korten

Misschien een troost, maar bij de vorige opgave deed mijn inzending er meerdere dagen over om die van 250 te berekenen (wel goedgekeurd desondanks )

[D2k]

Op vrijdag 14 december 2001 22:43 schreef Dash2in1 het volgende:

[..]

Misschien een troost, maar bij de vorige opgave deed mijn inzending er meerdere dagen over om die van 250 te berekenen (wel goedgekeurd desondanks )

*noteert*
herberekenen van Dash2in1

*noteert ook*
grotere testsets

[Dash2in1]

Op vrijdag 14 december 2001 22:49 schreef D2k het volgende:

[..]

*noteert*
herberekenen van Dash2in1

*noteert ook*
grotere testsets

Hehehe, was misschien wel handig geweest ja
Ach, vergat min of meer ff toen ik bezig was met programmeren om bepaalde zaken niet meteen af te kappen enzo. En was te lui om zelf een grote testset te nemen

[Dash2in1]

Twee vragen:
1) Mag je zoveel haakjes nesten als je wilt?
2) Bij bv de volgende input:

code:

2 5 -6 8
12

Mag dan als uitvoer het volgende komen:
2 * 5 + -6 + 8

??

[wasigh]

Op vrijdag 14 december 2001 23:06 schreef Dash2in1 het volgende:
Twee vragen:
1) Mag je zoveel haakjes nesten als je wilt?
2) Bij bv de volgende input:

code:

2 5 -6 8
12

Mag dan als uitvoer het volgende komen:
2 * 5 + -6 + 8

??

Alleen haakjes die echt nodig plaatsen

het tweede zal theSwitch moeten antwoorden

[Dash2in1]

Op vrijdag 14 december 2001 23:09 schreef wasigh het volgende:

[..]

Alleen haakjes die echt nodig plaatsen

het tweede zal theSwitch moeten antwoorden

Hmm, dus bijvoorbeeld
1 2 3
6
(1 + 2) * 3
Mag niet, omdat 1+2+3 geen haakjes nodig heeft?

[wasigh]

Op vrijdag 14 december 2001 23:19 schreef Dash2in1 het volgende:

[..]

Hmm, dus bijvoorbeeld
1 2 3
6
(1 + 2) * 3
Mag niet, omdat 1+2+3 geen haakjes nodig heeft?

jawel
(((((((((((((((1+2))))))))))))))) *3 mag niet

[Theswitch]

Op vrijdag 14 december 2001 23:06 schreef Dash2in1 het volgende:
Twee vragen:
1) Mag je zoveel haakjes nesten als je wilt?
2) Bij bv de volgende input:

code:

2 5 -6 8
12

Mag dan als uitvoer het volgende komen:
2 * 5 + -6 + 8

??

Ik heb bij cijfers en letters nog nooit negative getallen gezien, dus hier ook niks negatief. De invoer klopt dus niet

[Verwijderd]

Hmm, dit is een leuke opgave. Niet bepaald triviaal Helaas maar tot woensdag, en dit weekend heb ik echt geen tijd. Het zou dus begin volgende week op een avondje moeten gebeuren. I wonder if I can do magic things...

[RickN]

Op vrijdag 14 december 2001 23:22 schreef wasigh het volgende:

[..]

jawel
(((((((((((((((1+2))))))))))))))) *3 mag niet

MMM, ik heb deze vraag al vrij snel nadat de opgave was gepost gestelt en ik heb daar toen nooit een antwoord op gekregen. Ik ben er toen vanuit gegaan dat haakjes gebruikt mogen worden waar ze de zaak verduidelijken (dus niet alleen waar ze absoluut noodzakelijk zijn.

D.w.z. 1*2+3*4=14 heeft in principe geen haakjes nodig, maar ik ben ervan uit gegaan dat (1*2)+(3*4)=14 ook goed wordt gerekend.....

[Dash2in1]

Op vrijdag 14 december 2001 23:28 schreef Theswitch het volgende:

[..]

Ik heb bij cijfers en letters nog nooit negative getallen gezien, dus hier ook niks negatief. De invoer klopt dus niet

Ok, helder. Vraag me dan echter af waarom er staat dat alleen de eerste niet negatief mag zijn ?!

[kvdveer]

De opdracht is zeer duidelijk (complimenten) maar ik heb toch nog een vraagje:
is / een integer division of een gewone deling?

oftewel:
(1/2)*2 = 0 ?
(1/2)*2 = 1 ?

[Orphix]

Alleen gehele getallen worden gebruikt bij de invoer en antwoord. Echter tussendoor zijn wel niet-gehele getallen toegestaan. Bijvoorbeeld (3/4)*4 = 3.

dus (1/2)*2 = 1.

[kvdveer]

oeps... beter lezen...

Nu ik toch aan het zeiken ben... er staan geen bereiken voor de invoerwaarden. Mogen we 32-bits integers aannemen?

[Verwijderd]

Vraag: geldt de limiet van 10/20 minuten voor elke mogelijke invoer? [Zo staat het in de opgave, maar weten jullie dat zeker :)]

[kvdveer]

Op zaterdag 15 december 2001 03:02 schreef DiFool het volgende:
Vraag: geldt de limiet van 10/20 minuten voor elke mogelijke invoer? [Zo staat het in de opgave, maar weten jullie dat zeker :)]

Zo staat het in de opgave, en zo is het dus.
Dat is trouwens wel een poosje wachten voor de juri .

BTW... volgens mij haalt mijn algo de meeste combinaties van 7 in binnen 100 ms. Het is dus mogelijk.

[kvdveer]

code:

   39 ms 1 + 7 + 173 + 406 + 55 + 135 + 8 + 9 + 10 x (2 - 64) - 33 = 141
  220 ms 169 + 12 + 59 + 1.835 + 74 + 15 + 4 + 17 - 4 - 140 - 66 - 155 = 658
   30 ms 94 + 50 + 166 + 559 + 97 + 30 + 58 + 20 + 18 + (175 + 20) / 10 = 1.654
    0 ms 5 + 29 + 29 + 1.002 + 5 + 119 + 14 + 14 + 12 - 15 - 16 - 2 = 412
  149 ms 137 + 119 + 192 + 1.289 + 200 + 136 + 2 + 2 * 10 / 16 - 18 - 49 = 1.019
   10 ms 115 + 191 + 137 + 678 + 2 + 142 + 198 + 15 + 4 * 3 / 15 - 19 = 1.568
   81 ms 118 + 173 + 138 + 576 + 19 + 126 + 6 + 11 + 11 + 20 - 176 - 57 = 348
 6109 ms 32 + 54 + 36 + 1.154 + 15 + 2 + 2 x (122 + 15 x (32 - 58)) - 100 = 119
  160 ms 22 + 160 + 162 + 764 + 123 + 17 + 3 - 17 - 99 - 17 - 149 - 88 = 186
   10 ms 14 + 13 + 39 + 1.346 + 46 + 115 + (7 + 7 + 7 - 14 - 74) / 51 = 1.384
   10 ms 181 + 64 + 96 + 593 + 154 + 149 + 111 + (12 * 18 / 9 - 145) / 11 = 1.337
   20 ms 23 + 95 + 81 + 230 + 11 + 110 + (17 + 19 + 14 x (17 + 19)) / 135 = 554
  139 ms 141 + 147 + 100 + 1.328 + 32 + 47 + 2 x (3 + 20 + 7 x (73 - 190)) = 203
   10 ms 174 + 111 + 140 + 202 + 134 + 4 + (19 + 7 * 9 - 181) / 11 - 62 = 694
   30 ms 71 + 98 + 15 + 1.702 + 153 + 37 + 99 + 9 + 9 - 5 - 185 - 18 = 1.614
   29 ms 118 + 22 + 125 + 1.856 + 109 + 66 + 20 + 13 + 90 x (4 - 14) - 46 = 1.383
   40 ms 109 + 20 + 150 + 298 + 47 + 177 + 1 + 4 + (4 - 143) / 4 - 88 = 19
    0 ms 76 + 79 + 73 + 165 + 91 + 101 + 93 + 17 + (17 + 12) / 8 - 6 = 1.165
   10 ms 175 + 122 + 52 + 1.394 + 112 + 176 + 13 + 10 x (16 - 73) - 5 - 73 = 1.396
  130 ms 168 + 151 + 181 + 373 + 156 + 54 + 141 + (10 - 141) / 20 - 4 - 1 = 449
    0 ms 180 + 65 + 173 + 1.527 + 194 + 55 + 80 + 5 + 5 / 2 - 11 - 1 = 845
   10 ms 1 + 31 + 142 + 625 + 80 + 110 + 31 x (6 + 15) - 7 - 2 - 53 = 1.578
   80 ms 132 + 114 + 180 + 44 + 52 + 177 + 4 + 7 + 4 * 9 - 9 - 137 = 287
   10 ms 1 + 106 + 153 + 1.141 + 47 + 173 + (98 / 2 - 14) / 5 - 8 - 13 = 1.607
   40 ms 105 + 84 + 8 + 1.985 + 33 + 10 + 3 + 20 + 5 x (12 - 20) - 21 = 1.527
   79 ms 197 + 100 + 7 + 1.188 + 161 + 185 + (103 + 18 + 15 x (133 + 20)) / 16 = 1.989
  351 ms 147 + 157 + 4 + 733 + 64 + (18 + 157 x (53 + 18) - 1 - 19) / 15 = 1.848
 1832 ms 98 + 138 + 76 + 845 + 150 + 11 + 69 + (69 * 20 - 3) / 126 - 20 = 48
  289 ms 124 + 72 + 103 + 1.293 + 163 + 4 x (20 x (10 + 5) / 100 - 191) - 128 = 875
  831 ms 138 + 152 + 7 + 1.226 + 161 + 16 + (127 + 16) / 2 - 18 - 93 - 34 = 860
35310 ms 110 + 104 + 147 + 1.790 + 170 + (19 + 1 + 110 - 15 - 1 - 121) / 1 = 18

even opscheppen...

[edit] even een mooie piek van 35 seconden toegevoegd.

[Dash2in1]

Hey,

Doet hij het bij jullie ook met
9 9 9 9
324
?

Kwam er net achter dat me programma daarop dus niet werkt

[Twilight Burn]

Op zaterdag 15 december 2001 11:30 schreef Dash2in1 het volgende:
Hey,

Doet hij het bij jullie ook met
9 9 9 9
324
?

Kwam er net achter dat me programma daarop dus niet werkt

(9+9)*(9+9)
00:00:00.0800808

[Munters]

Op zaterdag 15 december 2001 03:24 schreef kvdveer het volgende:

[..]
10 ms 115 + 191 + 137 + 678 + 2 + 142 + 198 + 15 + 4 * 3 / 15 - 19 = 1.568
10 ms 14 + 13 + 39 + 1.346 + 46 + 115 + (7 + 7 + 7 - 14 - 74) / 51 = 1.384
[..]
even opscheppen...

1.568? 1.346? 1.384?
Het is extreem snel imo.
Maaruh... snap je de opgave eigenlijk wel?

[RickN]

Op zaterdag 15 december 2001 12:37 schreef Munters het volgende:

[..]

1.568? 1.346? 1.384?
Het is extreem snel imo.
Maaruh... snap je de opgave eigenlijk wel?

Ja, ik moest hier ook even 10 keer naar kijken, maar 1.568 is gewoon 1568

Maar verder, die metingen zeggen idd niet zoveel als je er niet bij zegt wat je hebt gemeten. Daarnaast zijn het natuurlijk wel extreem eenvoudige expressies die je daar berekent (bijna alleen plusjes)

En het is wel een beetje erg snel. Lijkt "to good to be true" en dat is het dan meestal ook. Garandeerd jouw algoritme dat er een uitkomst wordt gevonden als er een is (ook als er b.v. maar 1 goede oplossing is?)

[Verwijderd]

Op zaterdag 15 december 2001 03:24 schreef kvdveer het volgende:
Cijfers

Oke, maar probeer eens 7 cijfers, allemaal heel groot [dus geen 100 of zo], en niet mooi [geen 1000000], waar geen oplossing voor is, hoe snel is die dan?

[Dash2in1]

Op zaterdag 15 december 2001 12:49 schreef DiFool het volgende:

[..]

Oke, maar probeer eens 7 cijfers, allemaal heel groot [dus geen 100 of zo], en niet mooi [geen 1000000], waar geen oplossing voor is, hoe snel is die dan?

1234124 1234897 12351 9871235 8723451 12340975 1295871
0
41229 ms

Is dat snel? Enn, ach, maakt toch niet heel veel uit als het snel is, want zoals eerder gezegd 9 9 9 9 = 324 vindt ie (nog) niet.

[D2k]

Op zaterdag 15 december 2001 03:10 schreef kvdveer het volgende:

[..]

Zo staat het in de opgave, en zo is het dus.
Dat is trouwens wel een poosje wachten voor de juri .

* D2k gaat ff een tukkie doen tijdens het controleren

ff wat duurt dat soms lang zeg
of onze testset is te moeilijk voor de bruteforce

[Theswitch]

Op zaterdag 15 december 2001 02:41 schreef kvdveer het volgende:
oeps... beter lezen...

Nu ik toch aan het zeiken ben... er staan geen bereiken voor de invoerwaarden. Mogen we 32-bits integers aannemen?

Ja hoor, da's meer als genoeg lijkt me zo

[Theswitch]

Op zaterdag 15 december 2001 13:25 schreef D2k het volgende:

[..]

* D2k gaat ff een tukkie doen tijdens het controleren

ff wat duurt dat soms lang zeg
of onze testset is te moeilijk voor de bruteforce

Als je er iets in perl hebt of in windows/exe kan je ook wat naar mij sturen hooor.

[D2k]

Op zaterdag 15 december 2001 14:36 schreef Theswitch het volgende:

[..]

Als je er iets in perl hebt of in windows/exe kan je ook wat naar mij sturen hooor.

k
tnx
ik ga je er nu eens sturen

[D2k]

Op zaterdag 15 december 2001 03:02 schreef DiFool het volgende:
Vraag: geldt de limiet van 10/20 minuten voor elke mogelijke invoer? [Zo staat het in de opgave, maar weten jullie dat zeker :)]

ja

[Theswitch]

Volgens mij is deze opgave niet zo populair aan het aantal reacties te zien.

Verder, hoe zit 't met de uitslag van opgave 2 jury?

[Verwijderd]

Ik heb echt geen idee hoe ik 't moet aanpakken (nouja brute force snap ik wel maar dan krijg je meer dan een miljard iteraties dus dat haal je niet qua tijd) dus dan is de opgave vrij snel niet meer interessant. Als iemand nu een tipje van de sluier zou kunnen oplichten in goed overleg met de jury dan zou de opgave wel weer interessant worden want dan kan je iig aan de slag ..

[wasigh]

Op zondag 16 december 2001 14:01 schreef eXoR het volgende:
Ik heb echt geen idee hoe ik 't moet aanpakken (nouja brute force snap ik wel maar dan krijg je meer dan een miljard iteraties dus dat haal je niet qua tijd) dus dan is de opgave vrij snel niet meer interessant. Als iemand nu een tipje van de sluier zou kunnen oplichten in goed overleg met de jury dan zou de opgave wel weer interessant worden want dan kan je iig aan de slag ..

de 1e goede oplossing die we binnen hadden was een bruteforce oplossing dus het is zeker mogelijk!

[Verwijderd]

Op zondag 16 december 2001 14:29 schreef wasigh het volgende:

[..]

de 1e goede oplossing die we binnen hadden was een bruteforce oplossing dus het is zeker mogelijk!

was dat mijn inzending? en zo nee, is die van mij al getest?

[D2k]

Op zondag 16 december 2001 14:43 schreef crashburn het volgende:

[..]

was dat mijn inzending? en zo nee, is die van mij al getest?

nee en nee
hij ligt bij een java man te w88 op controle

[Verwijderd]

Op zondag 16 december 2001 14:44 schreef D2k het volgende:

[..]

nee en nee
hij ligt bij een java man te w88 op controle

Is de testset die gebruikt word om de inzendingen te testen eigenlijk ergens vandaan te halen?

[D2k]

Op zondag 16 december 2001 14:55 schreef crashburn het volgende:

[..]

Is de testset die gebruikt word om de inzendingen te testen eigenlijk ergens vandaan te halen?

noopz
die wordt achteraf pas bekend gemaakt

[kvdveer]

Op zaterdag 15 december 2001 12:42 schreef RickN het volgende:

[..]

Ja, ik moest hier ook even 10 keer naar kijken, maar 1.568 is gewoon 1568

Maar verder, die metingen zeggen idd niet zoveel als je er niet bij zegt wat je hebt gemeten. Daarnaast zijn het natuurlijk wel extreem eenvoudige expressies die je daar berekent (bijna alleen plusjes)

En het is wel een beetje erg snel. Lijkt "to good to be true" en dat is het dan meestal ook. Garandeerd jouw algoritme dat er een uitkomst wordt gevonden als er een is (ook als er b.v. maar 1 goede oplossing is?)

het zijn willekeurig gegenereerde variabelen. (ik geloof dat het vierkeer random(2000) was, 3xrandom(500) en twee keer random(20). Dat er plusjes en minnetjes uit komen is verklaarbaar: mijn algo geeft die grotere voorkeur, en als er meerdere oplossingen zijn, dan komen er dus antwoorden met plusjes en minnetjes uit.

Het algo is niet volledig. Het vindt ongeveer 90% van de antwoorden. als het antwoord niet gevonden wordt, dan probeer ik met een veel intensievere algo alsnog de oplossing te vinden.

[Verwijderd]

Op zondag 16 december 2001 14:29 schreef wasigh het volgende:

de 1e goede oplossing die we binnen hadden was een bruteforce oplossing dus het is zeker mogelijk!

Mja, tuurlijk is dat mogelijk. Omdat het zelden gebeurt dat je via brute force echt tot de laatste mogelijkheid moet zoeken. Als dat toch 't geval is, tja, dan ben je de klos...
Want ff rap gerekend moet de brute force die ik zo snel bedenk niet minder dan 10.899.947.520 mogelijkheden testen (bij 7 getallen als input dus). Als dat binnen de 20 minuten moet, dan moet ie er dus meer dan 9 miljoen testen per seconde in het allerslechtste geval. Vergeet dat dus maar Want op de testmachine (dacht PIII 700) komt dat heel grofweg overeen met een 70tal machine-instructies per test. Juist ja... Of zouden we 't toch maar in asm gaan doen ?

[Theswitch]

Ik denk niet dat dit een spoiler is, maar gewoon een ideetje

code:

(1*2) + (3*4) 
(3*4) + (1*2)
(2*1) + (3*4)
etc

zijn allemaal dezelfde berekeningen he