Presentasi hadiah kepada para peserta trek backend
Kami sedang menyelesaikan serangkaian analisis kejuaraan pemrograman kedua. Dalam beberapa minggu terakhir, kami telah menerbitkan analisis tiga lagu: ML, tampilan depan dan pengembangan seluler. Masih mengurai trek di backend. Ternyata menjadi yang paling populer: 2682 orang mengambil bagian dalam kualifikasi, 320 dari mereka mencapai final. Tugas untuk pengembang backend diciptakan oleh tim Yandex.Taxi.
Kode promosi Mars
Penulis: Maxim PedchenkoEnam bulan telah berlalu sejak peluncuran Yandex.Taxi di Mars. Menjelang Tahun Baru Mars, Yandex.Taxi memutuskan untuk memberikan kode promosi kepada orang-orang Mars. Tetapi ternyata Mars tidak dapat menggunakan kode promo Earth, karena server di Mars tidak berfungsi sesuai dengan aturan Earth. Oleh karena itu, Yandex.Taxi datang dengan kode promosi Mars khusus.
Kode promosi Mars dihasilkan sebagai berikut:
- Kunci enkripsi dibuat.
- Kunci enkripsi dibagi menjadi substring dengan panjang acak.
- Dari semua substring, substring dengan panjang L dipilih.
- Substring yang dipilih dicampur dan digabung.
- Hasil penggabungan adalah kode promosi.
Tantangan:
Penting untuk memeriksa apakah kode promosi yang dimasukkan valid. Jika kode promosi itu valid, Anda perlu mencetak "YA". Jika tidak valid, "TIDAK".
Format, Contoh, dan Catatan I / OFormat input
<panjang kode promosi>
<kode promosi>
<panjang kunci>
<kunci>
<panjang substring L>
Format output
Validitas kode promosi: YA atau TIDAK.
Contoh 1
Contoh 2
Contoh 3
Catatan
Panjang L> 1.
Alfabet kode promosi [AZ, 0-9].
Panjang kode promosi ada dalam kisaran [6, 30].
Panjang kunci dalam kisaran [6, 30].
Panjang Substring L <panjang kunci.
Panjang kode promosi adalah kelipatan dari L.
Solusi
Kita perlu mempertimbangkan semua kemungkinan partisi kunci enkripsi ke dalam substring dengan panjang L dan memeriksa apakah kode promo ini dapat terdiri dari kemungkinan partisi.
Petunjuk tersembunyi di catatan kondisi:
Panjang kode promosi ada dalam kisaran [6, 30].
Panjang kunci dalam kisaran [6, 30].
Pembatasan kecil menunjukkan bahwa solusi yang efektif tidak diperlukan, yang berarti bahwa Anda tidak perlu menghabiskan waktu mencari pengoptimalan - lebih baik untuk menyelesaikan masalah secara langsung.
Situasi ini adalah tipikal dari pengembangan backend produk. Seringkali ada situasi di mana Anda dapat menghabiskan berminggu-minggu pada algoritma optimal, tetapi jika Anda mempertimbangkan batasannya, menjadi jelas bahwa lebih baik menggunakan solusi yang cepat dan bukan yang paling optimal.
Jadi, kita akan mempertimbangkan baris dengan kode promosi sebagai urutan substring S dengan panjang L. Untuk setiap substring S kita menemukan semua substring
Sk sama dengan itu dari kunci enkripsi. Untuk setiap S
k, ingat penggunaannya, beralih ke substring S berikutnya dan ulangi algoritma.
Jika untuk substring S tidak mungkin untuk menemukan S
k yang tidak digunakan, perlu untuk mencoba varian pembelahan lain, jika tidak ada varian lain, maka kode promosi tidak valid.
Jika S
k ditemukan setidaknya untuk satu kasus untuk setiap S, maka kode promosi valid.
Optimasi Sistem Transportasi Mars
Penulis: Dmitry Polishchuk dan Anton ToduaItu adalah tahun 2058. Koloni-koloni pemukim pertama sudah mendarat di Mars dan mulai menghuninya, dan Yandex.Taxi mulai menyebarkan sistem stasiun antar-jemput.
Untuk operasi normal, stasiun ulang-alik membutuhkan catu daya yang konstan dari jaringan energi. Untuk menyalakan stasiun, Anda harus membangun generator energi nuklir uranium di dalam stasiun itu sendiri, atau meletakkan kabel ke stasiun pesawat ulang-alik lain (yang sudah bertenaga). Biaya membangun generator di dalam stasiun antar-jemput yang berbeda dapat bervariasi. Rute kabel antara stasiun antar-jemput juga bervariasi dalam biaya dan tidak selalu memungkinkan. Koneksi kabel bersifat dua arah.
Tugasnya adalah mengatur daya yang efisien (dengan biaya minimal) ke semua stasiun shuttle.
Di pintu masuk, program menerima jumlah total stasiun ulang-alik, biaya pembuatan generator untuk setiap stasiun ulang-alik dan deskripsi dari semua kabel yang mungkin antara stasiun antar-jemput (jumlah stasiun yang terhubung dan biaya pemasangan kabel).
Format, Contoh, dan Catatan I / OFormat input
Baris pertama berisi satu nomor stasiun antar-jemput non-negatif N ≤ 1000.
Baris kedua berisi nomor N yang menentukan biaya pembuatan generator di dalam stasiun yang sesuai.
Jalur ketiga berisi jumlah kabel non-negatif tunggal K ≤ 100000 antar stasiun antar-jemput.
Baris K berikutnya (mulai dari yang keempat) berisi deskripsi satu kabel - tiga bilangan bulat non-negatif:
jumlah stasiun pertama ,
jumlah stasiun kedua dan
biaya pelaksanaan .
Format output
Satu integer adalah biaya daya minimum untuk semua stasiun shuttle untuk konfigurasi yang diberikan.
Contoh 1
Contoh 2
Catatan
Stasiun diberi nomor dari satu.
Angka-angka di dalam garis dipisahkan oleh satu ruang.
Kebenaran data input tidak perlu diperiksa.
Solusi
Pertama, ada baiknya beralih dari deskripsi yang indah ke grafik tertimbang yang tidak diarahkan, di mana akan ada puncak di tempat stasiun antar-jemput, kabel akan menjadi pinggiran, dan biaya membangun kabel akan berubah menjadi bobot dari tepi yang sesuai. Tetapi pertanyaannya tetap - bagaimana memperhitungkan biaya membangun generator uranium di dalam stasiun (puncak) sendiri? Jawaban atas pertanyaan ini adalah inti dari masalahnya.
Misalkan ada simpul lain - sumber energi, dan ujung ditarik dari simpul ini ke masing-masing simpul grafik dengan bobot yang sama dengan biaya membangun generator uranium di stasiun yang sesuai (simpul). Asumsi ini membawa kita ke grafik terhubung yang perlu diubah menjadi pohon sehingga jumlah bobot tepi di dalamnya ternyata menjadi sekecil mungkin. Ini tidak lebih dari masalah menemukan pohon spanning minimum dalam grafik. Anda dapat membangun pohon rentang minimum menggunakan salah satu algoritma yang dikenal - misalnya, Prima atau Kraskal.
Kode sampel dengan komentar #include <algorithm> #include <iostream> #include <tuple> #include <vector> using Price = std::size_t; using Vertex = std::size_t; using Transition = std::tuple<Price, Vertex, Vertex>; using Graph = std::vector<Transition>; // ( ). class Equals { public: // . explicit Equals(std::size_t size) { equals_.resize(size); // . for (std::size_t i = 0; i < size; i++) { equals_[i] = i; } } // v1 v2 true, // . bool Emplace(std::size_t v1, std::size_t v2) { while (v1 != v2) { if (v2 < v1) { std::swap(v1, v2); } auto& next_v2 = equals_[v2]; if (next_v2 == v2) { next_v2 = v1; return true; } v2 = next_v2; } return false; } private: std::vector<size_t> equals_; }; int main() { // . std::size_t vertex_count = 0; std::cin >> vertex_count; if (vertex_count == 0) { std::cout << 0 << std::endl; return 0; } // — — . vertex_count++; // . Graph graph; graph.reserve(vertex_count); // . for (Vertex i = 1; i < vertex_count; i++) { Price price = 0; std::cin >> price; graph.emplace_back(price, 0, i); } // . std::size_t edge_count = 0; std::cin >> edge_count; for (std::size_t i = 0; i < edge_count; i++) { Price price = 0; Vertex from = 0, to = 0; std::cin >> from >> to >> price; graph.emplace_back(price, from, to); } // . std::sort(graph.begin(), graph.end()); // . // https://ru.wikipedia.org/wiki/_ Price result = 0; Equals equals{vertex_count}; for (const auto& [price, from, to] : graph) { if (equals.Emplace(from, to)) { result += price; } } // . std::cout << result << std::endl; return 0; }
Tidak ada parkir
Penulis: Ilya Mescherin dan Artyom SerebriyskyDi satu kota, mobil dilarang berhenti, kecuali menaiki penumpang. Dan penumpang tidak setuju untuk menunggu lebih dari 3 menit. Di kota ini, seorang pejalan kaki memesan taksi ke titik X dan menunjukkan selang waktu 180 detik. Pengemudi harus tiba tepat pada interval ini. Jika Anda tiba lebih awal, Anda tidak akan dapat mengharapkan penumpang. Jika Anda datang terlambat, penumpang yang marah akan membatalkan pesanan.
Karena pembatasan tersebut, hanya driver Z yang tersisa di kota ini, yang masing-masing di awal tugas berada di bagian atas grafik lalu lintas. Sistem kontrol harus menunjuk driver terbaik dari mereka yang berhasil tiba pada interval yang ditentukan. Pengemudi terbaik adalah orang yang datang untuk memesan sedekat mungkin dengan awal interval. Jika ada beberapa driver seperti itu, maka salah satunya.
Penting bagi setiap pengemudi untuk menentukan apakah ia memiliki waktu untuk tiba pada interval yang ditunjukkan, dan jika demikian, pada titik waktu paling awal pada interval yang ditunjukkan, ia dapat tiba.
Deskripsi formalDiberikan:
- Grafik berorientasi G dengan simpul N dan tepi K, simpul diberi nomor dari 0 hingga N - 1, 0 ≤ N ≤ 10 4 , 0 ≤ K ≤ 10 4 . Setiap tepi sesuai dengan waktu tempuh di dalamnya - bilangan bulat W, 10 ≤ W ≤ 10 4 .
- Memesan posisi pada kolom target ID.
- Posisi Z driver dalam kolom IDsource 2 , 1 ≤ Z ≤ 10 4 .
- Waktu t 0 , 0 ≤ t 0 ≤ 600 adalah bilangan bulat.
Sangat penting bagi setiap pengemudi untuk menemukan sedemikian rupa sehingga:
- ada rute dari driver IDsource z ke ID target sehingga pengemudi tiba pada t min ,
- t min ∈ [t 0 ; t 0 + 180],
- dan ini adalah t min awal yang mungkin: t min ≤ t i untuk setiap t i poin memuaskan 1 dan 2
- atau pastikan t min seperti itu tidak ada.
Format, Contoh, dan Catatan I / OFormat input
Grafik diatur dalam bentuk tiga kali lipat triples-top-end-end-time-triples.
Input data, setiap item pada barisnya sendiri:
1. K adalah jumlah tepi.
2. K tiga kali lipat ID ID Weight - titik awal dari tulang rusuk, titik akhir dari tulang rusuk, seberapa banyak mobil menggerakkan tulang rusuk.
3.
Target ID t
0 - di atas urutan [spasi] awal rentang ketika Anda harus tiba.
4. Z - jumlah driver.
5. (Z kali) ID
z adalah bagian atas driver berikutnya.
Format output
Untuk setiap driver, dengan urutan yang sama seperti yang mereka masukkan, cetak pada baris terpisah t
min yang dihitung atau –1 jika t
min tersebut tidak ada.
Contoh 1
Contoh 2
Contoh 3
Catatan
1. Beberapa tepi dapat berubah dari titik A ke titik B, termasuk yang memiliki bobot yang sama.
2. Iga dari A ke A diperbolehkan.
3. Keberadaan tepi (A-> B) dan (B-> A) pada saat yang sama (siklus panjang 2) diperbolehkan.
Solusi
Pengemudi tunggalPertama, kami akan menganalisis kasus sederhana dengan satu driver. Ukuran tulang rusuk adalah waktu [bepergian di atasnya], batasan finish dinyatakan dalam unit yang sama, sehingga kita dapat merumuskan kembali masalah: “Pengemudi bergerak dari titik A ke titik B sesuai dengan grafik. Temukan jalur minimum sedemikian sehingga panjangnya terletak di segmen [T, U]. "
Cara termudah untuk melakukan ini adalah menjalankan dijkstra yang dimodifikasi dari A ke B:
- Modifikasi 1. Misalkan kita mendapat bagian atas dari minQ dan sudah ditandai hitam (yaitu, jarak minimum untuk itu telah ditemukan). Maka kita tidak mengabaikannya, tetapi memprosesnya dengan cara standar - letakkan semua simpul yang berdekatan dengan jarak baru kembali ke minQ.
- Kami berhenti hanya ketika jarak ke minQ saat ini secara ketat lebih besar dari U.
- Misalkan kita menemukan puncak B selama lintasan traversal, maka jika jarak saat ini ≥ T, ingatlah itu sebagai jawaban R. Pada titik ini, dijkstra juga dapat terganggu.
Jadi, jika kita memiliki R, ini adalah jalur minimum dengan panjang dalam interval yang diperlukan.
Banyak pengemudiSolusi untuk dahi adalah menjalankan algoritma untuk setiap driver. Tetapi solusi seperti itu tidak berlalu dengan membatasi waktu. Kita harus belajar memberikan jawaban untuk setiap driver untuk O (1).
Untuk melakukan ini, kami memodifikasi algoritma untuk satu driver:
- Alih-alih dijkstra dari pengemudi ke titik pesanan, kami memulai dijkstra dari titik pesanan sesuai dengan grafik dengan Tepi terbalik (!).
- Kami mengambil keuntungan dari kenyataan bahwa jumlah simpul juga dibatasi hingga sepuluh ribu. Mari kita mendapatkan array jawaban R - untuk setiap titik ini adalah waktu minimum dalam rentang [T, U] ketika dapat dicapai dari A.
- Dalam proses melintasi grafik dari dijkstroy yang dimodifikasi, ketika kita memenuhi titik j dan jika jarak saat ini ke dalam interval yang diinginkan [T, U], kita masukkan R: R j = min (R j , dist).
Kemudian, untuk setiap driver di vertex J, seseorang dapat meminta R
j untuk mengetahui apakah ada jalur yang memenuhi kondisi dan berapa panjangnya.
Optimasi minQPanjang jalur selalu bilangan bulat dan terbatas pada 781 dari atas - untuk pesanan yang dilakukan pada t
0 = 600, detik terakhir yang sah dari kedatangan pengemudi adalah 780. Dalam hal ini, untuk mengimplementasikan dijkstra, Anda perlu menggunakan implementasi minQ berikut.
Kami memiliki array Fringe dengan ukuran [781]. Di setiap elemen Fringe
i ada unordered_set yang menyimpan id dari semua simpul yang ada lintasan panjang i.
1. Tambahkan simpul dengan jarak D:
fringe[D].insert(vertex);
2. Menurut kondisi, berat minimum tepi adalah> 0. Oleh karena itu, alih-alih mengambil elemen dari minQ satu per satu, Anda dapat melewati seluruh irisan:
for(int i = 0; i < fringe.size(); ++i) { if(fringe[i].empty()) { continue; } for(auto& vertex : fringe[i]) {
Kalkulator biaya perjalanan
Penulis: Nikolay FilchenkoPerlu untuk menghitung biaya perjalanan sesuai dengan formula yang diberikan. Setiap perjalanan ditandai dengan parameter integer K. Formula diberikan dalam notasi Polandia terbalik.
Operasi yang diizinkan:
- + - - penjumlahan dan pengurangan;
- * / - divisi perkalian dan integer;
- <= - perbandingan;
- ? - operator bersyarat. Jika argumen pertama benar - mengembalikan argumen kedua, sebaliknya - argumen ketiga.
Variabel [az] dan bilangan bulat dari -10
9 hingga 10
9 juga digunakan dalam rumus.
Kita dapat mengasumsikan bahwa hasil semua operasi dalam rumus tidak melebihi 10
9 dalam nilai absolut. Hasil operasi perbandingan hanya digunakan sebagai argumen kepada operator kondisional.
Format dan Contoh I / OFormat input
Pada baris pertama, satu angka 1 ≤ K ≤ 26 - jumlah variabel.
Baris kedua berisi rumus untuk menghitung harga (tidak lebih dari 3-10
4 elemen). Semua elemen dipisahkan oleh spasi.
Pada baris ketiga, 1 ≤ N ≤ 10
4 adalah jumlah tes.
Baris N berikutnya berisi bilangan bulat K masing-masing (–10
9 ≤ v ≤ 10
9 ) - nilai-nilai variabel dalam urutan abjad.
Format output
N baris yang mengandung satu bilangan bulat - hasil penggantian setiap set nilai. Dijamin bahwa hasil dari ekspresi terbatas dan ditentukan
Contoh 1
Contoh 2
Solusi
Ini adalah tugas untuk implementasi dan perhatian yang cermat. Ada dua poin utama dalam solusi:
- Ekspresi asli itu sendiri harus diubah menjadi array angka dan operasi agar tidak mem-parsing string ke dalam setiap set variabel.
- Harus diingat bahwa pembagian bilangan bulat dengan nol mengarah ke SIGFPE, jadi dalam operasi pembagian itu perlu dicek secara eksplisit bahwa penyebutnya bukan nol. Berdasarkan jaminan kehalusan dan kepastian hasil dari seluruh ekspresi, kita dapat memahami: hasil divisi tersebut tidak terlibat dalam hasil akhir dan berada di cabang yang tidak digunakan dari operator bersyarat, sehingga Anda dapat menerimanya dengan (misalnya, nol).
Habraposty pada topik: