Olimpiade Sains Provinsi (OSP) 2019 - Komputer

Diberikan graf seperti Gambar 1 di bawah ini. Graf ini terdiri dari 6 simpul dan 7 garis yang menghubungkan antar simpul.

Pak Dengklek dapat menghapus tepat 1 garis antar simpul pada graf tersebut. Sebagai contoh, apabila garis antar simpul 2 dan 6 dihapus, maka dihasilkan graf G seperti pada Gambar 2 di atas. Setelah itu, Pak Dengklek akan memilih himpunan simpul H dari graf G, sehingga simpul-simpul pada H sebanyak mungkin, dan tidak ada satu pun simpul yang terhubung langsung dengan simpul lain. Sebagai contoh, untuk Gambar 2 di atas, H yang terpilih memiliki 3 simpul (dapat memilih simpul bernomor 3, 4, dan 6).

Untuk setiap konfigurasi G yang dapat dibentuk dari Graf Awal (Gambar 1), berapakah maksimal banyaknya simpul pada H yang mungkin?

Struktur pohon di bidang informatika adalah sebuah struktur yang terdiri dari sebuah simpul yang disebut akar (root) dan dapat mempunyai anak yang berupa sub-pohon. Simpul yang tidak mempunyai sub-pohon disebut daun. Sebuah pohon dapat hanya terdiri dari satu simpul saja.

Pak Dengklek ingin membuat kandang bebek yang jika dihubungkan, akan membentuk sebuah struktur pohon N-ary seimbang penuh, yang setiap simpulnya akan ditempati maksimal oleh 1 bebek. Sebuah pohon dikatakan N-ary seimbang penuh apabila setiap simpulnya mempunyai tepat N sub-pohon kecuali daun.

Pak Dengklek akan menaruh bebek mulai dari akar pohon, dan hanya kandang yang merupakan daun yang boleh kosong. Contoh gambar pohon N-ary seimbang penuh dengan N=2 dan N=3 diberikan sebagai berikut.

Pak Dengklek ingin agar susunan kandang tersebut membentuk sebuah pohon N-ary seimbang penuh yang seindah mungkin. Nilai keindahan konfigurasi didefinisikan sebagai hasil penjumlahan dari jarak masing-masing simpul berisi bebek ke akar pohon. Jika Pak Dengklek mempunyai 31 bebek, berapakah N terbesar sehingga nilai keindahan kandang bebeknya ≥ 50?

Pak Dengklek ingin membuat deret bilangan a_i, i = 1..N, dengan syarat sebagai berikut:

• fpb(a₁, a₂, …, a_N) = 15,
• kpk(a₁, a₂, …, a_N) = 90, dan
• 0 < a₁ < a₂ < ⋯ < a_N.

Berapa banyak kemungkinan deret bilangan berbeda yang memenuhi ketiga syarat di atas, untuk semua N yang mungkin?

Dari seluruh himpunan yang tercipta, tentukan nilai maksimum dari banyaknya nilai TRUE setiap himpunan.

Pak Dengklek tahu bahwa dari 6 pernyataan tersebut, terdapat 3 pernyataan yang bernilai FALSE. Untuk kasus ini, tentukan nilai maksimum dari banyaknya nilai TRUE setiap himpunan.

Mata uang di negara Pak Blangkon hanya memiliki 3 macam koin, yaitu bernilai 1, 7, dan 23. Oleh mesin penukar uang negara tersebut, uang bernilai x akan ditukar, dimulai dengan koin bernilai paling besar. Apabila ada sisa, maka akan ditukar dengan koin bernilai kedua terbesar, dan seterusnya sampai nominalnya bernilai x. Algoritma yang dijalankan oleh mesin penukar tersebut menjamin bahwa banyaknya koin yang dikeluarkan adalah minimum dengan jenis koin yang sudah ada.

Pak Blangkon ingin membuat tepat 1 (satu) koin dengan nilai baru antara 2 sampai dengan 30 (inklusif), nilainya tidak sama dengan koin yang sudah ada, dan jaminan di atas tetap berlaku. Ada berapa banyak nilai koin baru yang mungkin?

Berapa langkah yang akan dijalankan oleh robot tersebut hingga ia sampai ke tujuan? (Tuliskan angka -1 jika robot tidak akan pernah sampai ke tujuan)

Jika anda dapat mengubah tepat satu sel '.' menjadi '#', sel manakah yang harus dipilih sehingga membuat robot dapat mencapai tujuannya dengan langkah semaksimal mungkin? Tuliskan jawaban dalam bentuk "baris,kolom" (tanpa tanda spasi dan tanpa tanda petik). Contoh: 1,1

Berapakah total biaya minimum yang diperlukan pak Dengklek agar seluruh desa terhubung satu sama lain?

Selain ingin mendapatkan total biaya termurah untuk membangun desa, Pak Dengklek juga ingin mengetahui total biaya termurah kedua dengan konfigurasi yang berbeda (jumlahnya boleh sama dengan total biaya termurah pertama). Berapakah total biaya termurah kedua yang mungkin?

Pak Dengklek akan mengirim sebuah pesan ke anaknya. Pesan tersebut hanya terdiri dari deretan angka. Ia ingin merahasiakan pesan tersebut, sehingga ia mengubahnya dengan sebuah fungsi pengkodean f yang merepresentasikan perubahan setiap angka dalam pesan tersebut.

Sebagai contoh, jika perubahan angka yang diberikan adalah sebagai berikut:

Maka, f("0123456789") = "1470362958", dan f("3820") = "0571".

Ia ingin mengirimkan pesan dengan fungsi pengkodean yang lain. Ia hanya tahu dengan fungsi tersebut, f(f("0123456789")) = "1783024659". Berapakah nilai dari f("0123456789")?

Diketahui beberapa pernyataan berikut yang dapat bernilai benar atau salah:

1. Ada pernyataan di bawah pernyataan ini yang benar
2. Ada pernyataan di atas pernyataan ini yang benar
3. Ada pernyataan di atas pernyataan ini yang salah
4. Ada pernyataan di bawah pernyataan ini yang salah
5. Ada pernyataan di bawah pernyataan ini yang benar
6. Ada pernyataan di atas pernyataan ini yang benar
7. Ada pernyataan di atas pernyataan ini yang salah
8. Ada pernyataan di bawah pernyataan ini yang salah

… (pola berlanjut)

2017. Ada pernyataan di bawah pernyataan ini yang benar
2018. Ada pernyataan di atas pernyataan ini yang benar
2019. Ada pernyataan di atas pernyataan ini yang salah
2020. Ada pernyataan di bawah pernyataan ini yang salah

Ada berapa maksimal pernyataan yang dapat bernilai benar?

Angka 2²⁹ mempunyai 9 digit dan semua digitnya berbeda. Digit apa yang tidak terdapat di dalam angka tersebut?

Pak Dengklek sedang mengecek berkas OSP Komputer 2019. Salah satu soalnya berbunyi seperti ini:

"Berapa banyak bilangan di antara [1 .. 1000] (inklusif) yang habis dibagi 3 dan habis dibagi x?"

Pak Dengklek tahu bahwa jawabannya adalah 393, namun ia lupa berapakah nilai x. Pak Dengklek hanya ingat bahwa 3 dan x pasti relatif prima. Dua bilangan dikatakan relatif prima apabila faktor persekutuan terbesar dari kedua bilangan tersebut adalah 1. Berapakah nilai x?

Jika diketahui Pak Dengklek melakukan perjalanan dari Kota-0 ke Kota-9 melewati tepat 4 penerbangan, berapa banyak kemungkinan rute berbeda yang bisa diambil?

Untuk menghindari kemungkinan cuaca buruk, beberapa rute penerbangan akan dibatalkan. Berapa rute penerbangan minimal yang harus ditutup sedemikian sehingga banyaknya rute yang bisa diambil dari Kota-0 ke Kota-9 masih tersisa tepat 2 kemungkinan rute?

Pak Dengklek mempunyai sebuah mesin. Mesin tersebut mengeluarkan 2 buah deretan angka acak yang masing-masing terdiri dari 0 dan 1 sepanjang 8 angka. Peluang kedua deretan tersebut identik dapat dinyatakan dalam bentuk (½)ⁿ. Berapakah n?

Diberikan graf dengan 10 simpul sebagai berikut:

Dari graf di samping (graf tidak berarah), berapakah jarak terkecil yang dapat ditempuh dari simpul 6 ke simpul 9?

Andi menemukan suatu permainan yang memiliki 10 pertanyaan di dalamnya. Beberapa pertanyaan hanya dapat dijawab apabila sudah berhasil menyelesaikan salah satu pertanyaan lain. Jika suatu pertanyaan A memiliki syarat B, C, D, maka Andi baru dapat menjawab pertanyaan A jika sudah berhasil menyelesaikan salah satu dari B, C, dan D. Syarat ini dituliskan dalam notasi A: [B, C, D].

Selengkapnya, permainan itu mempunyai syarat sebagai berikut:

• 1: [2, 3]
• 2: [5, 7]
• 3: [5, 9]
• 4: [7, 8]
• 5: [6, 10]
• 6: [3, 9]
• 7: [10]
• 8: [9, 10]
• 9: [7]
• 10: -

Pertanyaan nomor 10 dapat dijawab tanpa harus menyelesaikan pertanyaan lainnya.

Berapakah banyak pertanyaan minimum yang harus dijawab sebelumnya agar Andi dapat menjawab pertanyaan nomor 1?

Jika diketahui A bernilai TRUE, ada berapa kemungkinan kombinasi nilai B, C, D yang berbeda (tanpa memperhitungkan E) sehingga kelima premis tersebut benar?

Dari deskripsi di atas, berapa banyak kemungkinan kombinasi nilai A, B, C, D, dan E yang berbeda sehingga kelima premis tersebut benar?

Apabila N = 100, dari semua konfigurasi susunan kotak, berapakah jumlah pertukaran minimum yang mungkin terjadi sampai terurut?

Apabila N = 10, berapakah jumlah pertukaran minimum dari konfigurasi terburuk (worst case) untuk mengurutkannya?

Berapakah nilai dari F(N) apabila N = 12?

Berapakah nilai dari F(N) apabila N = 200?

Pak Dengklek memiliki sebuah kolam berisi sangat banyak ikan yang akan menjadi makanan bebeknya. Supaya teratur, Pak Dengklek membariskan bebeknya berdasarkan umur dari paling muda sampai bebek paling tua, dan menomorinya 1, 2, 3, dan seterusnya. Para bebek bergiliran makan ikan sesuai urutan baris. Bebek dengan nomor i harus mengambil tepat (2 * i - 1) ikan dari kolam tersebut.

Pak Dengklek datang setelah bebek dengan nomor X mengambil ikannya dan melihat bahwa tersisa 225 ikan di kolam tersebut. Ia tahu bahwa ada beberapa kemungkinan nilai X, namun ia penasaran, berapakah hasil penjumlahan dari semua kemungkinan nilai X tersebut, jika dijamin bahwa jumlah ikan di dalam kolam pada awalnya adalah N * N, dengan N > X?

Suatu saat, terdapat 10 bebek dan 10! ikan di dalam kolam. Para bebek sepakat untuk membagi ikan di dalam kolam tersebut dengan bermain dalam beberapa babak. Setiap babak dimainkan dengan aturan:

1. Bebek tertua di antara peserta permainan akan mengajak semua bebek peserta untuk membagi rata ikan di kolam tersebut.
2. Tiap bebek dapat menyatakan "OK" jika setuju, atau "NO" jika tidak.
3. Ada dua kemungkinan:
   • Jika bebek termuda tersebut dapat meyakinkan sedikitnya 50% bebek (termasuk dirinya) untuk menyatakan "OK", semua ikan dalam kolam akan dibagikan secara rata kepada peserta, dan permainan selesai.
   • Namun jika tidak, maka bebek tertua akan keluar dari permainan tanpa mengambil ikan dan permainan kembali ke langkah 1), untuk diulang pada babak berikutnya.

Catatan: N! = N x (N-1) x (N-2) x…. 3 x 2 x 1.

Setiap bebek berusaha mendapatkan ikan sebanyak mungkin dengan berpikir keras sebelum mengatakan "OK" atau "NO". Berapakah jumlah bebek peserta pada babak terakhir?

Sebagai contoh: Jika pada babak terakhir tersisa 2 ekor bebek, bebek yang lebih muda pasti akan memilih 'NO' karena ia ingin mendapatkan sebanyak-banyaknya ikan, namun bebek yang lebih tua lebih memilih membaginya dengan bebek yang lebih muda dibandingkan keluar dari permainan, sehingga ia akan memilih 'OK' dan permainan selesai.

Bebek Kwek hendak menyeberangi ladang yang berbentuk persegi secara diagonal dari ujung kiri bawah ke ujung kanan atas. Area ladang terbagi dalam kandang-kandang dan di dalam setiap kandang berisi beberapa ekor ayam. Gambar berikut ini menunjukkan petak-petak kandang dengan banyak penghuninya. Ketika Kwek berada di suatu kandang maka ia harus menyapa satu per satu penghuninya.

Saat itu Kwek agak terburu-buru, jadi tidak ingin berlama-lama menyapa ayam-ayam yang ditemuinya. Ia sudah berada di kandang kolom A baris 5 (kita sebut A5) dan pada akhirnya ia harus tiba di E1. Dari suatu kadang Kwek hanya dapat menuju ke petak di sebelah atas/bawah-nya atau sebelah kiri/kanan-nya. Misalnya, jika ia melalui lintasan A5-A4-B4-B3-B2-B1-C1-D1-E1 ia harus menyapa 27 ayam.

Tentukan lintasan yang harus dilalui Kwek supaya banyaknya ayam yang disapanya sesedikit mungkin. Tuliskan jawaban dalam bentuk lintasan (antar petak diberi tanda "-", dan tanpa tanda petik). Contoh penulisan: A5-A4.

Pak Dengklek hendak pergi ke pasar belanja makanan (pakan) bebek. Ia mendapat kabar bahwa harga pakan setelah pukul 8.00 akan naik. Sebelum pukul 8.00 harganya 100 ribu rupiah, setiap setelah 15 menit berikutnya harga itu akan dinaikkan 10 ribu rupiah, yaitu jam 8.00-8.14, menjadi 110 ribu rupiah, 8.15-8.29, menjadi 120 ribu rupiah, 8.30-8.44, menjadi 130 ribu rupiah, dan seterusnya.

Sayangnya, pagi itu Pak Dengklek bangun terlambat. Saat siap berangkat di halte angkot, waktu sudah menunjukkan pukul 8.08. Ia harus memilih angkot agar total uang yang dikeluarkannya untuk membeli pakan dan ongkos angkot adalah sesedikit mungkin. Berikut ini adalah tabel berisikan informasi sejumlah pilihan angkot (dibedakan dengan warna) yang hilir-mudik dari kampungnya ke pasar yang jadwal keberangkatannya berbeda-beda, dan waktu tempuhnya berbeda-beda (karena berkeliling ke tempat lain dahulu), serta tarifnya berbeda-beda.

Angkot manakah yang sebaiknya ia pilih?

Pak Dengklek kali ini membuat nama-nama sandi dari para bebeknya dengan suatu cara pengkodean yang aneh sebagai berikut.

• Huruf pertama nama tetap dan dijadikan huruf besar.
• Berikutnya, setiap huruf 'A', 'E', 'I', 'O', 'U', "H", 'W', 'Y' (termasuk huruf kecilnya) dihilangkan.
• Sisanya, ubah setiap huruf (termasuk huruf kecilnya) ke angka sebagai berikut:
  • B, F, P, V menjadi 1.
  • C, G, J, K, Q, S, X, Z menjadi 2.
  • D, T menjadi 3.
  • L menjadi 4.
  • M, N menjadi 5.
  • R menjadi 6.
• Beberapa angka yang sama secara berurutan diganti dengan hanya satu angka itu saja.
• Ambil empat huruf/angka terkiri dari yang sudah kode yang terbentuk; jika panjang kode kurang dari empat tambahkan akhiran beberapa angka 0 hingga panjang kode menjadi 4 huruf/angka.

Misalnya "Bob" dikode menjadi B100, "Bageur" dikode menjadi B260, "Heilbronn" dikode menjadi H416 dan "Essay" dikode menjadi E200. Menjadi apakah "Hilbert"?

Bebek Kwek menemukan peti harta karun. Sayangnya, peti tersebut terkunci dengan kunci kombinasi. Untuk membukanya terdapat sederetan 10 tombol; masing-masing tombol dapat menunjukkan angka 0 atau 1. Kwek menemukan juga sebuah tulisan di alas peti yang memberikan petunjuk mengenai kunci kombinasi:

• Aku memiliki tepat dua deretan 0-1-0 yang terpisah.
• Aku memiliki banyaknya 1 yang sama dengan banyaknya 0.
• Aku memiliki awalan 1-1-0 dan akhiran 1-0.
• Aku tidak memiliki deretan 1-0-0-0-1.

Tuliskan urutan kunci kombinasi ini? Tuliskan dalam format string berupa deretan 0 dan 1 yang dipisahkan oleh tanda strip "-". Contoh: 0-0-0-0-1-1-1-1-1-1

Bebek Kwak menemukan sebuah goa rahasia yang tertutup pintu. Pada pintu terdapat kunci kombinasi 3 angka, masing-masing dapat berharga bilangan 0 sampai dengan 9. Jika suatu kombinasi diberikan dan pintu dicoba dibuka maka terdengarlah suara.

• Kombinasi 1-7-2, suara "Satu benar tapi posisi salah"
• Kombinasi 8-5-4, suara "Dua benar tapi posisi salah"
• Kombinasi 9-8-6, suara "Satu benar tapi posisi salah"
• Kombinasi 7-5-1, suara "satu benar dan posisi benar"

Tentukan urutan kunci kombinasi yang semua benar dan posisi semua benar. Tuliskan 3 angka tersebut masing-masing dipisahkan oleh tanda strip "-". Contoh: 7-4-8

Suatu hari bebek Kwik pergi mengunjungi ke sejumlah desa: A, B, C, D, E dan F. Ia berangkat dari A ke desa-desa lainnya menggunakan sarana transportasi yang ada. Arah transportasi digambarkan dengan panah-panah yang menghubungkan satu desa dengan desa lainnya. Ada sarana transportasi yang gratis (ditunjukkan dengan panah bergaris putus-putus), dan ada sarana transportasi yang berbayar (ditunjukkan dengan panah bergaris tak putus-putus). Ia harus membayar 10 ribu rupiah untuk sarana transportasi berbayar sekali jalan (dari satu desa ke desa lain). Kebetulan pagi harinya Pak Dengklek memberkalinya uang 50 ribu rupiah.

Pada suatu saat (di suatu desa), Kwik mengabari Pak Dengklek bahwa uangnya habis hanya untuk membayar transportasi saja dan ia tidak sedang berada di B maupun di E. Dengan informasi itu di mana sajakah Kwik berada saat memberi kabar? Tuliskan semua kemungkinannya secara urut secara alfabet, dipisahkan oleh tanda koma dan tanpa spasi. Apabila tidak ada, tuliskan "Nihil" (tanpa tanda petik).

Sebuah robot condong ke kanan akan menelusuri suatu maze sebagai berikut: ia akan berjalan menyusuri jalan dan akan selalu belok ke kanan kapan saja itu memungkinkan. Gambar di samping ini menunjukkan contoh bagaimana robot itu akan berjalan di dalam maze contoh.

Dengan cara yang sama, tentukan maze-maze [A, B, C, D] yang robotnya dapat mencapai pintu keluar dari titik bulat.

Tuliskan jawaban dalam bentuk huruf-huruf dari maze secara terurut, dipisahkan tanda koma dan tanpa spasi. Misalnya semua benar, maka tuliskan A,B,C,D. Apabila tidak ada, tuliskan "Nihil" (tanpa tanda petik).

Bebek Kwek suka sekali berjalan mengunjungi para sahabatnya yang tinggal di kandang-kandang lain. Di ladang Pak Dengklek, ada 5 kandang: dua kandang ayam, dua kandang kelinci dan satu kandang kambing. Masing-masing penghuni menempati satu kandang.

Karena kondisi ladang maka:

• waktu berjalan Kwek dari kandang kambing ke kandang lainnya 3 menit

• waktu berjalan Kwek dari kandang ayam ke kandang kelinci dan sebaliknya adalah 2 menit

• waktu berjalan Kwek antara kedua kandang ayam, dan juga antara kedua kandang kelinci adalah 7 menit (agak memutar karena tidak nyaman kalau harus ketemu kambing tapi tidak mengunjungi).

Di setiap kandang, temannya selalu menyediakan biskuit-biskuit, yang satu kandang dengan kandang lain jenisnya berbeda: P, Q, R, S, dan T.

Suatu hari Kwek telah berjalan kesana kemari tapi ia tidak ingat kemana saja. Yang ia ingat, ia berturut-turut mendapatkan biskuit P, Q, S, R, T, R, P. Satu hal lagi, total waktu dalam perjalanannya (waktu bercakap-cakap tidak dihitung) adalah minimum. Biskuit apa yang diberikan kambing kepadanya kalau itu bukan P maupun T?

Berapa kalikah fungsi printgraf akan dipanggil apabila n = 6 (termasuk pemanggilan di main program)?

Berapa nilai n minimum agar banyaknya "*" yang dicetak ≥ 2019?

Diberikan Input dan Output sebuah program sebagai berikut:

*

**
 *

***
 **
  *

*****
 ****
  ***
   **
    *

Dan beberapa potongan kode sebagai berikut:

A. var i, j;
   for i := 1 to N do
   begin
     for j := 1 to i do write(" ");
     for j := i to N do write("*");
     writeln;
   end;

B. var i, j;
   for i := 1 to N do
   begin
     for j := N downto i do write("*");
     for j := 1 to i do write(" ");
     writeln;
   end;

C. var i, j;
   for i := 1 to N do
   begin
     for j := 1 to i - 1 do write(" ");
     for j := i to N do write("*");
     writeln;
   end;

D. var i, j;
   for i := 1 to N do
   begin
     for j := 1 to i do write(" ");
     for j := i+1 to N do write("*");
     writeln;
   end;

Mana sajakah fungsi yang menghasilkan output di atas? Apabila lebih dari satu jawaban, tuliskan semua, dan dipisahkan dengan tanda koma dan tanpa spasi. Sebagai contoh, apabila jawabannya adalah A, C, dan D, maka ditulis "A,C,D" (tanpa tanda petik)

Apabila input n adalah 10, tuliskan 2 angka pertama dan 2 angka terakhir yang dicetak secara berurutan. Tuliskan angka-angka dipisahkan oleh tanda koma. Sebagai contoh, Apabila 2 angka pertama = [1, 2] dan 2 angka terakhir = [3, 4], maka tulis jawaban anda "1,2,3,4" (tanpa spasi dan tanpa tanda petik).

Apabila input n adalah 500, tuliskan 5 angka pertama dan 5 angka terakhir yang dicetak secara berurutan. Tuliskan angka-angka seperti format jawaban soal sebelumnya.

FIBONACCI

Pak Dengklek sangat suka dengan bilangan Fibonacci, yaitu bilangan yang dibentuk dengan rumus:

• Fibonacci(0) = 0
• Fibonacci(1) = 1
• Fibonacci(n) = Fibonacci(n-1) + Fibonacci(n-2), untuk n > 1

Karena Pak Dengklek senang bermain, ia memutuskan untuk membuat tebak-tebakan ke bebeknya dengan aturan sebagai berikut: ia akan bertanya sebanyak Q kali. Untuk setiap pertanyaan, ia akan mengatakan sebuah bilangan bulat positif N. Sang bebek harus menjawab bilangan fibonacci ke-N. Karena nilainya dapat sangat besar, maka program anda cukup memberikan hasil modulo bilangan tersebut dengan 10⁹ + 7. Bantulah sang bebek membuat program yang menjawab pertanyaan anehnya itu!

Format Masukan:
Baris pertama berisi sebuah bilangan bulat Q, banyaknya pertanyaan Pak Dengklek.
Q baris berikutnya masing-masing berisi sebuah bilangan N.

Format Keluaran:
Q baris, baris ke-i berisi jawaban dari pertanyaan ke-i.

Batasan:

• 1 ≤ Q ≤ 100.000
• 0 ≤ N ≤ 100.000

Contoh Masukan dan Keluaran:

3
10
3
7

55
2
13

5
11
15
8
4
9

89
610
21
3
34

UKURAN SEGMEN

Pak Dengklek memiliki N buah titik dan ingin membentuk suatu himpunan garis penghubung dua buah titik yang valid. Sebuah himpunan garis dikatakan valid apabila semua garis di dalamnya memiliki gradien yang sama. Setiap titik dapat menjadi bagian dari satu atau lebih garis. Apabila dua buah garis tersebut berimpit, maka dua garis tersebut dihitung sebagai 2 garis yang berbeda. Karena jumlah titik sangat banyak, pak Dengklek tidak dapat menghitungnya satu-persatu. Pak Dengklek meminta bantuan kalian peserta OSP Informatika 2019 untuk membuat program yang dapat mengeluarkan ukuran maksimum garis valid!

Format Masukan:
Baris pertama berisi sebuah bilangan bulat N.
N baris berikutnya masing-masing berisi 2 bilangan bulat x_i dan y_i, menandakan koordinat titik ke-i.

Format Keluaran:
Sebuah bilangan berisi banyaknya elemen maksimum dalam semua himpunan garis valid.

Batasan:

• 3 ≤ N ≤ 2.500
• -100 ≤ x_i, y_i ≤ 100.
• Tidak ada 2 titik dengan koordinat yang sama.

Contoh Masukan dan Keluaran:

6
2 -2
2 2
0 -2
6 2
4 -2
4 2

6

10
1 -1
1 1
2 -1
3 1
-1 -1
0 1
0 -2
0 -3
3 -1
2 -3

10

PERHATIAN: Karena gradien dapat bernilai real (memiliki angka belakang koma), maka suatu gradien dianggap sama dengan gradien lainnya apabila perbedaan gradien tersebut lebih kecil atau sama dengan 10^-9.