Форум Всеукраїнської інтернет-олімпіади NetOI

Чуча · 2007-11-07 18:23:35

Уважаемые олимпийцы! Очень прошу вас помочь!
У меня не проходят последние 4 теста. Причем выдает:"Bad data". Что это значит?
Очень хотелось бы разобраться что у меня неправильно. Выкладываю текст решения. Кому будет нетрудно покопаться, укажите, пожалуйста на ошибки. Или выложите свои верные решения. Заранее спасибо.

var
s1,s2,temp:string;
l,n,i,j,start,number:byte;
max,ch:char;
Begin
read(n);
read(ch);
readln(s1);
l:=length(s1);
start:=1;
s2:='';
for i:=1 to l-n do
begin
max:=s1[start];
number:=start;
for j:=start+1 to n+i do
if s1[j]>max then
begin
max:=s1[j];
number:=j;
end;
s2:=s2+max;
start:=number+1;
end;
writeln(s2);
end.

Cris · 2007-11-07 18:28:02

program kife;
var n,i,j:byte;
g:char;
l,max,ls:string;
begin
readln(n,g,l);
ls:=l;
for j:=1 to n do
begin
max:='';
for i:=1 to length(l) do
begin
delete(l,i,1);
if max<l
then max:=l;
l:=ls;
end;
l:=max;
ls:=l;
end;
write(max);
end.

MAXXX · 2007-11-07 19:06:30

Не хочу создавать новую тему по этому вопросу, поэтому напишу здесь. Кто-нибуть знает решение Кайф с линейным временем работы в хучшем случае?
н-длина числа
Я знаю 2 квадратных:
1) пусть нам надо оставить к чисел. Найдем самую раннюю позицию максимальной цифры в промежутке 1..к-ая цифра с конца. Это первая цифра. Теперь рассмотрим промежуток от первой цифры ответа до к-1-ой цифры с конца.Найдем опять первую максимальную цифру, от нее потом 3-ю и т.д.
2) Реккурентное соотношение - лучший ответ из первых н цифр числа из которых мы вычеркнули к=лучшее из (первых н чисел из которых мы вычеркнули к-1 (вычеркиваем тогда н-тую цифру), первых н-1 чисел из которых мы вычеркнули к(не вычеркивеам н-тую цифру)). Тогда приидется хранить массив 255*255 стрингов и по времени вроде пару тестов не проходит
Решение н*лог(н)
Поиск максимума делаем с помощью структур данных - но константа при н тогда получается огромна
Решение за 10*н
Для каждой позиции і изначального числа запишем для каждой из цифр 0..9 первое ее вхождение в строке і..н. Дальше поиск максимума(как в 1 квадратичном решении) можно произвести по цифрам 0..9. Сложность получается суммарная 10*н если аккуратно реализовать.
А как по поводу решения за линию? Интерестно было бы услышать. ИМХО это вообще самая каверзная задачка тура - много людей из отрезка 90..99 не получили 100 именно из-за нее.

Відредаговано MAXXX (2007-11-07 19:08:02)

necro · 2007-11-07 19:12:51

MAXXX написав:
Не хочу создавать новую тему по этому вопросу, поэтому напишу здесь. Кто-нибуть знает решение Кайф с линейным временем работы в хучшем случае?
н-длина числа
Я знаю 2 квадратных:
1) пусть нам надо оставить к чисел. Найдем самую раннюю позицию максимальной цифры в промежутке 1..к-ая цифра с конца. Это первая цифра. Теперь рассмотрим промежуток от первой цифры ответа до к-1-ой цифры с конца.Найдем опять первую максимальную цифру, от нее потом 3-ю и т.д.
2) Реккурентное соотношение - лучший ответ из первых н цифр числа из которых мы вычеркнули к=лучшее из (первых н чисел из которых мы вычеркнули к-1 (вычеркиваем тогда н-тую цифру), первых н-1 чисел из которых мы вычеркнули к(не вычеркивеам н-тую цифру)). Тогда приидется хранить массив 255*255 стрингов и по времени вроде пару тестов не проходит
Решение н*лог(н)
Поиск максимума делаем с помощью структур данных - но константа при н тогда получается огромна
Решение за 10*н
Для каждой позиции і изначального числа запишем для каждой из цифр 0..9 первое ее вхождение в строке і..н. Дальше поиск максимума(как в 1 квадратичном решении) можно произвести по цифрам 0..9. Сложность получается суммарная 10*н если аккуратно реализовать.
А как по поводу решения за линию? Интерестно было бы услышать. ИМХО это вообще самая каверзная задачка тура - много людей из отрезка 90..99 не получили 100 именно из-за нее.

Это просто недоработка так как самое тупое решение получало АС. На линейным и сам задумывался. Надо наверно углубится в структуры данных например RMQ.

ПС : А сколько людей Милитари не решили ))

Відредаговано necro (2007-11-07 19:25:57)

AlexeyS · 2007-11-07 19:16:46

Я писал kife за O(n*ln(n)). А на счёт 10н, на сколько я понимаю, это и есть линия, то есть O(n).

#include <iostream>
#include <cstdio>
#include <vector>
#include <set>
#include <map>
#include <list>
#include <deque>
#include <algorithm>
#include <utility>
#include <cmath>
#include <string>

using namespace std;

#define FOR(i, a, n) for(int i=a, __ ## i=n; i<__ ## i; i++)
#define REP(i, n) FOR(i, 0, n)
#define sz(X) int(X.size())
#define mp make_pair
#define pb push_back
#define X first
#define Y second

typedef long long lint;
typedef pair<int, int> PII;
typedef vector<int> VI;

int main()
{
char s[300];
int n;
scanf("%d %s", &n, s);
int sn=strlen(s);
set<PII> num;
int ind=0;
REP(i, n) num.insert(mp(-int(s[i]), i));
REP(i, sn-n){
num.insert(mp(-int(s[i+n]), i+n));
PII p=*num.begin();
printf("%c", char(-p.X));
FOR(i, ind, p.Y+1) num.erase(num.find(mp(-int(s[i]),i)));
ind=p.Y+1;
}
printf("\n");
return 0;
}

askold · 2007-11-07 19:17:23

Реккурентное соотношение - лучший ответ из первых н цифр числа из которых мы вычеркнули к=лучшее из (первых н чисел из которых мы вычеркнули к-1 (вычеркиваем тогда н-тую цифру), первых н-1 чисел из которых мы вычеркнули к(не вычеркивеам н-тую цифру)). Тогда приидется хранить массив 255*255 стрингов и по времени вроде пару тестов не проходит

Достатньо зберігати масив довгих чисел 2*256. В мене пройшло на 19 балів.

MAXXX · 2007-11-07 19:18:08

При н*логн я тоже вобщемто говорил про RMQ. Но даже при реализации (н*логн, логн) константа я предпологаю больше 255. а при (н,1) - это вообще жуть будет - оно точно по времени не пройдет.
Я пожалуй переформулирую вопрос:
Решение за линию, которое проходит по времени и по сложности реализации сравнимо с каким-нибуть решением какой-нибуть задачи этого тура...Хотя бы самой трудоемкой...А не превышает его (ИМХО)ОЧЕНЬ сильно.

Відредаговано MAXXX (2007-11-07 19:19:40)

necro · 2007-11-07 19:22:22

AlexeyS написав:
#include <algorithm>

Нехотелось бы начинать бесполезный спор. Но как же меня злят эти решения (( не злитесь сишники но вам в пору писать не :
"Я писал за НлогН", а "За меня написали за НлогН".
Почему никто не хочет с этим боротся. Пусть даже вплоть до того что отказытася от Паскаля. Хотя это убивает львиную долю интереса решения задач когда тебе нужно только нужное проинклудить.
Когда последний раз кучу в ручную писали? А?! Товарищи супер-программисты?...

Відредаговано necro (2007-11-07 19:24:10)

AlexeyS · 2007-11-07 19:23:34

До меня дошло. MAXXX (если не ошибаюсь Андрей) ты реально нашёл решение за O(n). если хранить 10 масивов с положениями цифр.

AlexeyS · 2007-11-07 19:29:52

necro написав:
AlexeyS написав:
#include <algorithm>
Но как же меня злят эти решения (( не злитесь сишники

не беспокойся, я согласен, что паскаля достаточно, например мне хватило для первого места на всеукре. Но для студентов Паскаль - это детство.

MAXXX · 2007-11-07 19:30:16

2AlexeyS: нет, это не О(н). Это О(н*колво различных символов). Если бы строки могли быть из всех 255 символов - это бы не помогло
2askold: На последнем тесте ТЛ? У еще нескольких человек, котрые так писали тоже ТЛ
2necro: Это с одной стороны привелегия сишников и они правильно ею пользуются. Но с другой стороны помоему( я редко пишу на Си, поэтому оценивать реально не могу) это должно тормозить. По крайней мере если бы это было написано просто самим, то работало быстрее. Но си это может компенсировать природным быстродействием наверно...
ЗЫ. Это точно плохо тем, что сишники часто считают что им не нужны эти алгоритмы. И не учат их. А если надо написать чтото из структур данных чего нет в СТЛ - тут и наступает месть паскалиста)))

AlexeyS · 2007-11-07 19:32:46

MAXXX написав:
Это О(н*колво различных символов).

Согласен

reiten · 2007-11-07 19:39:47

Собственно, быстрее, чем O(n*число_цифр) тут и не выйдет. Иначе мы бы за единичное время находили минимум.
Но этого хватает с лихвой:

Код:

#include <cstdio>
#include <cstring>

using namespace std;

const int maxL=500;

int main() {
     char num[maxL+5];
     int first[maxL][10];
     int cur[10];
     int n,len;
     int i,j;
     scanf("%d%s",&n,num);
     len=strlen(num);
     for(j=0;j<10;j++)cur[j]=len+n+5;
     for(i=len-1;i>=0;i--) {
          cur[num[i]-'0']=i;
          for(j=0;j<10;j++)
               first[i][j]=cur[j];
     }
     for(i=0;i+n<len;i++) {
          for(j=9;j>=0&&first[i][j]-i>n;j--);
          putc(j+'0',stdout);
          n-=first[i][j]-i;
          i=first[i][j];
     }
     putc('\n',stdout);
     return 0;
}

Как на меня, так не особо сложно.
AlexeyS
А вот твой код с сетом как раз из-за сета мог и завалиться: тут ведь таймлимиты от авторского решения, так что при малых тестах и жестких константах сет может не влезть в time-limit чисто из-за констант в реализации. И уж всяко будет дольше, чем в решении 10n.

MAXXX · 2007-11-07 19:42:39

reiten написав:
Собственно, быстрее, чем O(n*число_цифр) тут и не выйдет. Иначе мы бы за единичное время находили минимум.

А вдруг есть кардинально другое решение?
Впрочем что-то мне подсказывает что нет...

necro · 2007-11-07 19:43:31

MAXXX написав:
2AlexeyS: нет, это не О(н). Это О(н*колво различных символов). Если бы строки могли быть из всех 255 символов - это бы не помогло
2askold: На последнем тесте ТЛ? У еще нескольких человек, котрые так писали тоже ТЛ
2necro: Это с одной стороны привелегия сишников и они правильно ею пользуются. Но с другой стороны помоему( я редко пишу на Си, поэтому оценивать реально не могу) это должно тормозить. По крайней мере если бы это было написано просто самим, то работало быстрее. Но си это может компенсировать природным быстродействием наверно...
ЗЫ. Это точно плохо тем, что сишники часто считают что им не нужны эти алгоритмы. И не учат их. А если надо написать чтото из структур данных чего нет в СТЛ - тут и наступает месть паскалиста)))

Да нет же вы не понимаете сути проблемы. Проблема в том что олимпиадчики ставятся в очень неравные условия которые как я полагаю обусловлены неосведомленнотью или равнодушием организаторов соревнований. Мне от того не холодно не жарко, но мне нравится такое положение дел и я непойму почему не никаких продвижений в решении этого вопроса.
Я же не спорю что Паскаль это в реальном програминге - не инструмент а пережиток прошлого, но олмпиады то должны проверять не только умение применить алгоритм но и запрограмировать его.
ПС : если говорить что Паскалисты - ламера то кто тогда Сишники?
ППС : имхо Сишники - юзеры, Паскалисты - девелоперы ))

MAXXX · 2007-11-07 19:48:41

1). Согласен. Я не имел ввиду что паскалисты ламеры... скорее с последней твоей фразой согласен
Такой вопрос...ТЛ=авторское время*к.
1).Это к для паскаля и для си одинаково?
2).Это авторское время для всех тестов различно и равно времени работы авторской проги на этом тесте или оно равно времени роботы авторской проги на хучшем тесте(ведь в конце концов лучший случай у автора может у когото быть худше)

Dark_Dimius · 2007-11-07 19:53:06

necro написав:
MAXXX написав:
2AlexeyS: нет, это не О(н). Это О(н*колво различных символов). Если бы строки могли быть из всех 255 символов - это бы не помогло
2askold: На последнем тесте ТЛ? У еще нескольких человек, котрые так писали тоже ТЛ
2necro: Это с одной стороны привелегия сишников и они правильно ею пользуются. Но с другой стороны помоему( я редко пишу на Си, поэтому оценивать реально не могу) это должно тормозить. По крайней мере если бы это было написано просто самим, то работало быстрее. Но си это может компенсировать природным быстродействием наверно...
ЗЫ. Это точно плохо тем, что сишники часто считают что им не нужны эти алгоритмы. И не учат их. А если надо написать чтото из структур данных чего нет в СТЛ - тут и наступает месть паскалиста)))
Да нет же вы не понимаете сути проблемы. Проблема в том что олимпиадчики ставятся в очень неравные условия которые как я полагаю обусловлены неосведомленнотью или равнодушием организаторов соревнований. Мне от того не холодно не жарко, но мне нравится такое положение дел и я непойму почему не никаких продвижений в решении этого вопроса.
Я же не спорю что Паскаль это в реальном програминге - не инструмент а пережиток прошлого, но олмпиады то должны проверять не только умение применить алгоритм но и запрограмировать его.
ПС : если говорить что Паскалисты - ламера то кто тогда Сишники?
ППС : имхо Сишники - юзеры, Паскалисты - девелоперы ))

прикол.... большинство операционок написаны на си, следовательно юзверями
....
ржал

Чуча · 2007-11-07 20:38:16

Люди. Скажите, пожалуйста, так всё-таки что такое Bad Data?

Nicky Nick · 2007-11-07 21:05:09

Dark_Dimius написав:
necro написав:
MAXXX написав:
2AlexeyS: нет, это не О(н). Это О(н*колво различных символов). Если бы строки могли быть из всех 255 символов - это бы не помогло
2askold: На последнем тесте ТЛ? У еще нескольких человек, котрые так писали тоже ТЛ
2necro: Это с одной стороны привелегия сишников и они правильно ею пользуются. Но с другой стороны помоему( я редко пишу на Си, поэтому оценивать реально не могу) это должно тормозить. По крайней мере если бы это было написано просто самим, то работало быстрее. Но си это может компенсировать природным быстродействием наверно...
ЗЫ. Это точно плохо тем, что сишники часто считают что им не нужны эти алгоритмы. И не учат их. А если надо написать чтото из структур данных чего нет в СТЛ - тут и наступает месть паскалиста)))
Да нет же вы не понимаете сути проблемы. Проблема в том что олимпиадчики ставятся в очень неравные условия которые как я полагаю обусловлены неосведомленнотью или равнодушием организаторов соревнований. Мне от того не холодно не жарко, но мне нравится такое положение дел и я непойму почему не никаких продвижений в решении этого вопроса.
Я же не спорю что Паскаль это в реальном програминге - не инструмент а пережиток прошлого, но олмпиады то должны проверять не только умение применить алгоритм но и запрограмировать его.
ПС : если говорить что Паскалисты - ламера то кто тогда Сишники?
ППС : имхо Сишники - юзеры, Паскалисты - девелоперы ))
прикол.... большинство операционок написаны на си, следовательно юзверями
....
ржал

+10))))

Dark_Dimius · 2007-11-07 22:33:57

reiten написав:
Собственно, быстрее, чем O(n*число_цифр) тут и не выйдет. Иначе мы бы за единичное время находили минимум.
Но этого хватает с лихвой:
Код:
#include <cstdio>
#include <cstring>

using namespace std;

const int maxL=500;

int main() {
     char num[maxL+5];
     int first[maxL][10];
     int cur[10];
     int n,len;
     int i,j;
     scanf("%d%s",&n,num);
     len=strlen(num);
     for(j=0;j<10;j++)cur[j]=len+n+5;
     for(i=len-1;i>=0;i--) {
          cur[num[i]-'0']=i;
          for(j=0;j<10;j++)
               first[i][j]=cur[j];
     }
     for(i=0;i+n<len;i++) {
          for(j=9;j>=0&&first[i][j]-i>n;j--);
          putc(j+'0',stdout);
          n-=first[i][j]-i;
          i=first[i][j];
     }
     putc('\n',stdout);
     return 0;
}
Как на меня, так не особо сложно.
AlexeyS
А вот твой код с сетом как раз из-за сета мог и завалиться: тут ведь таймлимиты от авторского решения, так что при малых тестах и жестких константах сет может не влезть в time-limit чисто из-за констант в реализации. И уж всяко будет дольше, чем в решении 10n.

вопрос - чего ты пишешь putc('\n',stdout); а не printf("\n"); привычнее или есть чтото мне не известное?

Skiminok · 2007-11-07 22:44:00

Чуча написав:
Люди. Скажите, пожалуйста, так всё-таки что такое Bad Data?

Bad Data - это значит или ошибка выполнения (программа вылетает по ходу работы, например, из-за деления на ноль или выхода за границы массива/типа данных) или неправильный формат вывода.

Skiminok · 2007-11-07 23:16:51

Dark_Dimius написав:
прикол.... большинство операционок написаны на си, следовательно юзверями
....
ржал

Первые версии Винды, к примеру, были написаны в основном на Паскале. Там же были реализованы и все необходимые трудоёмкие структуры данных, и вычисления и т.д. Потом только начинает набирать обороты Си, в основном из-за своего быстродействия - но не более! Программисты того времени (конец 80-х - начало 90-х) говорили, что перейти с простого и привычного человеческого языка на мозго...дробильный синтаксис Си их заставило бы только дуло пистолета. (Кстати, именно поэтому в то время так были популярны многочисленные гибриды, пытавшиея совместить достоинства всех языков - что-то подобное наблюдаем и сейчас... D, Lua...) А потом в Редмонде просто-напросто переписали все использованные алгоритмы на Си, сделав шаг в угоду скорости (хоть я и ярый фанат-дельфист, и готов отстаивать эту позицию до последней капли крови - но тут я ребят понимаю и готов признать, что выбор был вернее). Ну а дальше всё ясно без слов. Раз есть Майкрософт - значит есть негласный стандарт (не путать со стандартом языка Си). И пошло-поехало...
Только вот до конца 90-х самым популярным средством разработки на виндовой платформе почему-то всё равно оставался Delphi...

necro · 2007-11-07 23:47:19

Dark_Dimius написав:
necro написав:
MAXXX написав:
2AlexeyS: нет, это не О(н). Это О(н*колво различных символов). Если бы строки могли быть из всех 255 символов - это бы не помогло
2askold: На последнем тесте ТЛ? У еще нескольких человек, котрые так писали тоже ТЛ
2necro: Это с одной стороны привелегия сишников и они правильно ею пользуются. Но с другой стороны помоему( я редко пишу на Си, поэтому оценивать реально не могу) это должно тормозить. По крайней мере если бы это было написано просто самим, то работало быстрее. Но си это может компенсировать природным быстродействием наверно...
ЗЫ. Это точно плохо тем, что сишники часто считают что им не нужны эти алгоритмы. И не учат их. А если надо написать чтото из структур данных чего нет в СТЛ - тут и наступает месть паскалиста)))
Да нет же вы не понимаете сути проблемы. Проблема в том что олимпиадчики ставятся в очень неравные условия которые как я полагаю обусловлены неосведомленнотью или равнодушием организаторов соревнований. Мне от того не холодно не жарко, но мне нравится такое положение дел и я непойму почему не никаких продвижений в решении этого вопроса.
Я же не спорю что Паскаль это в реальном програминге - не инструмент а пережиток прошлого, но олмпиады то должны проверять не только умение применить алгоритм но и запрограмировать его.
ПС : если говорить что Паскалисты - ламера то кто тогда Сишники?
ППС : имхо Сишники - юзеры, Паскалисты - девелоперы ))
прикол.... большинство операционок написаны на си, следовательно юзверями
....
ржал

Офигеть. Сам придумал сам поржал. Опять же говоришь чтобы говорить... Ты что не можеш понять что речь идет конкретно об олимпиадах. Давай скажи еще чтонибудь на отмазку от того что просто лень реально шарить и разбиратся в структурах данных и алгоритмах...

Dark_Dimius · 2007-11-08 09:16:28

Skiminok написав:
Dark_Dimius написав:
прикол.... большинство операционок написаны на си, следовательно юзверями
....
ржал
Первые версии Винды, к примеру, были написаны в основном на Паскале.

источник?

Чуча · 2007-11-08 12:23:07

Skiminok написав:
Чуча написав:
Люди. Скажите, пожалуйста, так всё-таки что такое Bad Data?
Bad Data - это значит или ошибка выполнения (программа вылетает по ходу работы, например, из-за деления на ноль или выхода за границы массива/типа данных) или неправильный формат вывода.

Спасибо.

Форум Всеукраїнської інтернет-олімпіади NetOI

#1 2007-11-07 18:23:35

Задача kife. Что неправильно?

#2 2007-11-07 18:28:02

Re: Задача kife. Что неправильно?

#3 2007-11-07 19:06:30

Re: Задача kife. Что неправильно?

#4 2007-11-07 19:12:51

Re: Задача kife. Что неправильно?

MAXXX написав:

#5 2007-11-07 19:16:46

Re: Задача kife. Что неправильно?

#6 2007-11-07 19:17:23

Re: Задача kife. Что неправильно?

#7 2007-11-07 19:18:08

Re: Задача kife. Что неправильно?

#8 2007-11-07 19:22:22

Re: Задача kife. Что неправильно?

AlexeyS написав:

#9 2007-11-07 19:23:34

Re: Задача kife. Что неправильно?

#10 2007-11-07 19:29:52

Re: Задача kife. Что неправильно?

necro написав:

AlexeyS написав:

#11 2007-11-07 19:30:16

Re: Задача kife. Что неправильно?

#12 2007-11-07 19:32:46

Re: Задача kife. Что неправильно?

MAXXX написав:

#13 2007-11-07 19:39:47

Re: Задача kife. Что неправильно?

Код:

#14 2007-11-07 19:42:39

Re: Задача kife. Что неправильно?

reiten написав:

#15 2007-11-07 19:43:31

Re: Задача kife. Что неправильно?

MAXXX написав:

#16 2007-11-07 19:48:41

Re: Задача kife. Что неправильно?

#17 2007-11-07 19:53:06

Re: Задача kife. Что неправильно?

necro написав:

MAXXX написав:

#18 2007-11-07 20:38:16

Re: Задача kife. Что неправильно?

#19 2007-11-07 21:05:09

Re: Задача kife. Что неправильно?

Dark_Dimius написав:

necro написав:

MAXXX написав:

#20 2007-11-07 22:33:57

Re: Задача kife. Что неправильно?

reiten написав:

Код:

#21 2007-11-07 22:44:00

Re: Задача kife. Что неправильно?

Чуча написав:

#22 2007-11-07 23:16:51

Re: Задача kife. Что неправильно?

Dark_Dimius написав:

#23 2007-11-07 23:47:19

Re: Задача kife. Что неправильно?

Dark_Dimius написав:

necro написав:

MAXXX написав:

#24 2007-11-08 09:16:28

Re: Задача kife. Что неправильно?

Skiminok написав:

Dark_Dimius написав:

#25 2007-11-08 12:23:07

Re: Задача kife. Что неправильно?

Skiminok написав:

Чуча написав:

Нижній колонтитул