Форум Всеукраїнської інтернет-олімпіади NetOI
На форумі обговорюються лише питання, пов'язані з олімпіадою
Ви не зайшли.
#1 2007-11-08 18:20:12
- MItornaDOS
- Новий користувач
- Звідки: Вінницька область
- Зареєстрований: 2007-11-08
- Повідомлень: 74
Задачі
Задача набрала 8 балів. Ні одного тайм аута. Допоможіть розібратися: що не так.
Код:
Program Kife;
var a:array [1..255] of integer;
x,x2,buf,N,p,i,j,Max,k,xx:integer;
viv,L,z,koor:string;
flag:boolean;
Begin
read (N,L);
delete (L,1,1);
xx:=0;
x:=1;
x2:=1;
j:=0;
buf:=N;
koor:='';
for i:=1 to Length (L) do val (L[i],a[i],p);
while ((N>0) and (length (L)>N)) do
begin
Max:=a[xx+1];
for i:=2 to N+1 do if a[xx+i]>Max then
begin
Max:=a[xx+i];
x:=xx+i;
x2:=i;
flag:=false;
end;
if flag
then
begin
xx:=xx+1;
str (a[xx],z);
koor:=koor+z;
delete (L,1,1);
end
else
begin
xx:=x;
str (a[xx],z);
koor:=koor+z;
delete (L,1,x2);
N:=N-x2+1;
end;
flag:=true;
if N>=Length (L) then
begin
delete (L,1,N);
N:=0;
end;
end;
if Length (L)<=N then delete (koor,Length (koor)-N,N);
L:=koor+L;
writeln (L);
End.Інші я опрацьовую пока самостійно
Відредаговано MItornaDOS (2007-11-08 19:21:55)
Поза форумом
#2 2007-11-08 20:04:54
- netoi07
- Новий користувач
- Зареєстрований: 2007-11-01
- Повідомлень: 9
Re: Задачі
input:
249 123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789
123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789123456789
123456789123456789123456789123456789123456789123456789001
(переводы строк сделаны для нормального отображения на форуме)
твой output:
99999
мой output:
999999
И вообще везде, где на входе L имеет 255 цифр твоя прога выводит ответ без 1 символа.
Вроде все остальные тесты проходит нормально..
=> вывод: в 12 тестах длина числа была максимально возможной
+
изменяешь строчку
" viv,L,z,koor:string;" на
" viv,L,z,koor:ansistring;"
и получаешь полный балл..
Відредаговано netoi07 (2007-11-08 20:09:37)
Поза форумом
#3 2007-11-08 20:15:48
- MItornaDOS
- Новий користувач
- Звідки: Вінницька область
- Зареєстрований: 2007-11-08
- Повідомлень: 74
Re: Задачі
netoi07 написав:
+
изменяешь строчку
" viv,L,z,koor:string;" на1
" viv,L,z,koor:ansistring;"
и получаешь полный балл..
сенкс
а что за ansistring?
Поза форумом
#4 2007-11-08 20:51:34
- MItornaDOS
- Новий користувач
- Звідки: Вінницька область
- Зареєстрований: 2007-11-08
- Повідомлень: 74
Re: Задачі
ага!
вот через эту вещь срезается 255-ый символ
Код:
read (N,L); delete (L,1,1);
Поза форумом
#5 2007-11-08 22:06:59
Re: Задачі
String - строка времён Turbo Pascal, ограничение на длину - 255 символов
AnsiSting - строка времён FreePascal, ограничение на память - 2 Гб
WideString - строка времён Delphi, ограничение на память - 2 Гб, Unicode.
Теоретически здесь можно обойтись и без AnsiString, чуть видоизменив считывание вот так:
var N: integer;
c: char;
L:string;
Begin
read (N,c);
readln(L);
Если вы с первого раза сумели написать программу, в которой транслятор не обнаружил ни одной ошибки, сообщите об этом системному программисту. Он исправит ошибки в трансляторе.
Поза форумом
#6 2007-11-09 14:31:26
- MItornaDOS
- Новий користувач
- Звідки: Вінницька область
- Зареєстрований: 2007-11-08
- Повідомлень: 74
Re: Задачі
Skiminok написав:
String - строка времён Turbo Pascal, ограничение на длину - 255 символов
AnsiSting - строка времён FreePascal, ограничение на память - 2 Гб
WideString - строка времён Delphi, ограничение на память - 2 Гб, Unicode.
Теоретически здесь можно обойтись и без AnsiString, чуть видоизменив считывание вот так:
var N: integer;
c: char;
L:string;
Begin
read (N,c);
readln(L);
Я понял, спасибо!
Поза форумом
#7 2007-11-10 10:36:43
- MItornaDOS
- Новий користувач
- Звідки: Вінницька область
- Зареєстрований: 2007-11-08
- Повідомлень: 74
Re: Задачі
Вот задача проходит 8 тестов, остальные "Time Out"
Код:
program Military;
{$H+}
var s,z:string;
i,j,c:longint;
begin
readln (s);
i:=0;
j:=0;
while pos ('><',s)<>0 do
begin
while pos (' ',s)<>0 do delete (s,pos (' ',s),1);
z:=s;
while pos ('><',s)<>0 do
begin
c:=pos ('><',s);
delete (s,c,2);
delete (z,c,2);
insert ('<>',z,c);
insert (' ',s,c);
j:=j+1;
end;
s:=z;
i:=i+1;
end;
writeln (i,' ',j);
{$H-}
end.Поза форумом
#8 2007-11-10 10:49:44
- reiten
- журі
- Звідки: Киев
- Зареєстрований: 2005-10-16
- Повідомлень: 196
Re: Задачі
Правильно. Такое решение больше набирать и не должно.
Видимо, таймов раньше не было из-за обрезки строки по 256 символам.
"...Существуют два подхода к проектированию программ. В одном архитектура делается настолько простой, что в ней явно нет дефектов; в другом - настолько сложной, что в ней нет явных дефектов".
С. А. Хоар
Поза форумом
#9 2007-11-10 11:25:18
- MItornaDOS
- Новий користувач
- Звідки: Вінницька область
- Зареєстрований: 2007-11-08
- Повідомлень: 74
Re: Задачі
reiten написав:
Правильно. Такое решение больше набирать и не должно.
Видимо, таймов раньше не было из-за обрезки строки по 256 символам.
а что сделать то?
Поза форумом
#10 2007-11-10 11:29:43
- reiten
- журі
- Звідки: Киев
- Зареєстрований: 2005-10-16
- Повідомлень: 196
Re: Задачі
Искать алгоритмически верное решение.
Там есть линейный алгоритм на самом деле.
Мой код:
Код:
#include <cstdio>
using namespace std;
const int maxL=90000;
char seq[maxL+5];
int main() {
scanf(" %[<>]",seq);
int time,i,before;
long long moves;
for(i=0,time=moves=before=0;seq[i];i++)
if(seq[i]=='>')before++;
else {
moves+=before;
if(before) {
if(time+1<before)time=before;
else time++;
}
}
printf("%d %Ld\n",time,moves);
return 0;
}"...Существуют два подхода к проектированию программ. В одном архитектура делается настолько простой, что в ней явно нет дефектов; в другом - настолько сложной, что в ней нет явных дефектов".
С. А. Хоар
Поза форумом
#11 2007-11-10 13:23:37
- MItornaDOS
- Новий користувач
- Звідки: Вінницька область
- Зареєстрований: 2007-11-08
- Повідомлень: 74
Re: Задачі
reiten написав:
Искать алгоритмически верное решение.
Там есть линейный алгоритм на самом деле.
Мой код:Код:
#include <cstdio> using namespace std; const int maxL=90000; char seq[maxL+5]; int main() { scanf(" %[<>]",seq); int time,i,before; long long moves; for(i=0,time=moves=before=0;seq[i];i++) if(seq[i]=='>')before++; else { moves+=before; if(before) { if(time+1<before)time=before; else time++; } } printf("%d %Ld\n",time,moves); return 0; }
знаю только паскаль/делфи
Поза форумом
#12 2007-11-10 17:44:53
Re: Задачі
Вот полностью работающее решение на Делфи (или на Фри):
Код:
program Military4;
{$APPTYPE CONSOLE}
type integer=longint;
var
pc, c: char;
qr, time, quan: Integer;
function max(a,b: integer): Integer;
begin if a>b then max:=a else max:=b end;
begin
repeat Read(c) until (c='>') or eoln;
qr:=1; time:=0; quan:=0;
pc:=c;
while not eoln do
begin
Read(c);
if c='>'
then Inc(qr)
else begin
Inc(quan,qr);
if pc='>'
then time:=max(qr,time+1)
else inc(time)
end;
pc:=c;
end;
Writeln(time,' ',quan);
end.Если вы с первого раза сумели написать программу, в которой транслятор не обнаружил ни одной ошибки, сообщите об этом системному программисту. Он исправит ошибки в трансляторе.
Поза форумом