Selasa, 19 November 2013
Bukit dan Lembah
| Batas Waktu | 1 detik |
| Batas Memori | 32 MB |
| Sumber | OSN 2005 |
Pak Dengklek memberikan Anda data ketinggian yang di catat dalam perjalanannya dari suatu posisi awal ke posisi akhir. Data ketinggian adalah bilangan-bilangan positif. Jalan kadang menaik, kadang menurun, kadang datar saja. Posisi di mana terjadi perubahan menaik kemudian menurun (boleh diselingi jalan datar) didefinisikan sebagai puncak dari suatu bukit. Sebaliknya, posisi terjadi perubahan dari menurun terus menaik (boleh diselingi bagian jalan yang datar) didefinisikan sebagai titik terbawah suatu lembah. Walaupun perubahan tersebut kecil saja, definisi itu tetap berlaku.
Carilah beda ketinggian terbesar antara puncak bukit dengan titik terbawah lembah berikutnya atau sebaliknya antara titik terbawah lembah dengan puncak bukit berikutnya pada data perjalanan tersebut.
Format Masukan
Banyak baris, antara 2 sampai 600.000 baris, yang masing-masing berisi sebuah bilangan bulat antara 0 sampai 1.000.000.000.
Format Keluaran
Sebuah baris berisi sebuah bilangan bulat yaitu beda ketinggian terbesar yang diperoleh.
Contoh Masukan
10 26 26 35 35 27 30 30 45 10 8 9
Contoh Keluaran
37
Penyelesaian
ini test case nya sudah ditambah, kalau pake code yang ini tidak sesuai dengan maksud soal karena hanya mencari bukit paling tinggi - lembah paling rendah, monggo di coba lagi
BalasHapusIya ini kalo ini mah cari terbesear - terkecil,
HapusSori blm gw edit disini udah jarang update xD
Gan cuma mau kasih referensi gan
BalasHapusKodenya bukan begitu, yg itu ga ac
Gini nih kodenya (pake c++ tapi) :
#include
#include
#include
#include
using namespace std;
int main()
{
int bil[600000],ujung[600000],baru[600000];
bool xtra[600000];
int i,j,k,m;
int x,maks,h,y;
i=1;
while(scanf("%d",&bil[i])!=EOF)
{
xtra[i]=true;
i++;
}
x=1;
for(j=1;j<=i-1;j++)
{
if(xtra[j])
{
k=1;
baru[x]=bil[j];
x++;
while(bil[j+k]==bil[j])
{
xtra[j+k]=false;
k++;
}
}
}
y=1;
for(m=1;m<=x-1;m++)
{
if((m==1) || (m==x-1))
{
ujung[y]=baru[m];
y++;
}
else
{
if((baru[m-1]baru[m]) && (baru[m+1]>baru[m]))
{
ujung[y]=baru[m];
y++;
}
}
}
}
maks=0;
for(i=2;i<=y-1;i++)
{
h=abs(ujung[i]-ujung[i-1]);
if(h>maks)
{
maks=h;
}
}
printf("%d\n",maks);
return 0;
}
Yang pertama baca input
Yang kedua kita buang input2 yg bernilai sama dan indeksnya berurutan, jadi kita masukkan ke array lain dengan nilai berbeda untuk indeks yg berurutan
Yang ketiga kita tentukan max dan min serta kita masukkan kembali ke array yg lain
Setelah itu yg terakhir kita gunakan fungsi abs( ) untuk menghitung selisih dari max dan min yg indeksnya berurutan dan kita cari selisih terbesarnya
NB : Sepertinya testcase soal ini pada tokilearning telah di update, jika kita masukkan jawaban di blog Anda yang hanya mengurangkan max - min ke tokilearning sekarang akan salah (hanya accepted sebelum di update)
Iya presepsi gw yg sebelumnya salah, makasih sarannya. code gw yg ini jg sudah AC kok http://ideone.com/6oHpit
Hapus