Reaali Robootika.COM

NXT robotimaailm ja programmeerimine C-keeles

Informaatika olümpiaadi põhikooli eelvoor – Jada seest numbri leidmine

26 December 2011 Leivo (2)

http://www.teaduskool.ut.ee/orb.aw/class=file/action=preview/id=6379/poh.et.pdf 

3. Jada - 1 sekund - 50 punkti

Vaatleme (lõpmatut) numbrijada, mille saame kõigi positiivsete täisarvude kasvavas järjekorras üksteise järele kirjutamisega: 123456789101112131415...

Kirjutada programm, mis leiab selles jadas positsioonidel N ja N + 1 olevad numbrid.

Sisend. Tekstifaili jada.sis ainsal real on täisarv N (1 <= N <= 109).

Väljund. Tekstifaili jada.val ainsale reale väljastada kaks numbrit — jada otsitavad elemendid. Numbrid väljastada vahetult üksteise kõrvale, ilma tühikuteta.

Näide. jada.sis

5

jada.val

56

Näide. jada.sis

14

jada.val

12

Hindamine. Testides summaarse väärtusega 30 punkti on N <= 106 ja nende hulgas testides summaarse väärtusega 15 punkti on N <= 103.

Selle lahenduse väljamõtlemine oli kõige keerulisem. Siin tekkis mitu lahendusvarianti kuid kas alljärgnev on kõige efektiivsem, selles pole ma kindel. Sisetunne ütleb, et seda saaks intelligentsemalt teha, kuid minu arvuridade seaduspärade õppimine on üsna kaugesse kooliaega libisenud seega lähenesin nö. “brutal force” meetodil ülesande lahendamisele.

Alljärgnevaga on ülesanne lahendatud, aga äkki on kellelgi parem meetod?

Code Snippet
  1. #include <stdio.h>
  2.  
  3. FILE *jada, *valf;
  4.  
  5. int _tmain(int argc, _TCHAR* argv[])
  6. {
  7.     int temp;
  8.     int sisend;
  9.     int i;
  10.     int tulemus;
  11.     int jrk;
  12.     int end = 0;
  13.  
  14.     jada = fopen("jada.sis", "r");
  15.     fscanf( jada, "%i", &sisend);
  16.  
  17.     for(i=1; i<100000000; i++)
  18.     {
  19.         temp = i;
  20.         jrk = 0;
  21.         //järgmise while tsükli abil saame teada mis number on sisend positsioonil
  22.         //ja mitmendal kohal antud numbri sees on otsitav arv
  23.         while(temp > 0) {
  24.             temp = temp/10;
  25.             end++;
  26.             jrk++;
  27.             if(end == sisend)
  28.                 break;
  29.         }
  30.         if(end == sisend)
  31.             break;
  32.     }
  33.  
  34.     //saame teada numbri positsioonide arvu
  35.     temp = i;
  36.     end = 0;
  37.     while(temp > 0) {
  38.         temp = temp/10;
  39.         end++;
  40.     }
  41.  
  42.     //vastavalt postisioonile leiame numbri seest arvu
  43.     temp = i;
  44.     for(int k = jrk; k <= end; k++)
  45.     {
  46.         tulemus = temp%10;
  47.         temp = temp/10;
  48.     }
  49.  
  50.    printf("arv on %i\n", tulemus);
  51.    valf = fopen("jada.val", "w");
  52.    fprintf(valf, "%i%i\n", tulemus, tulemus+1); 
  53.    fclose(valf);                                      
  54.    return 0;
  55. }
Tags :

Comments (2) -

  • Simmo

    12/27/2011 12:38:05 PM | Reply

    Ei süvenenud väga su lahendusse, kuid see for loop on küll hirmuäratav. Lisaks tundub mulle, et see programm ei väljasta õiget tulemust: programm väljastab tulemus ja tulemus+1, kuid küsiti hoopis numbrit N ja N+1 positsioonil, mitte ühe võrra suuremat (näited on petlikud).

    Minu C++ lahendus, mis sai maksimumi, oli selline:  (code tagi ka kuidagi saab kommentaaris?)
    #include <iostream>
    #include <fstream>
    #include <sstream>
    #include <cmath>

    using namespace std;

    // arvuta mitu symbolit on vastava jargu arvudel kokku
    unsigned int astesym(int aste)
    {
        return 9 * pow(10.0, aste) * (aste + 1);
    }

    int main()
    {
        ifstream fin("jada.sis");
        ofstream fout("jada.val");
        
        unsigned int N;
        fin >> N;
        
        // vahenda arvu, leia jark
        int aste = 0;
        for (; N > astesym(aste); aste++)
        {
            N -= astesym(aste);
        }
        
        // sea loendamise alguseks 0; 1 asemel
        N--;
        
        // leia arv milles N on ja mitmes number (i)
        unsigned int num = pow(10.0, aste) + N / (aste + 1);
        unsigned int i = N % (aste + 1);
        
        // tekstina num ja sellest jargmine(kui i peaks ule minema)
        stringstream ss;
        ss << num << num + 1;
        string str = ss.str();
        
        fout << str[i] << str[i + 1] << endl;
        
        return 0;
    }

  • Leivo

    12/27/2011 1:35:06 PM | Reply

    Suurepärane.
    See loop tundus ka mulle endale üsna hirmuäratav Smile
    Tänud selle korrektse lahenduse jagamise eest!

Add comment

Loading