Hvordan løser man NIO-oppgaver?

En (overdrevent enkel) NIO-oppgave kan se omtrent slik ut:


Oppgave

Ola er overbevist om at han har dårlig trynefaktor, for læreren har gitt ham en lang liste med tall som han vil at Ola skal regne ut som hjemmelekse som må leveres kl. 08:15 dagen etter. Dette har ikke Ola særlig lyst til å gjøre for hånd – skriv et program som kan hjelpe ham!

Input

Første linje inneholder et heltall n, som forteller hvor mange tall som skal adderes. Deretter følger en linje med de n heltallene som skal adderes. n vil være mindre enn eller lik 1000000, og hvert enkelt tall vil være mellom -2000000000 og 2000000000. Eksempel:

3
5 8 -4

Output

Én linje, som inneholder summen av de n tallene. Summen kommer garntert til å være mindre enn eller lik to milliarder. Eksempel:

9


Oppgaveteksten er en eller annen situasjon som skaper behovet for en eller annen utregning, ofte formulert som en litt humoristisk (og litt tåpelig) historie. Noen ganger er oppgaveteksten skrevet slik at den distraherer litt fra hva oppgaven egentlig handler om, så det gjelder å ikke henge seg for mye opp i detaljene der og heller få en forståelse for hva selve utregningen handler om. I dette eksempelet er det ganske enkelt snakk om å addere tall – alt snakket om lekser og innleveringsfrist er irrelevant.

Inputen kommer alltid til å oppfylle betingelsene i oppgaveteksten! Når man skriver programmer i den virkelige verden, er det veldig viktig at man sjekker at inputen faktisk er gyldig (dette kalles å gjøre inputvalidering), men siden dette er en konkurranse og den ikke handler om inputvalidering, har vi sørget for at man ikke trenger å bry seg om dette. Så i dette eksempelet kan programmet uten videre anta at det faktisk bare kommer til å stå heltall i inputen, og at vært tall vil få plass i en int. Noen ganger sier oppgaveteksten også at svaret kommer til å holde seg innenfor en viss grense; det kan du også stole på – selv om det selvfølgelig er mulig at summen av en million tall på opptil to milliarder blir mye mer enn to milliarder, vil inputen være slik at summen holder seg innenfor to milliarder (dvs. at man enten blir bedt om å summere noen få store tall, eller mange små tall, eller mange tall som både er positive og negative). I noen slike oppgaver må du likevel passe på dersom du gjør mellomregninger hvor resultatene underveis kanskje kan bli større.

Det er også veldig viktig at outputen er eksakt på det formatet som blir beskrevet (inkludert linjeskift etter hver linje), og at programmet ditt ikke produserer mer output enn nødvendig. Du kan altså ikke skrive ut hjelpetekster som f.eks. “Skriv inn et tall:” eller “Svaret er:”. Dersom du er på Windows og bruker system("PAUSE") i slutten av programmet for å hindre at konsollvinduet lukker seg når programmet er ferdig, må du fjerne denne før du sender inn. Du kan godt printe ekstra tekst som debuggingshjelp underveis, men du må fjerne dette før du sender inn. main() er også nødt til å returnere 0.

Vi kommer antageligvis ikke til å lese koden din, så kommentarer trengs ikke. Det er heller ikke nødvendig at koden er spesielt lesbar, men for din egen del bør du prøve å ha ryddig kode og forståelige variabelnavn.

Hele besvarelsen må ligge i én .cpp-fil, og det er denne (ikke .exe-filen) du skal sende inn. Dersom du bruker Visual Studio, er det dermed viktig at du krysser av for Empty Project når du lager et nytt prosjekt. Dersom du definerer dine egne klasser, må du også ha klassedeklarasjonen i selve .cpp-filen, selv om dette ikke er god praksis til vanlig.

En perfekt besvarelse av oppgaven ovenfor ser dermed slik ut:

#include <iostream>

using namespace std;

int main() {
    int n;
    cin >> n;
    int sum = 0;
    for (int i = 0; i < n; i++) {
        int number;
        cin >> number;
        sum += number;
    }
    cout << sum << endl;
    return 0;
}

Når du leverer inn koden, blir den kompilert av vår datamaskin, og programmet blir først kjørt én gang mot et datasett som ligner på eksempelet i oppgaveteksten. Resultatet herfra vises som “Public score”. Trykk “Play”, og så blir programmet ditt kjørt flere ganger med forskjellig input av økende størrelse og vanskelighetsgrad, så får du poeng ut fra hvor mange inputsett programmet ditt svarte rett på – dette vises som “Total score”, og er den faktiske poengsummen din. Det at programmet ditt svarer rett på eksempelinputen i oppgaveteksten er altså ikke noen garanti for at du får full score. Dersom programmet ditt svarer feil på noen av datasettene, føles det litt som å famle i blinde fordi du ikke får se inputen som programmet ikke klarte – men det er litt av utfordringen! ;-) Da må du prøve å tenke ut situasjoner som faller innenfor det oppgaveteksten beskriver og som kanskje ikke programmet ditt takler, og kanskje lage dine egne datasett (kanskje du til og med må skrive et eget program for å generere datasett så du får testet ut ting). Heldigvis du kan sende inn så mange ganger du vil, og den beste besvarelsen på hver oppgave teller – du trenger altså ikke å være redd for å sende flere ganger.

Konkurranseserveren har dessverre noen bugs som gir villedende tilbakemelding i noen tilfeller. De vi vet om hittil er:

  • Compilation failed – Time out: Antageligvis er det stor trafikk på serveren; vent litt og send inn på nytt.
  • Execution killed because of forbidden file access: Programmet ditt bruker for mye minne. Grensen er 256 MB hvis ikke oppgaveteksten sier noe annet.
  • Execution killed because of forbidden syscall rt_sigprocmask.: Du har utført en ulovlig handling på en STL-container (vector, set, map, queue osv.), f.eks. at du går utenfor grensene eller prøver å kopiere et område som ikke eksisterer, eller du har glemt å fjerne system("PAUSE") før innsending.
  • Execution killed with signal 8: Du har utført en matematisk ugyldig operasjon, f.eks. å dele på 0. Merk at hvis du har en int-variabel som du gjentatte ganger dobler, vil variabelen til slutt overflow’e og muligens bli 0. Dette vil ikke i seg selv føre til en krasj, men hvis du deler noe på den variabelen, vil det krasje.
  • Execution killed with signal 11: Programmet ditt prøver å lese eller skrive til minne det ikke eier – typisk fordi du går utenfor grensene på et array eller en vector. Merk også at det er farlig å lage store arrays eller arrays med dynamisk størrelse på denne måten: int numbers[size]; – bruk heller dynamisk minneallokering: int * numbers = new int[size]; .

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>