Блог пользователя bardakov_a_a

Автор bardakov_a_a, 12 лет назад, По-русски

Взялся за Кормена, вот с толкнулся в самом начале с проблемкой анализа алгоритма Будьте любезны, на примере строки 1 объясните как нужно делать задание

https://docs.google.com/open?id=0B8XlXdD_oV46Z2lYVTlDRVFtck0

Полный текст и комментарии »

  • Проголосовать: нравится
  • +2
  • Проголосовать: не нравится

Автор bardakov_a_a, 12 лет назад, По-русски

http://mirror.codeforces.com/blog/entry/495 — Разбор задачи (http://mirror.codeforces.com/contest/1/problem/C собственно сама задача) я что-то не понимаю на каком правиле основывается n = pi / gcd(A, B, C);

Полный текст и комментарии »

  • Проголосовать: нравится
  • -5
  • Проголосовать: не нравится

Автор bardakov_a_a, 12 лет назад, По-русски

Дамы и Господа! Нужна ваша помощь. Вот задача из самого первого соревнования codeforces http://mirror.codeforces.com/contest/1/problem/B?locale=ru

Помогите найти ошибку в логике. Валится на 7 тесте

program Project2;

{$APPTYPE CONSOLE}

var
  n: Integer;
  i: Integer;
  tmp: String;


function Selection(tmp: String): Boolean;
var i,j: Integer;
begin
  Selection:=True;
  if tmp[1]='R' then
  begin
    Delete(tmp, 1, 2);
    if Pos('C', tmp)<>0 then
        Selection:=False;
  end;
end;

function Power(a, n: Integer): Int64;
begin
  if n=0 then Power:=1
  else if odd(n) then Power:=Power(a*a, n div 2)*a
       else Power:=Power(a*a, n div 2);
end;

procedure ToTwoView(tmp: String);
var i, j: Integer;
  k: Integer;
  st: String;
  sum: Int64;
begin
  sum:=0;
  j:=Length(tmp);
  for i := j downto 1 do
    if tmp[i] In ['0'..'9'] then
      st:= tmp[i] + st
    else break;
  for j := i downto 1 do
    sum:=sum + (Ord(tmp[j])-Ord('A')+1)*Power(26,i-j);
  WriteLn('R',st,'C',sum);
end;

procedure ToOneView(tmp: String);
var st, st2: String;
  i,j,k: Integer;
  p, code: Integer;
begin
  i:=Pos('C', tmp);
  st:='';
  k:=Length(tmp);
  for j := 1 to i do
    if tmp[j] In ['0'..'9'] then
      st:=st+tmp[j];
  for j := i to k do
    if tmp[j] In ['0'..'9'] then
      st2:=st2+tmp[j];
  Val(st2, p, code);
  st2:='';
  while p>0 do
  begin
    i:= p mod 26;
    if i=0 then i:=26;
    st2:=st2+Chr(Ord('A')-1+i);
    p:=p-i;
    p:=p div 26;
  end;
  k:=Length(st2);
  for i := k downto 1 do
    Write(st2[i]);
  Write(st);
  WriteLn;
end;

begin
  ReadLn(n);
  for i := 1 to n do
  begin
    ReadLn(tmp);
    case Selection(tmp) of
      true: ToTwoView(tmp);
      false: ToOneView(tmp);
    end;
  end;
end.

Думаю, функция selection при каких-то значениях не верно определяет, но конкретного примера пока не нашел.

Полный текст и комментарии »

  • Проголосовать: нравится
  • +1
  • Проголосовать: не нравится

Автор bardakov_a_a, 12 лет назад, По-русски

Очередной раз тренировался в решении олимпиадных задач и наткнулся на следующую: https://docs.google.com/open?id=0B8XlXdD_oV46RGFmTWg5LWtjd2M

Подкиньте идеи для решения И объясните по какому принципу в 1-м примере получился такой ответ

Полный текст и комментарии »

  • Проголосовать: нравится
  • -12
  • Проголосовать: не нравится

Автор bardakov_a_a, 12 лет назад, По-русски

~~~~ program Project2;

const MaxN=100005; type TTree=array[1..MaxN] of Integer;

var N: Integer; // количество вершин Tree: TTree; //дерево x,y: Integer; //ребра дерева a,b,c: Integer; //начало, конец, узел проверки M: Integer; //количество тестов

function run(a,b,c: Integer): String; forward;

///инициализация procedure initial; begin N:=0; x:=0; y:=0; a:=0; b:=0; c:=0; M:=0; FillChar(Tree, SizeOf(Tree), 0); end;

///основная часть /// считывание /// обработка /// запись procedure readdata; var F: Text; i: Integer; G: Text; begin Assign(F, 'input.txt'); Reset(F); Assign(G, 'output.txt'); Rewrite(G); ReadLn(F,N); for i := 1 to N — 1 do begin ReadLn(F,x, y); if Tree[y]=0 then Tree[y]:=x else Tree[x]:=y; end; ReadLn(F, M); for i := 1 to M do begin ReadLn(F, a, b, c); WriteLn(G, run(a,b,c)); end; Close(G); Close(F); end;

function run(a,b,c: Integer): String; var i: Integer; begin run:='No'; for i := a to b do if (Tree[i]=c)Or(c=a)Or(c=b) then begin run:='Yes'; exit; end; end;

begin initial; readdata; end.

~~~~~

Проверка показала, что набрал из 10 балов 6. Я предполагаю не уложился по времени,тогда как нужно было изменить решение чтобы уложиться? Ведь если я буду использовать указатели, рекурсивный обход будет еще медленнее.

Полный текст и комментарии »

  • Проголосовать: нравится
  • +5
  • Проголосовать: не нравится

Автор bardakov_a_a, 12 лет назад, По-русски

Дамы и Господа! Нужна Ваша помощь. Решил заняться олимпиадным программированием и вот пока встречаю камни предкновения. Решал задачу с Timus 1110 Степень http://acm.timus.ru/problem.aspx?space=1&num=1110 1110. Степень Ограничение времени: 0.5 секунды Ограничение памяти: 16 МБ Даны целые числа N, M и Y. Напишите программу, которая найдёт все целые числа X в диапазоне [0, M – 1], такие что XN mod M = Y. Исходные данные Ввод содержит единственную строку с числами N, M и Y (0 < N < 999, 1 < M < 999, 0 < Y < 999), записанными через пробел. Результат Выведите все числа X через пробел в одной строке. Числа должны идти в порядке возрастания. Если искомых чисел нет, выведите −1.

Вот собственно код

program Project2;

{$APPTYPE CONSOLE}

var
  N,M,Y: Word;
  i: Word;
  found: Boolean;

function Power(i: Word; N: Word): Integer;
var res: Integer;
begin
  if odd(N) then  res:=i
  else res := 1;
  while N>1 do
  begin
    N:=N div 2;
    i:=i*i;
    if odd(N) then
      res:=res*i;
  end;
  Power:=res;
end;

function Left(x: Integer; y, n: Integer): Integer;
begin
  Left:=Power(x mod n, y) mod n;
end;

begin
  ReadLn(N, M, Y);
  found:=true;
  for i := 0 to M --- 1 do
    if Left(i, N, M) = Y then
    begin
      Write(i, ' ');
      found:=false;
    end;
  if found then Write(-1);
end.


Валиться на 6 тесте. Предполагаю не укладывается по времени, но я уже не знаю как ее еще улучшить. Помогите кто чем сможет

Полный текст и комментарии »

  • Проголосовать: нравится
  • -3
  • Проголосовать: не нравится

Автор bardakov_a_a, 12 лет назад, По-русски

Народ, нужна помощь. Решал задачу на Timus. 1011 Кондукторы Your text to link here... так вот не пойму почему она работает с типом Extended и не работает с Real.

Задача Какое может быть минимальное число жителей города, где кондукторы составляют строго более P%, но строго менее Q% населения? Ограничения: 0.01 ≤ P, Q ≤ 99.99. Числа P и Q могут быть заданы с точностью до сотых долей. Исходные данные Числа P и Q в десятичной записи, разделённые пробелом или переводом строки. Результат Программа должна выдать искомое число в десятичной записи. Вот собственно код program Pr; {$APPTYPE CONSOLE} var P,Q: Extended; min: Integer; i:Integer; Begin Read(P,Q); i:=0; while True do begin i:=i+1; min:=Trunc(P*i/100)+1; If min<Q*i/100 then break; End; Writeln(i); End. Помогите понять

Полный текст и комментарии »

  • Проголосовать: нравится
  • -4
  • Проголосовать: не нравится