Dec 072009
 

Problemset bisa didownload di sini:
BNPCHS 2009 Final Round – Problemset (PDF – 496KB)

Testdata bisa didownload di sini:
BNPCHS 2009 Final Round – Testcase (ZIP – 3091KB)

Pembahasan solusi bisa dilihat di sini:

  13 Responses to “BNPCHS 2009 – Final Round”

  1. pertamax! 😀

  2. setelah di teliti, 10 problems yang ada, problem authornya beda2 smua :))

  3. Argghhhh, problem A dan G ngga akan pernah gw lupain !

  4. Wah soal2nya bagus2 loh…
    Variasinya dan tingkat kesulitannya pas!

    Hore… sekarang tidak ada alasan lagi untuk tidak nge-blog INC/ICPC 09 >:)

  5. kok blakangan ini write-upnya ngga ada storynya pak? spt write-up HS07 gt… pengen tau behind the scene-nya kayak apa 😀

    anyway, soalnya bagus2 & menarik, tapi banyak bgt euy 😀

  6. writeup icpc….~ >:)

  7. gan, ada contoh kodingannya g tentang problem dari A-j tu???
    kirimin dong.. thanks

  8. yang soal B bukannya seharusnya kita uji apakah x >= A-1 ya ??

  9. Pak Hendry, solusi saya seperti ini, tapi kok di tokilearning masih TLE. Kenapa ya?


    #include

    using namespace std;

    int get_last_digit(int n) {
    int precompute[10][4] = {
    0, 0, 0, 0,
    1, 1, 1, 1,
    6, 2, 4, 8,
    1, 3, 9, 7,
    6, 4, 6, 4,
    5, 5, 5, 5,
    6, 6, 6, 6,
    1, 7, 9, 3,
    6, 8, 4, 2,
    1, 9, 1, 9,
    };

    return precompute[n % 10][n % 4];
    }

    int main() {
    int T;
    cin >> T;

    while (T--) {
    int N;
    cin >> N;

    int res = 0;

    for (int i = 1; i <= N; i++) {
    res += get_last_digit(i);
    }

    cout << res % 10 << endl;
    }

    return 0;
    }

    • Eh, ini maksudnya untuk soal I yang Jumlah Pangkat.

    • Code kamu masih recompute jawaban untuk setiap query/case, sehingga total kompleksitas untuk T kasus menjadi O(TN). Codenya bisa diimprove dengan precompute semua jawaban dari 1..N dan simpan ke dalam array, sehingga setiap kali ada case input X, tinggal cout array[X]. Cara precomputenya kan gampang:

      arr[1] = get_last_digit(1);
      for ( int i = 2; i <= 1000000; i++ ) arr[i] = arr[i-1] + get_last_digit(i); Dengan demikian total kompleksitasnya jadi O(T + N), which is lebih bagus dari yang punya kamu sekarang.

 Leave a Reply

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=""> <s> <strike> <strong>

(required)

(required)