Олимпиада 2013

Интересные алгоритмы, олимпиадные задачи, эффектные и эффективные решения. freepascal, delphi, c, c++, c#, java, javascript, perl, ruby, python, php, bash, wsh и т.д. Компиляторы, интерпретаторы, линкеры, отладчики, системы контроля версий и многое другое.

Модератор: xdsl

Олимпиада 2013

Сообщение Vladislav_133 01 апр 2013, 17:35

Очень странно, что опять на последней олимпиаде всплыл вопрос с пробелами. Он время от времени всплывает, но не так уж сильно, как на этот раз. У кого-то программа не работает, если в строке есть дополнительные пробелы в конце, у кого то, если между элементами в строке есть дополнительные пробелы. Кому-то надо чтобы в конце текстового файла была одна пустая строка, но не больше, кому-то требуется, чтобы после последней значащей строки шел сразу код конца файла. Это разнобой возник из непонимания сути проблемы. Многие участники, почему-то, взялись считывать всю строку, а потом писать процедуру разбора этой строки. Причем, зачастую процедура оказывалась не совершенной и в результате появляются ошибки, не относящиеся к сути олимпиады. Но дело в том, что в большинстве задач заранее известно, сколько параметров и какие (по типу) параметры находятся в каждой строке. Так что писать подобные процедуры и тратить драгоценное время абсолютно не стоит. Ну, если уж вам так хочется, заранее напишите такую процедуру, сделайте ее более-менее универсальной, а потом вставляйте ее во все ваши решения, чтобы сэкономить драгоценное время.
Второй вопрос, на котором хочется остановиться, это ввод и вывод информации. Обычно на олимпиадах подобного рода требуется написать программу, работающую с входными и выходными потоками. Все должно выглядеть примерно так. Пусть исполняемый модуль называется prog, тогда
Код: Выделить всё
Prog <in.txt >out.txt

И все. При этом имена входного и выходного файла нигде в самой программе не задается, а только в командной строке. Это очень удобно. Кроме того всегда можно вводить и выводит с консоли:
Код: Выделить всё
#ввод из файла, вывод на консоль
Prog <in.txt
#ввод с консоли, вывод файл
Prog >out.txt
#ввод и вывод с консоли
Prog
Реализуется этот механизм просто элементарно, гораздо проще того, который многие использовали.
И так приступаю к примерам.
Листинг 1. Обработка произвольного количества строковой информации (язык C)
Код: Выделить всё
#include <stdio.h>
int main() {
char s[1000];
while(gets(s)){
/*здесь выполняем какие либо действия с полученной строкой*/

/*выводим строку для контроля*/
puts(s);
    }
    return 0;
}

Листинг 2. Обработка произвольного количества строковой информации (язык C++)
Код: Выделить всё
#include <iostream>
using namespace std;
int main() {
char s[1000];
while(!cin.eof()){
cin.getline(s,1000,'\n');
/*здесь выполняем какие либо действия с полученной строкой*/

/*выводим строку для контроля*/
cout << s <<endl;
    };
    return 0;
}


Листинг 3. Обработка произвольного количества строковой информации (язык Pascal)
Код: Выделить всё
var
s:ansistring;
begin
while(not eof) do
begin
readln(s);
{здесь выполняем, какие либо действия с полученной строкой}

{выводим строку для контроля}
writeln(s);
    end;
end.


В листингах 1-3 представлены примеры обработки текстовых файлов с произвольным количеством строк. Причем программы работают именно с входным и выходным потоками. Как видите механизм очень простой, даже элементарный. Аналогичные программы можно написать и для всех остальных алгоритмических языков: PHP, Python, Perl и т.д.
Теперь обратимся к тому вопросу, с которого я начал свое изложение. И так в большинстве случаев мы всегда знаем, в какой строке сколько параметров имеется.
И так, предположим, что у нас есть текстовый файл, в котором, имеются строки, содержащие числа: два целых и одно вещественное. Вот как будут выглядеть программы, для чтения такого файла. Представленные программы не будут реагировать на количество пробелов в строке: в конце, начале или середине.

Листинг 4. Обработка произвольного количества строк, содержащих числовые данные (язык C)
Код: Выделить всё
#include <stdio.h>
int main() {
int a,b;
double f;
while(scanf("%d%d%lf",&a,&b,&f)!=-1){
/*здесь выполняем, какие либо действия с полученными числами*/

/*выводим числа для контроля*/
printf("%d %d %lf\n",a,b,f);
    }
    return 0;
}


Листинг 5. Обработка произвольного количества строк, содержащих числовые данные (язык C++)
Код: Выделить всё
#include <iostream>
using namespace std;
int main() {
    int a,b;
    double f;
    while(!cin.eof()){
       cin >> a >> b >> f;
/*здесь выполняем, какие либо действия с полученными числами*/

/*выводим числа для контроля*/
cout << a << ' ' << b<< ' '  << f <<endl;
    };
    return 0;
}


Листинг 6. Обработка произвольного количества строк, содержащих числовые данные (язык Pascal)
Код: Выделить всё
var
a,b:integer;
f:real;
begin
while(not eof) do
begin
readln(a,b,f);
{здесь выполняем, какие либо действия с полученными числами}

{выводим числа для контроля}
writeln(a,b,f);
end;
end.

На олимпиаде ведь большее и не требуется.
Если же с вас потребуют анализ вводимой строки (в условии задачи), например, если в строке попадутся не числа, или если в строке будет большее или меньшее количество чисел, чем заявлено, тогда и надо проводить анализ.
Ну и, наконец, пример программы, где строка действительно разбирается.

Листинг 7. Пример программы с разбором вводимых строк
Код: Выделить всё
#include <stdio.h>
int get_p(char *, char *, int *);

int main() {
   char s[1000],s1[1000];
   int i=0;
/*здесь выполняем какие либо действия с полученной строкой*/
   while(gets(s)){
/*выводим элементы строки*/
      while(get_p(s,s1,&i)){
         puts(s1);         
      }
   }
    return 0;
}
//функция, которая извлекает очередной элемент строки
int get_p(char *s, char *s1, int *i){
   int p=0,j=0;
   while(1){
      if(s[*i]>32){
         if(!p)p=1;
         s1[j++]=s[(*i)++];
      }else{
         if(p||!s[*i])break;
         (*i)++;
      }
   }
   s1[j]='\0';
   return p;
}


Но в конце концов, ведь есть же библиотечные функции, которые очень хорошо могут разобрать строку на части.
Последний раз редактировалось Vladislav_133 02 апр 2013, 11:21, всего редактировалось 1 раз.
Аватара пользователя
Vladislav_133
Elite
 
Сообщения: 1386
Зарегистрирован: 13 дек 2008, 18:08
Полное имя: П.В.Ю.

Re: Олимпиада 2013

Сообщение xdsl 01 апр 2013, 20:36

Владислав Юрьевич, char s[1000] - это все-таки не произвольная длина строки. И если в строке 2000 символов, такое определение устроит много проблем, начиная от зависания программы, кончая исключениями всех видов.

Даже var s:ansistring - не произвольная длина, хоть максимум в 2 миллиарда символов достичь труднее, чем в 1 тысячу.

Поэтому следует, на мой взгляд, все-же указывать максимальную длину строки в исходном файле, также как и количество строк. Никто-же не мешает указать максимум миллион строк по максимум 1000 символов ;)

Ну и внесу свою лепту кодом в обработку строк. Пусть в строке имеется набор слов (последовательности непробельных символов), разделенных произвольным кол-м пробелом. Тогда, получить все слова строки можно последовательностью вызовов, например такой функции (пока она не вернет пустую строку):
Подсветка синтаксиса: [ Загрузить ] [ Скрыть ]
Подсветка синтаксиса языка pascal
function getword(var s:string; var i:dword):string;
 begin
    result:='';
    while (i<=length(s))and(s[i]<=#32) do inc(i);
    while (i<=length(s))and(s[i]>#32) do begin result+=s[i]; inc(i); end;
 end;

Пример использования (считать строку, вывести в столбик по словам):
Подсветка синтаксиса: (getword.pp) [ Загрузить ] [ Скрыть ]
Подсветка синтаксиса языка pascal
{$mode objfpc}
{$H+}
function getword(var s:string; var i:dword):string;
 begin
    result:='';
    while (i<=length(s))and(s[i]<=#32) do inc(i);
    while (i<=length(s))and(s[i]>#32) do begin result+=s[i]; inc(i); end;
 end;
var s,w: string; i:dword=1;
begin
 readln(s);
 while true do begin
  w:=getword(s,i);
  if w='' then break;
  writeln(w);
 end;
end.

Надеюсь, нигде не заврался - не проверял, набросал по памяти.
xdsl
 
Сообщения: 1236
Зарегистрирован: 09 дек 2008, 05:16
Откуда: ВЦ ШГПИ
Полное имя: Слинкин Д.А.

Re: Олимпиада 2013

Сообщение Vladislav_133 01 апр 2013, 21:23

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

Re: Олимпиада 2013

Сообщение Vladislav_133 24 апр 2013, 16:46

Тема интересная и я решил ее продолжить. Собственно возник вопрос о том, можно ли в один проход построчно обрабатывать текстовый файл, если мы не знаем максимальной длины строки в тексте. Думаю, что можно, не имея при этом специального аппарата для такой обработки. Но начну несколько издалека. Рассмотрим простую программу, которая считывает текст посимвольно, разбивая при этом его на строки.
Код: Выделить всё
#include <stdio.h>

int main() {
   int c,i = 0;
   char s[1000];
   while(1){
      c=fgetc(stdin);
      if(c==(int)'\n' || c== EOF){
         s[i]='\0';
         //обработка строки
         //что-то делаем
         //вывод строки
         printf("%s",s);
         if(c==EOF)break;
         i=0;
         printf("\n");
      }else {
         //присовить символ и перейти к следующему
         s[i++]=(char)c;
      }
   }
   return 0;
}


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

Re: Олимпиада 2013

Сообщение xdsl 25 апр 2013, 08:50

Опять сталкиваемся с максимальной длиной строки. Владислав Юрьевич, в программе ОНА У ВАС ОГРАНИЧЕНА! не более 999 символов!
Значит и в условии задачи ее надо ограничивать. Иначе будет exception, или еще какой баг.

Вариант, самый близкий к понятию неограниченной длины, это "длины строки, не превышающей размера доступной приложению оперативной памяти". Но это, во первых, понятие растяжимое и зависит кучи параметров (аппаратуры, ОС, языка программирования, настроек компилятора/интерпретатора, настроек ограничений для пользователя и т.п.). А во вторых - на порядок усложняет обработку, т.к. подразумевает динамическое выделение памяти, и даже, при требовании только одного прохода по текстовому файлу, требует неоднократного перераспределения памяти для одной и той-же строки (память придется выделять кусками).

Можно, конечно, переложить все эти задачи на плечи языка программирования:
Подсветка синтаксиса: (infstring.pp) [ Загрузить ] [ Скрыть ]
Подсветка синтаксиса языка pascal
{$mode objfpc}
var s:ansistring;
begin
 while not eof do begin
   readln(s);
   // что-то делаем со строкой
   writeln(s);
 end;
end.

И получить максимальную длину строки в 2 гигабайта, но для действительно длинных строк это будет ОЧЕНЬ медленно.

Единственный случай, когда можно не оговаривать длину строки, это ситуация, когда даны другие ограничения (например - на общий размер файла), из которых максимальная длина строки может быть выведена. Или когда она вообще не важна. Например: определить номер строки, в которой содержится максимальное кол-во слов (длина слова - до 1000 байт, длина файла - до 100 гигабайт). В такой ситуации длина строки может быть потенциально до 100ГБ, что не позволит загрузить ее в оперативную память при любых реальных раскладах. Однако для решения задачи это и не нужно.
xdsl
 
Сообщения: 1236
Зарегистрирован: 09 дек 2008, 05:16
Откуда: ВЦ ШГПИ
Полное имя: Слинкин Д.А.

Re: Олимпиада 2013

Сообщение Vladislav_133 25 апр 2013, 10:27

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

Re: Олимпиада 2013

Сообщение xdsl 26 апр 2013, 07:51

Vladislav_133 писал(а):Нет, нет. Решение еще впереди. Я лишь хотел показать посимвольный ввод, который пригодится в последствии.
Так сказать, держу интригу.
Я до сих пор уверен, что без знания максимальной длины строки в тексте, невозможно загрузить ее и обработать ЦЕЛИКОМ, как это предлагается в примере от В.Ю., ибо размер такой строки в пределе равен бесконечности. Иногда, даже зная максимальную длину строки, это невозможно сделать (например, в задаче может быть сказано, что максимальная длина строки - 1 терабайт).

Так-что ждем решения.
xdsl
 
Сообщения: 1236
Зарегистрирован: 09 дек 2008, 05:16
Откуда: ВЦ ШГПИ
Полное имя: Слинкин Д.А.

Re: Олимпиада 2013

Сообщение Vladislav_133 26 апр 2013, 11:49

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


Вернуться в Алгоритмизация и программирование

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

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