Олимпиадные задачи (с окончившихся олимпиад), ТОЛЬКО условия и ПРОВЕРЕННЫЕ решения Опции

[AlaRic]

Внимание!
В этой теме публикуем только сами задачи и их решения... Обсуждения - в отдельных темах!!!

------------------------------------------------------------

Автобусные билеты в рулоне пронумерованы от 000001 до 999999. Составить программу, выводящую на экран количество и номера (в несколько столбиков) всех счастливых билетов в некотором диапазоне, организовав запрос начального и конечного номера билета диапазона.
Примечание: Счастливым считать тот билет, у которого сумма первых трех цифр равна сумме трех последних.

------------------------------------------------------------

На судоверфь для докового ремонта пришли пять судов А, В, С, D, Е. В доке судоверфи может находиться только одно судно. Необходимое время стоянки в доке каждого судна различно и составляет соответственно МА, МВ, МС, MD и МЕ. Составить программу, определяющую и выводящую на экран очередность постановки судов в док, при которой суммарные потери от простоя судов минимальны.

------------------------------------------------------------

Маленький заблудившийся медвежонок движется по дороге, вдоль которой на расстоянии М друг от друга растут деревья. Останавливаясь под каждым деревом, медвежонок забывает, откуда пришел, и, отправляясь через некоторое время в дальнейший путь, совершенно случайно выбирает то или иное направление движения. На каком расстоянии от первого дерева может быть медвежонок после шести этапов?

------------------------------------------------------------

В городе N домов. Найдите максимально возможное количество непересекающихся заборов, которое можно построить в этом городе, при условии, что каждый забор огораживает хотя бы один дом, а никакие два забора не огораживают одну и ту же совокупность домов.

------------------------------------------------------------

В клетках таблицы расставлены числа. Расставить в этих клетках K ферзей так, чтобы они друг друга не били и чтобы сумма чисел, ими закрываемых, была максимальной.

------------------------------------------------------------

В заданной последовательности целых чисел найти максимально длинную подпоследовательность чисел такую, что каждый последующий элемент подпоследовательности делился нацело на предыдущий.

------------------------------------------------------------

По кругу расположено N монет гербами вверх и M монет гербами вниз. Обходя круг по ходу часовой стрелки, переворачивает каждую S-тую монету. В первый раз счет начинается с герба. В каком порядке надо расставить монеты, чтобы после K ходов стало L монет, лежащих гербами вверх.

------------------------------------------------------------

Заменить буквы цифрами так, чтобы соотношение оказалось верным:
ХРУСТ*ГРОХОТ=РРРРРРРРРРР

------------------------------------------------------------

При поступлении в вуз абитуриенты, получившие двойку на первом экзамене, ко второму не допускаются. В массиве A[n] записаны оценки, полученные на первом экзамене. Подсчитать, сколько человек не допущено ко второму экзамену.

------------------------------------------------------------

Составить программу, которая формирует список L, включив в него по одному разу элементы, которые входят в один из списков L1 и L2, но в то же время не входят в другой.

[AlaRic]

Последовательность целых чисел строится следующим образом:
- первое задается (обозначим его через a),
- каждое следующее число является суммой цифр квадрата предыдущего.
Например, если a=4, то получится последовательность 4, 7, 13, 16, ...
По заданным a и n определить n-е число в этой последовательности. Известно, что a<10000 и n<1000000.

[Slam]

Телефонный номер называется «шахматным», если его цифры набираются на телефонном кнопочном номеронабирателе ходом шахматного коня. Написать программу, подсчитывающую, сколько можно набрать различных семизначных «шахматных» номеров, начинающихся с заданной цифры.

1 2 3 
4 5 6 
7 8 9 
  0  

[Ivs]

"Театр"

В театре N мест, пронумерованных целыми числами от 1 до N. Некоторые из зрителей опоздали на спектакль, поэтому после третьего звонка те зрители, которые имели билеты на неудобные места, пересели на более удобные. Опоздавшие зрители, которые пришли уже после третьего звонка, садились на первое попавшееся свободное место.

В антракте один из опоздавших зрителей решил сесть на свое место. Если его место до этого было занято, то тот, кто там сидел, пересаживался на свое место. Если и там кто-то уже сидел, то и этот зритель также вынужден был вернуться на свое место. И так далее.

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

Требуется создать программу для вычисления количества зрителей, поменявших свои места из-за опоздания одного зрителя.

Технические требования:

Входной файл: INPUT.TXT
Выходной файл: OUTPUT.TXT

Формат входных данных:

Входной файл INPUT.TXT состоит из трех строк. В первой строке содержится целое число N (N<=30000) — количество мест в зале.

Вторая строка содержит последовательность из N целых чисел, разделенных пробелами, где первое число определяет номер места в билете у зрителя, который занял место с номером 1, второе - номер места в билете у зрителя, который занял место с номером 2, и так далее. Если место было свободно, то соответствующее число равно 0.

В третьей строке содержится одно число - номер места в билете у опоздавшего зрителя, который в антракте решил пересесть на свое место.

Формат выходных данных:

Выходной файл OUTPUT.TXT должен содержать одно число — количество зрителей, поменявших свои места в антракте, включая опоздавшего зрителя.

Пример файлов входных и выходных данных:

INPUT.TXT:
10
0 2 5 3 1 0 0 0 0 0
4

OUTPUT.TXT:
3

Решение (Показать/Скрыть)

{$A+,B-,D+,E+,F-,G-,I+,L+,N-,O-,P-,Q-,R-,S+,T-,V+,X+}
{$M 16384,0,655360}

program Olymp;

var
  F1,F2 : Text;                     { Файлы I/O                        }
  i     : Integer;                  { Номер билета                     }
  A     : Array [1..30000] of word; { Массив номеров мест              }
  N     : Integer;                  { Количество мест                  }
  Count : Word;                     { Кол-во зрителей поменявших места }

begin
  Assign(F1,'INPUT.TXT');  Reset(F1);
  Assign(F2,'OUTPUT.TXT'); Rewrite(F2);
  Readln(F1,N);
  for i:=1 to N do Read(F1,A[i]);   { Заполняем массив номерами        }
  Readln(F1,i);                     { Считываем номер опоздавшего      }
  Count:=0;                         { Инициализируем счетчик           }
  while A[i]<>0 do                  { Пока место занято выполнять      }
  begin                             { -------------------------------- }
     Inc(Count);                    { Увеличиваем кол-во пересаживаний }
     i:=A[i];                       { Номер следующего зрителя         }
  end;                              { -------------------------------- }
  Writeln(F2,Count);                { Записываем результаты в файл     }
  Close(F1);                        { Закрываем файлы                  }
  Close(F2);                        { -------------------------------- }
end.

[Флогримм]

Задача "Навигатор кладоискателя"

Описание
Имеется лабиринт прямоугольной формы M на N, в котором в клетке с координатами (KLI, KLJ) зарыт клад (KLI - номер строки, KLJ - номер столбца).
Кладоискатель находится в клетке с координатами (1,1), имеет план лабиринта с указанием месторасположения клада.

Задача
Определить, какое минимальное количество стен должен разрушить кладоискатель, чтобы добраться до клада.

Входные данные:

6{m}
7{n}
4{kli}
5{klj}
0011101{0-проходимая клетка, 1 -нет}
0010101
0111110
1101011
0101110
0101010

Предлагайте свои алгоритмы!!!

пример входного файла:

6
7
4
5
0011101
0010101
0111110
1101011
0101110
0101010

Решение с пояснениями (Показать/Скрыть)

program find;
uses crt;
const
  path='d:\'; {путь к "карте"}
  filename='lab1.txt';
  SizeOfArray=100; {максимальная размерность массива}
  razd='|';

label step1;

function StrToFloat(str:string):integer;
{ действует так же, как и аналогичная в Делфи }
var code,v:integer;
begin
  val(str,v,code);
  strtofloat:=v;
end;

var
  fil:text;
  str:string;
  m, { кол-во строк }
  n, { кол-во столбцов }
  kli, { клад находится в ячейке mas[kli, klj] }
  klj,
  i, j, a,
  walls {кол-во стен (искомая величина) }
  : byte;

  mas: array[1 .. sizeofarray, 1 .. sizeofarray] of byte;

procedure draw; { прорисовка массива }
begin
  for i:=1 to m do begin
    for j:=1 to n do write(mas[i,j]:3, razd);
    writeln;
  end;
end;

begin
  textcolor(white); clrscr;
  writeln('Путь файла-карты> '+path+filename);
  assign(fil,path+filename); reset(fil);
  Writeln('Данные о лабиринте> ');
  readln(fil,m);
  gotoxy(21,2); write('Строк m=',m);
  readln(fil,n);
  gotoxy(21,3); write('Столбцов n=',n);
  readln(fil,kli);
  readln(fil,klj);
  gotoxy(21,4); write('Клад находится в ячейке: ',kli,'x',klj);

  FOR i:=1 to m do begin {считываем лабиринт из файла и записываем в массив}
    readln(fil,str);
    for j:=1 to n do mas[i,j]:=StrToFloat(str[j]);
  end;
  close(fil);
  writeln;
  writeln('Карта> ');

  draw;

  { algorithm }
  step1:

  {1}
  a:=2;
  mas[1,1]:=a;
  while (a<m*n) do begin
    for i:=1 to m do
      for j:=1 to n do begin
        if mas[i,j]=0 then begin
          if mas[i+1,j]=a then mas[i,j]:=a+1;
          if mas[i-1,j]=a then mas[i,j]:=a+1;
          if mas[i,j-1]=a then mas[i,j]:=a+1;
          if mas[i,j+1]=a then mas[i,j]:=a+1;
        end;
      end;
    inc(a);
  end;
  {\1}

  {2}
  if mas[kli,klj]<=1 then begin
    for i:=1 to m do
      for j:=1 to n do
        if (mas[i,j]=1) and
           ((mas[i-1,j]>1)or(mas[i+1,j]>1)or(mas[i,j-1]>1)or(mas[i,j+1]>1)) then
        begin
          mas[i,j]:=0;
        end;
    inc(walls);
    goto step1;
  end;
  {/2}

  {/algorithm}
  writeln;
  draw;
  writeln('Клад найден! Чтобы добраться до него надо проломать ',walls,' стен.');
end.

1 - "Идентифицируем" текущую комнату.
2 - Если в ней нету клада, тогда разрушаем стену, ограничивающую комнату(т.е. объединяем в одну две или больше граничащих друг с другом комнат) и "goto step1;" переходим к шагу 1, иначе выводим искомое значение walls;

Пояснение к шагу 1.
Пусть имеем лабиринт

 0| 0| 0| 0|
 0| 1| 0| 1|
 0| 1| 1| 1|
 0| 0| 1| 0|
 0| 1| 1| 0|
 0| 0| 1| 1|

После "идентификации" комнаты мы получим лабиринт

 2| 3| 4| 5|
 3| 1| 5| 1|
 4| 1| 1| 1|
 5| 6| 1| 0|
 6| 1| 1| 0|
 7| 8| 1| 1|

Для "идентификации текущей комнаты я использую алгоритм прохода лабиринта методом волновой трассировки"
Т.е. мы ячейке mas[1,1]:=2, а затем сканируем массив и если находим ячейку значение которой равно 0 (проходимая ячейка) и у нее в соседях есть ячейка со значением A, тогда текущей присваиваем значение А+1; увеличиваем А на 1;

Пояснение к шагу 2:
Если mas[kli,klj] имеет значение 0 или 1, тогда клад не найден, если больше, тогда найден.

Как удалить стену:
удаляем все единицы, у которых есть в соседях не единицы.

[Флогримм]

Прохождение лабиринта методом волновой трассировки(или просто волновой алгоритм)!

1) http://www.codemanual.net/main/algo/alg20.htm
Достаточно подробное объяснение. Без кода, только алгоритм.
В статье описывается метод, когда можно ходить по диагонали! во многих задачах обычно такой возможности нету, так что можно его немного переделать, учтите это.

2) http://algolist.manual.ru/games/wavealg.php - алгоритм+код

Сообщение отредактировано: Флогримм - 15.11.2004 7:34

[corazon]

------------------------------------------------------------

Игрок А выбирает натуральное число X, 1<= X <= N. Игрок В должен угадать число X при помощи вопросов вида «Число X больше или равно К?», где К – некоторое натуральное число. На каждый вопрос игрока В игрок А отвечает честно и не меняет число X. Игрок В платит игроку А за ответ «Да» - 2 руб., за ответ «Нет» - 1 руб. Определите для данного N наименьшую сумму денег Р(N), достаточную для угадывания любого числа X, 1<= X <= N. Постройте алгоритм, по которому игрок В задаст вопросы таким образом, что угадает число X и при этом заплатит не более Р(N) рублей.

------------------------------------------------------------

Лабиринт из N комнат задан таблицей соединений(матрица смежности), в которой для каждой пары комнат указано, соединены ли они коридором. Построить путь из комнаты с номером i в комнату с номером j. (реализуется с помощью алгоритма Дейкстры)

[Altair]

------------------------------------------------------------

<<Умная пчела>> (6 баллов, 1 секунда на тест)

__F
E__A
D__B
__C
В улье, изображенном на рисунке, ползает пчела. Соты улья представляют собой правильные шестиугольники, поэтому пчела может переползти из одной соты в соседнюю ней через любую из 6 граней. Каждое направление движения обозначается заглавными латинскими буквами от A до F, как показано на рисунке. При записи пути движения пчелы указывается направление движения и число последовательных переходов, совершенных в этом направлении. Так, например, 4 перехода в направлении В записываются как В4. Утром пчела начала свой путь и к вечеру оказалась в некоторой точке улья. Требуется написать программу, которая определяет, за какое минимальное число переходов пчела сможет вернуться в исходную точку, если известна полная запись маршрута. Размер улья можно считать бесконечным.

Формат входных данных:
Текстовый файл input.txt, содержащий одну строку, представляющую запись пути пчелы. Считать, что входная строка не более 80 символов и не содержит синтаксических ошибок. Между командами никакие разделители не ставятся. Число повторений, указанное после команды, находится в диапазоне от 1 до 999 включительно.
Формат выходных данных (вывод на экран):
Целое неотрицательное число - искомое минимальное число переходов
Пример 1
файл input.txt: A1B1C1D1E1
Выходные данные: 1
Пример 2
файл input.txt: A32B33D32A1
Выходные данные: 34

------------------------------------------------------------

<<Произведение дробей>> (12 баллов, 10 секунд на тест)Найти произведение N обыкновенных дробей, записав ответ в виде обыкновенной несократимой дроби.
Например, (3/8)*(2/8)*(14/9)=(7/30).
Формат входных данных:
Текстовый файл input.txt, в первой строке которого записано натуральное число N (1М<10000). В каждой из последующих строк указана пара натуральных чисел - числитель и знаменатель одной дроби. Данные таковы, что числители и знаменатели исходных дробей и числитель и знаменатель ответа после его сокращения не превосходят 30 000.
Формат выходных данных (вывод на экран):
Два натуральных числа - числитель и знаменатель ответа.
Пример:
файл input.txt
3 8
2 5
14 9
Выходные данные:
7 30

------------------------------------------------------------

«Часы» (12 баллов, 1 секунда на тест)
Каждая цифры в электронных часах изображена некоторыми из 7 штрихов. Штрихи пронумерованы сверху вниз, слева направо, как показано на рисунке. Цифры получаются следующими штрихами: 0-1,2,3,5,6,7; 1-3,6; 2-1,3,4,5,7; 3-1,3,4,6,7; 4-2,3,4,6; 5-1,2,4,6,7; 6-1,2,4,5,6,7; 7-1,3,6; 8-1,2,3,4,5,6,7; 9-1,2,3,4,6,7. Часы выпущены фирмой «VREMENI.NET», и поэтому в некоторых цифрах часть штрихов пропала. По имеющемуся изображению цифр на часах определить, какое время часы могли бы показывать. Все возможные варианты вывести в порядке возрастания времени.
Формат входных данных:
Текстовый файл input.txt содержит четыре строки (часы и минуты) по семь символов в каждой. Один символ может быть либо нулем либо единицей: 0 - соответствующий штрих в цифре не горит, 1 - штрих в цифре горит. Например, последовательность 1100010 означает, что горят штрихи 1, 2 и 6.
Формат выходных данных:
Текстовый файл output.txt, содержащий строки в формате ЧЧ:ММ - возможное время в порядке возрастания.
Пример:
файл input.txt:
1110111
1110111
1110111
1110111
файл output.txt:
00:00
00:08
08:00
08:08

------------------------------------------------------------

«Бассейн» (15 баллов, 1 секунда на тест)
Бассейн емкостью 500 м3 наполняется из трех труб A, В, С со скоростями потоков 20, 40 и 100 м3/ч соответственно. Слив производится через три стока D, Е, F с пропускными способностями 30, 50 и 80 м3/ч соответственно, либо через естественный перелив. Открытие и закрытие труб/стоков производится только на границе некоторого часа. Имеется журнал открытия и закрытия труб и стоков за сутки, при этом одна и та же труба/сток может за сутки открываться (закрываться) неоднократно. В один и TOT же час возможно несколько операций (над различными трубами/стоками). Определить, в течении какого количества часов (с точностью до 0.001 часа) вода переливалась через край бассейна при условии, что в 0 часов бассейн был пуст.
Формат входных данных:
В первой строке файла input.txt записано натуральное число N - количество записей в журнале. В каждой из N последующих строк указано целое число - номер часа и через пробел название трубы/стока. Если труба/сток была закрыта - она открывается, если открыта - закрывается.
Формат выходных данных (вывод на экран):
Действительное число с тремя десятичными знаками после запятой - количество часов, в течение которых
вода переливалась через край бассейна.
Пример:
файл input.txt:
4
0 A
5 С
10 F
11 С
Выходные данные:
2.667

------------------------------------------------------------

<<Стираем числа>> (25 баллов, 1 секунда на тест)
На доске записаны подряд натуральные числа от 1 до N (N < 1 000 000 000). Сначала стирают все нечетные числа. Из оставшихся стирают все числа, стоящие на четных местах, затем снова стирают все числа, стоящие на нечетных местах, и так далее, пока не останется одно число. Какое это число?
Пример:
Входные данные: 10
Выходные данные: 6

------------------------------------------------------------

<<Строки>> (30 баллов, 1 секунда на тест)
На вход подаются строки A и В. Необходимо преобразовать строку A в строку В с минимальным суммарным штрафом, который определяется следующим образом: a) удаление символа из строки A - х баллов; б) вставка символа в строку A - у баллов; в) замена символа в строке A на любой другой символ - z баллов. Напишите программу, определяющую минимальный суммарный штраф при преобразовании строки A в строку В.
Формат входных данных:
Файл input.txt, содержащий две строки A, В (длины строк < 255) и три целых неотрицательных числа х, у, z - по одному числу в строке.
Формат выходных данных (вывод на экран):
Одно целое неотрицательное число - минимальный суммарный штраф.
Пример:
файл input.txt:
мама
папа
1
1
10
Выходные данные:
4

[Jahnerus]

Нус! ... раз можно постить свои реализации ... то почему бы и нет!

<<Стираем числа>> (25 баллов, 1 секунда на тест)

Реализация (Показать/Скрыть)

uses crt;

function main(n:longint):longint;
var
  step,first,last:longint;
  b:boolean;
begin
  step:=2;
  first:=1;
  last:=n;
  b:=false;
  while first<>last do begin
    if b then begin
      if (last-first+step div 2) mod step=0 then last:=last-step div 2;
    end
    else begin
      if (last-first) mod step=0 then last:=last-step div 2;
      inc(first,step div 2);
    end;
    step:=step*2;
    b:=not(b);
  end;
  main:=first;
end;

begin
  clrscr;
  writeln(main(10));
  readln;
end.

Сообщение отредактировано: volvo - 20.03.2010 14:34

[LammerzAttack]

Имя входного файла: divider.in
Имя выходного файла: divider.out
Количество тестов: 30
Ограничение по памяти: 1 Мб
Ограничение по времени: 1 с

Когда Константин Михайлович Столбов был еще маленьким, он любил играть в интересную игру. Кто-то из его друзей рисовал на доске какое-то число, а Константин Михайлович пытался придумать все такие пары чисел, что их сумма равна данному числу, причем второе число получается из первого вычеркиванием одной цифры. Первое число имеет как минимум две цифры и не должно начинаться с нуля. Второе число должно иметь на одну цифру меньше и может начинаться с нуля.

Формат входного файла
Во входном файле записано число 9 < N < 1000000001

Формат выходного файла
На первой строве число искомых пар. Далее все возможные пары чисел, подходящих под условие задачи, в порядке возрастания первого числа, по одной паре в каждой строке. Пары должны выводитьсяв формате X + Y = N с пробелами между числами и знаками! В конце каждой строки должен стоять символ перевода строки.

Пример
divider.in
302

divider.out
5
251 + 51 = 302
275 + 27 = 302
276 + 26 = 302
281 + 21 = 302
301 + 01 = 302

[LammerzAttack]

Имя входного файла: maze.in
Имя выходного файла: maze.out
Количество тестов: 10
Ограничение по памяти: 1 Мб
Ограничение по времени: 10 с

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

Гвардия Принца Пришельцев палит в меня с балкончиков, я тоже стреляю - наугад. "BFG-9000" выжигает три зеркала одним залпом. Помещение наполнено серебряным дымом. Пули колотят по броне, сбивая меня на пол. Стреляю в падении, вращаюсь на спине, словно в забытом танце своей юности - "брейке", еще два раза стреляю. Три зеркала, три зеркала, три зеркала...

(Сергей Лукьяненко "Лабиринт Отражений")

BFG-9000 уничтожает три соседних балкончика с монстрами на них за один выстрел. После выстрела выжившие монстры ранят Леонида (главного героя повести) - 1 процент жизни каждый. Далее следует новый выстрел Леонида, новый выстрел монстров и тд, пока все монстры не погибнут. Необходимо добиться того, чтобы Леонид получил минимальные повреждения в этой схватке.

Формат входного файла
В первой строке число 2 < N < 17, количество балкончиков, на который монстры держат круговую оборону. Вторая строка содержит N натуральных чисел - количество монстров на соответствующем балкончике (не менее одного и не более 100 на каждом)

Формат выходного файла
Одно число - какое минимальное повреждение может получить Леонид.

Пример
maze.in
7
3 4 2 2 1 4 1

maze.out
9

[LammerzAttack]

Вот условие
Имя входного файла: polymer.in
Имя выходного файла: polymer.out
Ограничение по памяти: 1 Мб
Ограничение по времени: 10 с

Недавно российские учёные изобрели новый, революционный материал — сверхпрочные полимерные волокна! Их область применеия настолько широка, что пока даже сами учёные не в состоянии представить в каких областях производства они могут пригодится. Но пока учёные решают новую проблему, военные уже утащили новинку себе на вооружение и вовсю производят сверхпрочные защитные костюмы из сверхпрочных полимерных волокн.

Однако при тестировании на полигонах они столкнулись с новой проблемой — оказалось что при пошиве костюма молекулы одной цепочки начинают взаимодействовать друг с другом и взависиомсти от обхвата груди, ширины талии и бедёр солдата прочность костюма резко меняется. Учёные установили, что атомы в полимерных цепочках могут находиться в одном из m состояний (от 0 до m-1, состояния выражаются только целыми числами), где m — число характеризующее волокнистую цепочку полимера. Кроме того, теоретику Обоеву Рулону удалось доказать, что костюм остаётся прочным только если представив последовательность состояний атомов в цепочке в виде числа записанного в системе с основанием m оно делится на число p (число характеризующее обхват груди, ширину талии и бёдер солдата).

Ваша задача помочь учёным написать программу, которая будет определять можно ли из данной цепочки пошить для данного солдата прочный костюм.
Формат входного файла

В первой строке целые числа p (1 < p < 256) и m (26 < m < 359). В следующей строке через пробелы записаны состояния всех атомов в цепочке. Кол-во атомов в цепочке не превышает 2000000.
Формат выходного файла

YES, если из такого волокна можно сшить прочный костюм солдату. NO, если нельзя.
Пример
polymer.in

2 3
1 1
polymer.out
YES

В примере m меньше 26, так как это пример. Я не понимаю, что здесь надо сделать. Объясните пожалуиста смысл условия.

Сообщение отредактировано: LammerzAttack - 14.04.2005 20:12

[NightPaladin]

Вот подумал над позапрошлой задачей. Извини забыл вывод в файл - ну так уж это - приспособишь

Реализация (Показать/Скрыть)

program asd;
Uses
     CRT;
var
     num, count, i    :  LongInt; { <--- вместо Integer }
     st   :  String;
     by,num2, count2  :  Byte;
     ch,ch2 :  Integer;
(*______________________________ *)
     vrem   : Integer;
begin
     ClrScr;
             WriteLn('Input number:');
             ReadLn(num);

             For  count:= 12 to num-1 do
                  begin
                        Str(count,st);
                        by:= Length(st);
                        For count2:= 1 to by do
                            begin
                                 Delete(st, count2, 1);
                                 Val(st, num2,i);
                                 vrem:=num2 + count;

                                 If vrem = num then
                                    WriteLn(num2,'+',count);
                            end;
                  end;
     ReadKey;
end.

Вообще честно говоря решил не сам рациональным способом - скорее всего, т.к. оный наверное вообще не рассчитан на перевод в строку... но главное решение...

Я исправил тип с Integer на LongInt, чтобы программа могла работать с большими числами (как указано в условии)

Сообщение отредактировано: volvo - 20.03.2010 14:36

[kuzya]

Задача:
Дано выражение x*x+y*y=z*z (так называемые Пифагоровы тройки).
Вводится число N (N<=2000), причём x<=N, y<=N. Найти количество троек; все x, y, z, соответствующие данным условиям. X, Y, Z, N - целые положительные числа.

(Ограничение по времени 5 сек.)

Пример:
Ввод:
4
Вывод:
1
3 4 5

Решение задачи (Показать/Скрыть)

program troiki;
uses crt;
var
  c, cmax, summ, maxsumm: real;
  n,q: integer; a, amax, b, bmax: longint;
begin
  clrscr;
  write('n=');read(N);
  for a:=1 to n do begin
    for b:=1 to n do begin
      if a<b then begin { добавление этой строки уменьшит время вычисления }
        c:=sqrt(sqr( a ) + sqr( b ));
        if frac( c ) = 0 then begin
          summ:=(a+b+c);
          if summ>maxsumm then begin
            maxsumm:=summ;
            amax:=a; bmax:=b; cmax:=c;
          end;
          q:=q+1;
        end;
      end;
    end;
  end;
  writeln;
  writeln(q);
  writeln(amax,' ',bmax,' ',trunc(cmax));
  writeln(trunc(maxsumm));
  readkey;
end.

Однако при N = 1700 вычисление длится больше 5 сек.

[kuzya]

Задача: Дано натуральное число К. Напечатать К-ую цифру последовательности 123456789101121314..., в которой выписаны все подряд натуральные числа. (Последовательность в ЭВМ не вводить)

Есть решение (Показать/Скрыть)

program chisla;
uses crt;
var
  i, n, i1: longint;
  s, d: string;
begin
  clrscr;
  read(n);
  for i:=1 to n do begin
    str(i,s);
    if (length(d))<=n then d:=d+s;
  end;
  writeln;
  writeln(d);
  writeln(d[n]);
  readkey;
end.

Добавлено (Volvo):
Чтобы не было проблем с переполнением строки при больших K, эту задачу лучше решать на основе инварианта.

Первые 9 цифр - это однозначные числа (1 .. 9), вторые 90 - двухзначные (10 .. 99), дальше 900 трехзначных (100 .. 999), и т.д.

By Volvo (Показать/Скрыть)

function get_digit(n: longint): char;
var
  i: longint;
  digits: byte;
  start_of, maximal: longint;
  num_of_n, num_of_digit: integer;
  s: string;
begin
  digits := 1;
  start_of := 0;

  maximal := 9;
  while n > digits * maximal + start_of do begin
    inc(digits); maximal := maximal * 10;
    inc(start_of, pred(digits) * (maximal div 10));
  end;
  maximal := maximal div 10;

  dec(n, start_of);
  num_of_n := (n div digits) + byte((n mod digits) <> 0);
  num_of_digit := n - digits * pred(num_of_n);

  n := 1;
  for i := digits downto 2 do n := n * 10;
  str(n + pred(num_of_n), s);
  get_digit := s[num_of_digit];
end;

Completed in 0.046999845653772 seconds

**********

By klem4 (Показать/Скрыть)

function DigitInfo(const k: LongInt): Char;
var
  temp, curr, digit_len, digit_owner_number, digit_group: LongInt;
  digit_pred_group: LongInt;
  s: String;
begin
    digit_group := 9;
    digit_pred_group := 0;
    digit_len := 1;
    temp := 9;

    while (k > digit_group) do begin
      inc(digit_len);
      temp := 9 * digit_len * round(exp(pred(digit_len) * ln(10)));
      digit_pred_group := digit_group;
      digit_group := temp + digit_group;
    end;

    digit_owner_number := (k - digit_pred_group - 1) div digit_len + 1;
    str(round(exp((digit_len - 1) * ln(10))) + digit_owner_number - 1, s);
    DigitInfo := s[k - (digit_pred_group + digit_len * (digit_owner_number - 1) + 1) + 1];
end;

var
  k: Integer;

begin
  readln(k);
  writeln(DigitInfo(k));
end.

Completed in 0.078000104986131 seconds

**********

By hardcase (Показать/Скрыть)

function GetDigit(k: integer): integer;
var counter: integer;     // счетчик натуральных чисел
    number: integer;      // текущее разбираемое число
    needNewNumber: boolean; // флаг - "завершился ли разбор числа?"
    maxDecimalMask: integer;  // максимальная маска десятичного разряда
    nextDecimalMask: integer; //  maxDecimalMask * 10
    decimalMask: integer;     // текущая маска десятичного разряда

    procedure Init;
    begin
        counter := 0;
        maxDecimalMask := 1;
        nextDecimalMask := maxDecimalMask * 10;
        needNewNumber := true;
    end;

    function GetNextDigit: integer;
    var digit: integer;
    begin
        // получаем следующее натуральное число
        if needNewNumber then begin
            needNewNumber := false;
            inc(counter);
            number := counter;
            if (counter mod nextDecimalMask) = 0 then begin
                maxDecimalMask := nextDecimalMask;
                nextDecimalMask := maxDecimalMask * 10;
            end;
            // сбрасываем маску
            decimalMask := maxDecimalMask;
        end;
        // получаем число в разряде
        digit := number div decimalMask;
        number := number mod decimalMask;
        decimalMask := decimalMask div 10;
        // если маска нулевая, то мы разобрали число
        if decimalMask = 0 then
            needNewNumber := true;
        // возвращаем результат
        GetNextDigit := digit;
    end;

var i: integer;
    digit: integer;
begin
    Init;
    // тупо перебираем k-разрядов
    digit := 0;
    for i := 1 to k do
        digit := GetNextDigit;
    // возращаем результат
    GetDigit := digit;
end;

Completed in 30.46800009906292 seconds

**********

By Malice (Показать/Скрыть)

function test (x:longint): char;
var i:longint;
s:string;
begin
i:=0;
repeat
inc (i); str (i,s);
if x<=length(s) then begin
test:=s[x]; x:=0; end else
x:=x-length(s);
until x=0;
end;

Completed in 58.29700010363013 seconds

Сообщение отредактировано: volvo - 20.03.2010 14:43

[Mora]

Задачки про файлы:

------------------------------------------------------------

Память на жестком диске компьютера разбита на параграфы, каждый размером 16 Кб. Файл может занимать только целое кол-во параграфов, даже если параграф занят не весь, то он все равно отдается файлу полностью. Во входном файле в одной через пробел указаны размеры файлов в байтах. Определите объем, занимаемый директорией на жестком диске.

------------------------------------------------------------

В файле задано некоторое кол-во цифр N (N<=10000). Цифры расположены в одне строчку и разделены пробелами. Требуется определить, можно ли из данных цифр составить N-значное простое число (нужно использовать все заданные числа и только их). Если возможно составить несколько N-значных чисел, программа должна определить их все. В первой строке выходного файла должно быть указано кол-во простых чисел, далее в каждой строке по одному числу.

[Nosferatu]

Площадь прямоугольников
Дано N прямоугольников со сторонами, параллельными осям координат. Требуется пределить площадь фигуры, образованной объединением данных прямоугольников.
Ввод из файла rectarea.in В первой строке находится число прямоугольников - N. Затем идут N строк, содержащих по 4 числа: X1, X2, Y1, Y2 - координаты двух противоположных углов прямоугольника.
Вывод в файл rectarea.out Вывести одно число - площадь фигуры

Пример
Ввод
2
1 1 3 3
2 2 4 4
Вывод
7

[minkod]

1. В трехмерном пространстве задан куб с ребром длиной 1.
Одна из вершин в точке с координатами, например,(0.0.0), а противоположная с координатами (1,1,1). По двум введенным вершинам определить, находятся ли они на одном ребре куба или на одной его грани.

2. По ребрам куба ползут тараканы. Все они ползут из вершины (000) в вершину (111) так, что каждый из них проползает при этом три ребра. Найти самое «истоптанное» ребро.

3. Нужно расшифровать длинное секретное донесение.
Таблица кодировки неизвестна, зато известно, что каждый символ закодирован восемью битами.

4. Вводится последовательность целых чисел (в диапазоне от -32000 до 32000). Требуется разбить их на пары так, чтобы произведения чисел в парах были одинаковы.
Входные данные: Вводится N (количество чисел), 1<=N<=100. Затем вводятся N целых чисел.
Выходные данные: Если разбить на пары можно, то выдать произведение чисел в паре (все варианты), иначе - сообщение "Нет решения".

5. Есть N лампочек и М переключателей, каждый из которых какие-то лампочки переключает, а какие-то нет.
Сначала часть лампочек включена. Договоримся горящие лампочки обозначать I. а выключенные - 0. Для переключателей будем писать I, если переключатель меняет состояние данной лампочки, и 0, если не меняет. Тогда любой переключатель можно представить строкой из N нолей и единиц. Начальное и конечное состояние лампочек также закодируем строкой из 0 и I. «Применение» переключателя к лампочкам приводит к тому. что включенные лампочки становятся выключенными, а выключенные включенными (естественно, это справедливо только для лампочек, к которым есть доступ от этого переключателя) Напишите программу, которая определяет, какие переключатели нужно применить, чтобы лампочки перешли в конечное состояние.
Входные данные: Вводятся числа N и M (1<=N<=50,1<=M<=50).
Вводится строка, характеризующая конечное состояние лампочек. Вводится M строк, характеризующих переключатели.
Выходные данные: Номера переключателей , которые нужно применить, причем каждый переключатель можно применить не более 1 раза, либо сообщение "Нет решения".

[hardcase]

Брутальня задача с контеста в CBOSS, когда-то пытался решить - не вышло.

"Миное поле чудес" находилось на окраине Тьмускорпионии. Его карта представляла собой прямоугольник из клеток. В каждой клетке может находится либо не находится одна мина. На данный момент поле было частично исследовано - то есть про некоторые клетки известно, есть там мина или нет. При отсутствии мины в клетке известно общее кол-во мин в соседних (по стороне и углу) клетках. Известно также общее кол-во мин на поле.
В данной задаче по заданной начальной ситуации вы должны определить вероятности нахождения мин в неоткрытых клетках. Под вероятностью того, что в данной клетке находится мина, понимается отношение количества возможных вариантов расстановки мин, при которых в данной клетке находится мина, к общему количеству вариантов. При подсчёте кол-ва вариантов, мы должны считать только те расстановки, которые согласуются с заданной начальной ситуацией.
Гарантируется, что начальная ситуация задана корректно, т.е. существует по крайней мере одна расстановка мин, с ней согласующаяся. Также гарантируется, что кол-во клеток, соприкасающихся с открытыми клетками, не превышает 25.

Input: В первой строке файла записаны через пробел три целых числа N, M, K. M и N - размер поля (2<=N, M <= 20), а K - общее количество мин (0 <= K <= N x M)
В последующих N строках задаётся само поле. Каждая строка - M символов, каждый из которых описывает клетку поля. Символы '0'..'9' обозначают кол-во мин в соседних клетках. Прописная латинская 'X' - неоткрытая клетка. 'M' - клетка, в которой точно есть мина.

Output: В первой строке выходного файла всё те же N M K, в последующих - N строк по M вещественных чисел, каждое из которых - вероятность нахождения мины в соответствущей клетке.

[Bill Gates]

ФАЙЛОВЫЙ МЕНЕДЖЕР
Имя входного файла: far.in
Имя выходного файла: far.out
Петя работает над очень большим проектом. Проект содержит N файлов. В процессе работы Пете часто приходится просматривать и редактировать файлы. Для ускорения работы Петя использует файловый менеджер FAR Menager, который отбражает список имен файлов проекта в некотором порядке.
В текущей версии FAR Manager'а для перемещения по списку имен файлов есть следующие возможности:
1) Можно нажать клавишу "вниз", при этом курсор перемещается на следующий файл в списке. Для последнего файла в списке следующим считается первый.
2) Можно нажать клавишу "вверх", при этом курсор перемещается на предыдущий файл в списке, для первого файла предыдущим считается последний.
3) Можно нажать клавишу "Alt" и, удерживая ее, набрать последовательность латинских букв. После этого клавишу "Alt" следует отпустить, и в этот момент курсор переместится на ближайший файл, имя которого начинается с заданной последовательности символов. Ближайший файл - это файл, на который можно переместиться за наименьшее количество нажатий клавиши "вниз". Если заданная последовательность является началом имени текущего файла, или файла, имя которого начинается с этой последовательности, не существует, то курсор остается на месте.
Первая и вторая из описанных возможностей файлового менеджера требуют по одному нажатию на клавиши, а третья - одного клавиши "Alt" плюс нажатий, равное длине набранной последовательности латинских букв.
Файлы пронумерованы от 1 до N в порядке их следования. После загрузки FAR Manager'а курсор находится на первом файле.
Петя знает, что ему придется редактировать файл с номером a[1], затем с номером a[2] и так далее, а последним - файл с номером a[k]. В последовательности a[1], a[2], ..., a[k] один и тот же номер может встечаться несколько раз. При каждом перемещении от одного файла к другому Петя хочет нажимать как можно меньше клавиш.
Требуется написать программу, которая выдает искомую последовательность нажатий клавиш.

ФОРМАТ ВХОДНЫХ ДАННЫХ
В первой строке входного файла записано целое число N (1 <= N <= 1000) - количество файлов в проекте.
В следующих N строках записаны имена файлов, по одному в каждой строке. Файлы перечеслены в том порядке, в котором они отображаются файловым менеджером. Имена состоят только из строчных латинских букв. Длина каждого имени не превосходит 2000 символов. Все имена файлов различны.
Далее в следующей строке записано целое число k (1 <= k <= 10).
Последняя строка входного файла содержит k целых чисел a[1], a[2], ..., a[k] (1 <= a <= N) - номера редактируемых файлов. Редактирование файлов выполняется в том порядке, в котором они встречаются в последовательности a[1], a[2], ..., a[k].

ФОРМАТ ВЫХОДНЫХ ДАННЫХ
Выходной файл должен содержать описание искомой последовательности нажатий клавиш в виде k блоков информации:
* Первый блок информации описывает перемещение от файла с номером a[1] к файлу с номером a[2].
* Второй блок информации описывает перемещение от файла с номером a[2] к файлу с номером a[2].
* ...
* k-ый блок информации описывает перемещение от файла с номером a[k-1] к файлу с номером a[k].
Каждый блок информации выглядит следующим образом.
В первой строке блока записывается число L - наименьшее количество нажатий клвиш, необходимое для перемещения от очередного файла последовательности к следующему.
Следующие L строк блока описывают нажаимаемые клавиши. Каждая из строк содержит описание одной клавиши:
* Если нажимается клавиша "вниз", то в строке записывается слово down
* Если нажимается клавиша "вверх", то в строке записывается слово up
* Если нажимается клавиша "Alt", то в строке записывается слово Alt
* При нажатии клавиши с латинской буквой выводится соответсвующая ей латинская буква
Если существует несколько оптимальных вариантов перемещения, то требуется вывести любой из них.

ПРИМЕРЫ
========== ==========
far.in far.out
========== ==========
6 1
submit up
monitor 3
monitorx Alt
monyator m
subversion down
sub 0
5 2
6 3 3 5 2 down
down
2
Alt
m
========== ==========
8 3
abc Alt
abv a
abba u
test 2
auvto down
ioi down
olympiad
2
4 6
========== ==========