Dec 172008
 

Bina Nusantara Programming Contest for High School Students (BNPCHS) 2008

Problemset bisa didownload di sini:
BNPCHS 2008 – Problem Set (PDF – 366KB)

Test Data bisa didownload di sini:
BNPCHS 2008 – Test Data (ZIP – 2135KB)

Pembahasan solusi bisa dilihat di sini:

  19 Responses to “BNPC HS 2008 – Problem Set & Analysis”

  1. Bahas soal penyisihannya juga

  2. @wonder
    ada di blog saya untuk yang ACM Mode. 🙂

  3. hmm.., mo nanya Om Shu, itu shot[i] bt apa ya gunany? kl ga pk shot[i] hasilny sm aja kan? tq

  4. @tukangtanya: itu kan untuk menentukan titik mana yang sudah di ambil dan mana yang belum.

  5. itu yang c/c++ sebernya buat c++ kan.. tp aq msh blm biasa ma c++, nah aq coba coding di ats aq ubah k dlm c. untuk algo insya aq dah ngerti, pertama di masukan k dlm array, lalu di sorting berdasarkan finish trs cari ajj hasilnya..
    untuk test case aq dah berhasil tapi ketika di coba upload di toki learning selalu time limited..
    gimana cara untuk ngakalinya yahh??, mohon bantuannya…

    • sortnya pake apa?

      • scanf(“%d %d %d”,&t,&d,&e);
        c=0;
        saji[c].h=t+d+e;//h =makanan habis atw selesai
        saji[c].m=t+d;//m=makanan matang atw start

        for(c=1;c=0 && status==0){
        if(saji[j].h <= lama){
        status=1;
        }else{
        saji[j+1].h=saji[j].h;
        saji[j+1].m=saji[j].m;
        j–;
        }
        }
        saji[j+1].h=lama;
        saji[j+1].m=t+d;
        }

        asalnya aku pisahkan proses sort dengan proses inputan, karena time limit aq satukan seperti di atas.. tapi masih saja time limit..
        mohon bantuannya…

      • yang di ats slh maaf..

        scanf(“%d %d %d”,&t,&d,&e);
        c=0;
        saji[c].h=t+d+e;
        saji[c].m=t+d;

        for(c=1;c=0 && status==0){
        if(saji[j].h <= lama){
        status=1;
        }else{
        saji[j+1].h=saji[j].h;
        saji[j+1].m=saji[j].m;
        j–;
        }
        }
        saji[j+1].h=lama;
        saji[j+1].m=t+d;
        }

      • kok bagian whilenya selalu ilang yahh..
        aq jelasin ajj yahh, moga bisa ngerti..
        jadi setelah input, datanya langsung di simpen di dlm array dengan tempatnya yang bener…

        klw kirim email bisa g pa, tolong periksain.. 😀

      • Tulis codenya di http://ideone.com/ aja deh, trus paste linknya di sini, itu code di atas banyak yang hilang kayaknya (gw jg ga liat ada sortnya di mana).

      • Ya iya itu algoritmanya O(n^2), jelas TLE kan N nya bisa 100.000. Kudu pake sorting yang O(n lg n): merge sort, quick sort, heap sort, ato apa lah.

      • ohhh gituu yahhh…
        msh blm ngerti apa itu O(n^2) atw O(n lg n), hehehehehe
        coba cari merge sort atw heap sort. pernah ngerti quick sort tapi quick sort yang aq pelajari masih suka bocor 🙁

        makasih yahh omm… 😀

  6. coment yang di ats untuk soal makan sepuasnya…

  7. Pa kalau Run Time Error biasanya di sebabkan oleh apa aja yahh pa???

  8. used[line[i]-‘a’] = true;
    itu maksudny apa ya

    • dipecah satu per satu aja.

      line[i] itu isinya karakter, antara ‘a’ samapi ‘z’.

      line[i] – ‘a’ itu u/ mengubah ‘a’..’z’ (97 .. 122) menjadi 0..25.
      kode ascii ‘a’ itu nilainya 97. jadi kalau kita printf( “%d\n”, ‘a’ ); nilai yang tercetak adalah 97.

      used[line[i]-‘a’] = true; itu kita ngubah array used ke line[i]-‘a’ (ini antara 0..25) jadi true.

  9. pak, bisa jelasin knp antirudal, kalo disort menurut t harus pake h terbesar? ga dpt logikanya

    • wah, ini blog saya tulis 7 tahun yang lalu, udah rada lupa.

      anw, sortnya perlu gitu karena ada masalah pada “< " dan "<=" berikut:

      dua buah rudal yang memiliki…

      1. h sama namun t berbeda bisa ditembak dengan anti-rudal yang sama.
      2. t sama namun h berbeda tidak bisa ditembak dengan anti-rudal yang sama.

      contoh inputnya (udah diurutkan berdasarkan t menaik dan h menaik):

      4
      2 2 3 5
      3 6 9 3

      dengan urutan seperti itu, kita akan menembak 3 kali: {(2, 3), (3, 9)}, {(2, 6)}, dan {(5, 3)}. padahal kalau (2, 6) dipasangkan dengan (3, 9), maka (2, 3) dan (5, 3) bisa dipasangkan; hanya perlu 2 anti-rudal.

      antara (2, 3) dan (2, 6), si (3, 9) lebih untung jika dipasangkan dengan (2, 6) — yang paling tinggi di t = 2. karena (2, 3) masih bisa mencapai rudal-rudal lain (jika ada) yang tingginya antara 3..5, yang ga bisa dicapai rudal (2, 6). dan di kasus di atas, ada rudal yang demikian: (5, 3).

 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)