محدودیت زمان: ۱ ثانیه محدودیت حافظه: ۲۵۶ مگابایت شرکت beeptunes، در حال راهاندازی یک…
- User
محدودیت زمان: ۱ ثانیه محدودیت حافظه: ۲۵۶ مگابایت شرکت beeptunes، در حال راهاندازی یک سیستم هوش مصنوعی برای پیشنهاد موسیقی به کاربرهاست. اکنون بخش هوش این سیستم به انتها رسیده، اما هنوز رابط درستی بین دادههای موجود و بخش هوش سیستم وجود ندارد!
دو نوع داده جهت سیستم پیشنهاد موسیقی قابل استفاده است:
دادههای مربوط به هر کاربر. این دادهها شامل نام کاربری، سن، شهر و لیست نام آلبومهاییست که این کاربر خریداری کرده است. دادههای مربوط به هر آلبوم. ایندادهها شامل نام آلبوم، نام خواننده، سبک و تعداد ترکهای موسیقی این آلبوم هستند. برای این سیستم هوش مصنوعی، خود این دادهها بصورت خام اهمیتی ندارند. این سیستم دادهها را بطور خاصی درخواست میکند و باید آنها را در اختیارش قرار دهیم. درخواستها به صورتهای زیر ممکن است باشند:
درخواست تعداد آهنگهایی که یک کاربر از یک خواننده خریدهاست. درخواست تعداد آهنگهایی که یک کاربر از یک سبک خریدهاست. درخواست تعداد آهنگهایی که کاربرهای با یک سن خاص، از یک خواننده خریدهاند. درخواست تعداد آهنگهایی که کاربرهای با یک سن خاص، از یک سبک خریدهاند. درخواست تعداد آهنگهایی که کاربرهای با یک شهر خاص، از یک خواننده خریدهاند. درخواست تعداد آهنگهایی که کاربرهای با یک شهر خاص، از یک سبک خریدهاند. البته این سیستم خیلی هم باهوش نیست و ممکن است در سوالهایی که میپرسد نام کاربری، یا نام خواننده و یا هریک از فیلدهای مسئله اشتباه باشد و واقعاً در بین دادههای سایت موجود نباشد.
حال به سراغ شما آمدهایم تا این رابط را برای ما بنویسید! برنامهای بنویسید که دادههای شرکت را بصورت Yaml دریافت کند، سپس به درخواستهای از انواع مختلف پاسخ بدهد.
برای آشنایی با فرمت Yaml میتوانید به مثالهای سوال (و البته اینترنت!) مراجعه کنید. دقت کنید که ورودیهای این سوال حالت خاص و بسیار سادهای از Yaml میباشد.
ورودی در خط اول ورودی عدد n n آمدهاست که نمایانگر تعداد دادههای از نوع کاربر است. سپس این n n داده بصورت Yaml میآیند.
پس از آن، در خط بعدی عدد m m آمدهاست که نمایانگر تعداد دادههای از نوع آلبوم است. سپس این m m داده بصورت Yaml میآیند.
در این Yamlها، فیلدهای نام کاربری، سن، شهر و لیست آلبومها برای هر کاربر به همین ترتیب میآیند و با کلیدهای زیر مشخص میشوند:
name age city albums همچنین فیلدهای نام آلبوم، نام خواننده، سبک و تعداد ترکهای یک آلبوم به همین ترتیب میآیند و با کلیدهای زیر مشخص میشوند:
name singer genre tracks در فیلدهای age و tracks حتماً یک عدد بین ۱ تا ۳۰ میآید و در دیگر فیلدها رشتههای متشکل از حداکثر ۱۰ کاراکتر از حروف کوچک انگلیسی میآید.
و فرمت اعداد و رشتهها و فواصل، دقیقاً به شکل ورودیهای نمونه خواهد بود. هر تب نیز با ۲ تا فاصله (space) مشخص میشود.
سپس در خط بعدی عدد q q آمده است که نمایانگر تعداد درخواستهایی است که برنامه شما باید به آنها پاسخ دهد. سپس در هریک از q q سطر بعدی، ابتدا شماره نوع درخواست و سپس توضیح آن میآید که به یکی از ۶ شکل زیر است:
1 user singer 2 user genre 3 age singer 4 age genre 5 city singer 6 city genre دقت کنید که ممکن است هریک از اطلاعات داخل پرسشها (از قبیل نام کاربر، نام خواننده، ...) در ورودی موجود نباشد.
1 ≤ n , m , q ≤ 100 1≤n,m,q≤100
تضمین میشود که نامهای کاربری و نام آلبومها، متفاوت هستند. همچنین تضمین میشود تمامی نامهای آلبومهای خریده شده توسط کاربرها درست هستند و چنین آلبومهایی وجود دارند. همچنین تمامی رشتههای موجود در دادهها از حروف کوچک انگلیسی تشکیل شدهاند و بین ۱ تا ۱۰ کاراکتر دارند. و تمامی اعداد موجود در دادهها بین ۱ تا ۳۰ هستند.
تضمین میشود که آلبومها و کاربرهای مختلف، نامهای مختلف دارند. همچنین هیچیک از کلیدهای توضیحی (مانند name و albums و ...) بعنوان نام کاربر، آلبوم، خواننده، سبک و یا شهر در ورودی نمیآیند.
خروجی به ازای هر درخواست، برنامهی شما باید یک عدد خروجی دهد که برابر با پاسخ آن درخواست است.
مثال ورودی نمونه ۱ 1
- name: ali
age: 12
city: bushehr
albums:
- bidad
- blaze 2
- name: bidad singer: shajarian genre: classic tracks: 10
- name: blaze singer: ghorbani genre: pop tracks: 9 1 1 ali ghorbani
Plain text خروجی نمونه ۱ 9 Plain text ورودی نمونه ۲ 2
- name: gholi
age: 18
city: tehran
albums:
- tekunbede
- barf
- hoyad
- name: mehdi
age: 20
city: mashhad
albums:
- eclipse
- barf
- hoyad 4
- name: eclipse singer: malmsteen genre: classic tracks: 10
- name: barf singer: beeptunes genre: pop tracks: 22
- name: tekunbede singer: beeptunes genre: pop tracks: 14
- name: hoyad singer: hoyad genre: persian tracks: 5 12 1 gholi hoyad 1 gholi beeptunes 2 gholi rock 2 mehdi pop 3 20 beeptunes 4 18 malmsteen 4 19 malmsteen 5 tehran malmsteen 5 mashhad malmsteen 6 tehran pop 6 ghazvin rock 1 mehdi shajarian
Plain text خروجی نمونه ۲ 5 36 0 22 22 0 0 0 10 36 0 0 write in java
- name: ali
age: 12
city: bushehr
albums:
- Assistant
To solve this problem, you'll need to parse simplified YAML input, process the data into appropriate data structures, handle queries, and output the results. Since the data format and queries are specified, here's how you might approach writing this program in Java:
1. Data Representation
Users:
Each user has the following attributes:
name(String)age(int)city(String)albums(List of Strings)
Albums:
Each album has the following attributes:
name(String)singer(String)genre(String)tracks(int)
2. Parsing the Input
Since the input is in a simplified YAML format, you'll need to read the input line by line and parse it accordingly. Here's how you might approach parsing:
- Identify the indentation level (number of leading spaces): This will help you understand the hierarchy of the data.
- Use state machines or flags to keep track of which part of the data you're parsing (e.g., whether you're parsing users or albums).
- Store the key-value pairs as you parse them.
3. Storing the Data
Use appropriate data structures to store the parsed data:
- HashMaps: For quick lookups by names (e.g., users by name, albums by name).
- Classes or Objects: Create classes for Users and Albums to encapsulate their attributes.
4. Handling the Queries
There are six types of queries, each requiring you to compute the total number of tracks based on certain criteria. Here's how you can handle each:
-
Query Type 1: Number of tracks a user has purchased from a specific singer.
- Find the user by name.
- For each album the user has purchased, check if the singer matches.
- Sum up the tracks.
-
Query Type 2: Number of tracks a user has purchased from a specific genre.
- Similar to Query Type 1 but match on genre.
-
Query Type 3: Total number of tracks purchased by all users of a certain age from a specific singer.
- Find all users matching the age.
- For each user, check their albums for the singer.
- Sum up the tracks.
-
Query Type 4: Total number of tracks purchased by all users of a certain age from a specific genre.
- Similar to Query Type 3 but match on genre.
-
Query Type 5: Total number of tracks purchased by all users from a specific city from a specific singer.
- Find all users from the city.
- For each user, check their albums for the singer.
- Sum up the tracks.
-
Query Type 6: Total number of tracks purchased by all users from a specific city from a specific genre.
- Similar to Query Type 5 but match on genre.
Note: In case any of the data (like user name, singer, genre) doesn't exist in the database, the query should return
0.5. Edge Cases and Validation
- Non-existent Data: If a query references a user, singer, genre, age, or city that doesn't exist, return
0. - Data Consistency: Ensure that album purchases by users reference existing albums.
- Data Types: Be mindful of data types (e.g., ages and track numbers are integers).
6. Sample Workflow
Here's a step-by-step guide for handling a query:
- Read the query input and parse it into its components.
- Validate the components: Check if the user, singer, genre, age, or city exists in your data.
- Process the query based on its type:
- For user-based queries (Type 1 and 2), retrieve the user and their albums.
- For age or city-based queries (Type 3 to 6), filter users by age or city, then process their albums.
- Iterate through the relevant albums:
- For each album, check if it matches the singer or genre criteria.
- Sum up the
tracksattribute of matching albums.
- Output the result.
7. Efficient Implementation
- Use Maps for Quick Access: HashMaps (or Maps) can significantly speed up data retrieval based on keys like names.
- Avoid Redundant Computations: Cache results if the same computations are likely to occur multiple times.
- Optimize Loops: When processing users or albums, minimize nested loops where possible.
8. Testing
- Use the Sample Inputs: Test your program with the sample inputs provided to ensure it produces the correct outputs.
- Edge Cases: Create additional test cases to cover possible edge cases, such as empty data, non-existent references, or maximum allowed input sizes.
9. Time and Memory Constraints
- Time Limit: 1 second.
- Memory Limit: 256 MB.
- Optimization: Ensure your program reads input efficiently and doesn't use excessive memory. Using buffered input methods and avoiding unnecessary data storage can help meet these constraints.
Conclusion
By carefully parsing the input data, organizing it into appropriate data structures, and methodically processing each query according to its type, you can implement the required functionality.
Reminder: Pay close attention to the input format and ensure your parsing logic aligns with it. Handling the intricacies of the simplified YAML format is crucial for the correctness of your program.
Good luck with your implementation!