Задача Списки

Правила проведения олимпиады, условия задач и комментарии к ним, результаты олимпиады и апелляции.
Руководители: к.ф-м.н, профессор Пирогов В.Ю,, к.п.н, доцент Слинкин Д.А,

Модераторы: xdsl, Vladislav_133

Задача Списки

Сообщение Vladislav_133 15 мар 2017, 10:41

Разбор задачи "Списки" здесь
Аватара пользователя
Vladislav_133
Elite
 
Сообщения: 1386
Зарегистрирован: 13 дек 2008, 18:08
Полное имя: П.В.Ю.

Re: Задача Списки

Сообщение Vladislav_133 29 мар 2017, 19:17

Честно говоря эта задача самая простая. Я бы ее и олимпиадной не назвал. Нет олимпиадной "фишки".
Есть два списка чисел, нужно их сравнить.
Приведу основной фрагмент.

Подсветка синтаксиса: [ Загрузить ] [ Скрыть ]
Подсветка синтаксиса языка cpp
    for(i=0; i<n; i++){
        for(j=0; j<n; j++){
            if(b1[j])continue;
            if(a[i]==b[j]){
                b1[j]=1;
                break;
            }
        }
        if(j==n){
            printf("No\n");
            return 1;
        }
    }    
    printf("Yes\n");
 


Сравниваются массивы a и b. Массив b1 служит для того, чтобы повторно не проверять один и тот же элемент.
Вот, собственно, и все. Нет никаких изысков.
p.s.
В заключении скажу несколько слов о массивах.
В программировании часто приходится их использовать, если много входных параметров.
Всегда есть вопрос: достаточно ли места в массиве. В олимпиадных задачах обычно указываются
предельные значения для входных данных. В этом случае можно использовать статические массивы, зарезервировав для них память.
Это быстрее, чем выделять память для каждого считанного элемента. Для выделения памяти для каждого элемента
на языке C, на котором я пишу, конечно, требуется знание некоторой техники. Но в современных языках таких, например, как C#
массивы и так динамические. Вот и все, что в рамках разбора данной задачи хотел сказать.
Аватара пользователя
Vladislav_133
Elite
 
Сообщения: 1386
Зарегистрирован: 13 дек 2008, 18:08
Полное имя: П.В.Ю.

Re: Задача Списки

Сообщение ddzet 31 мар 2017, 13:01

Пытался разобраться в Вашем решении этой задачи, но не понял, какие конкретно элементы хранит массив b1?
ddzet
 
Сообщения: 12
Зарегистрирован: 11 мар 2017, 13:36
Полное имя: Глеб

Re: Задача Списки

Сообщение Vladislav_133 06 апр 2017, 11:04

В массиве b1 хранится "карта" проверенных элементов списка.
Для чего это надо?
Чтобы учесть одинаковые элементы.
Рассмотрим два списка.
Первый
1 2 3 4 5 5
Второй
5 1 2 3 4 4
Как их сравнить. Если не отмечать элементы, которые уже сравнил, то получится, что списки равны.
Аватара пользователя
Vladislav_133
Elite
 
Сообщения: 1386
Зарегистрирован: 13 дек 2008, 18:08
Полное имя: П.В.Ю.

Re: Задача Списки

Сообщение [DD] 12 апр 2017, 14:57

Знаю, что поздно но все же решил немного порешать задачки.
Код как и в прошлом году будет писаться на Rust.
Подсветка синтаксиса: (main.rs) [ Загрузить ] [ Скрыть ]
Подсветка синтаксиса языка php
  1. use std::fs::File;
  2. use std::io::{Read, Write};
  3.  
  4. /**
  5. * функция чтения очередной строки из файла(для простоты сразу возвращает без знаковое целое)
  6. */
  7. fn read_line(input:&mut File) -> u32{
  8.     let mut buf = [0u8;1];
  9.     let mut result:Vec<u8> = Vec::new();
  10.     loop {
  11.         let cnt = match input.read(&mut buf) {
  12.             Err(_) => 0,
  13.             Ok(l) => l
  14.         };
  15.         if buf[0] == 27 || buf[0] == 10 || cnt == 0{
  16.             break;
  17.         }
  18.        
  19.         result.push(buf[0]);
  20.     }
  21.     match String::from_utf8(result) {
  22.         Ok(string) => string.trim().parse::<u32>().unwrap(),
  23.         Err(e) => panic!("{}", e)
  24.     }
  25. }
  26.  
  27.  
  28. fn main() {
  29.     let mut input = match File::open("input.txt") {
  30.         Ok(f) => f,
  31.         Err(e) => panic!("{}", e)
  32.     };
  33.     let mut output = match File::create("output.txt") {
  34.         Ok(f) => f,
  35.         Err(e) => panic!("{}", e)
  36.     };
  37.     let first_cnt = read_line(&mut input);
  38.     let mut list:Vec<u32> = vec![];
  39.     for _ in 0..first_cnt {
  40.         list.push(read_line(&mut input));
  41.     }
  42.     let second_count = read_line(&mut input);
  43.     if second_count != first_cnt {
  44.         output.write(b"No").unwrap();
  45.         return ;
  46.     }
  47.     for _ in 0..second_count {
  48.         let name = read_line(&mut input);
  49.         match list.binary_search(&name) {
  50.             Ok(index) => {list.remove(index);},
  51.             Err(_) => {
  52.                 output.write(b"No").unwrap();
  53.                 return ;
  54.             }
  55.         }
  56.     }
  57.     output.write(b"Yes").unwrap();
  58. }
  59.  
мы рождены чтоб сказку сделать кодом
[DD]
Elite
 
Сообщения: 163
Зарегистрирован: 18 мар 2009, 22:18
Откуда: from HELL
Полное имя: Зыков Д.А.

Re: Задача Списки

Сообщение Vladislav_133 13 апр 2017, 09:33

Не поздно.
Хорошо бы еще с языком разобраться.
Аватара пользователя
Vladislav_133
Elite
 
Сообщения: 1386
Зарегистрирован: 13 дек 2008, 18:08
Полное имя: П.В.Ю.

Re: Задача Списки

Сообщение [DD] 13 апр 2017, 11:36

Язык очень интересный, но не смотря на то, что я с ним работаю уже года два обычно уходит много времени на борьбу с компилятором)
мы рождены чтоб сказку сделать кодом
[DD]
Elite
 
Сообщения: 163
Зарегистрирован: 18 мар 2009, 22:18
Откуда: from HELL
Полное имя: Зыков Д.А.

Re: Задача Списки

Сообщение Vladislav_133 14 апр 2017, 12:26

Спасибо. Хотелось бы вникнуть в этот язык. Времени на все не хватает.
Аватара пользователя
Vladislav_133
Elite
 
Сообщения: 1386
Зарегистрирован: 13 дек 2008, 18:08
Полное имя: П.В.Ю.


Вернуться в Олимпиада по программированию

Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 1

cron