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

[Xorian]

Подсчитать число двоичных N-значных натуральных чисел (N<36). в каждом из которых нет трех единиц идущих подряд, а незначащие нули в записи чисел отсутствуют.
Ваша программа должна запросить значение N; найти и сообщить число N-значных двоичных чисел без трех единиц подряд.
Пример: Исходные данные: 4 Ответ: 6 (Имеются в виду числа 1000, 1001,1010, 1011, 1100, 1101)

Это задача на тему динамического программирования. Суть решения писать не буду, а код собственно вот:

var
  a: array [1..35] of longint;
  n, i: longint;
begin
  readln (n);
  a[1]:=1; a[2]:=2; a[3]:=3;
  for i:=4 to n do a[i]:=a[i-3]+a[i-2]+a[i-1];
  writeln (a[n]);
end.

[АНГЕЛ]

Пятый Белорецкий турнир по информатике
Покажите решение, пожалуйста
A. Почта
На станцию Белорецк прибыл почтовый поезд с письмами желающих участвовать в Белорецком турнире. Из достоверных источников начальник станции узнал, что в одном из вагонов во все конверты вложено по одному грамму суперзаразных микробов. К счастью, перед въездом на станцию из каждого вагона было взято некоторое число писем, и вся пачка взвешена на сверхточных весах. Выясните, можно ли по этим данным узнать, в каком вагоне находятся зараженные письма.
Входные данные:
В первой строке количество вагонов и масса выбранных писем, во второй – для каждого вагона по порядку указано количество выбранных из него писем.
Выходные данные:
Порядковый номер вагона с зараженными письмами или слово "IMPOSSIBLE", если выявить такой вагон невозможно.
Пример входных данных:
5 122
1 2 0 4 5
Пример выходных данных:
2
Технические ограничения: Любое чистое письмо весит 10 грамм, состав поезда не превышает 50 вагонов, в вагоне помещается не более 1000000 писем.

B. Контрольная.
Учитель провел контрольную работу. Ученики сидели за одним длинным столом. После контрольной ученики выходили из-за стола по одному, каждый раз выходил один из сидящих с краю, подходил к столу учителя и клал свою тетрадь сверху стопки или подсовывал ее вниз. Выясните, сколькими различными способами при этом могло получиться, что тетради легли в алфавитном порядке фамилий их владельцев.
Входные данные:
В первой строке количество учеников, в следующих строках – их фамилии в порядке следования за столом.
Выходные данные:
Найденное количество способов.
Пример входных данных:
3
ИВАНОВ
СИДОРОВ
ПЕТРОВ
Пример выходных данных:
3
Технические ограничения: В классе не более 50 российских учеников, среди которых нет однофамильцев.
Примечание: Способы считаются различными, если они различаются порядком складывания тетрадей (кто именно клал тетрадь i-м по счету).

C. Пары.
В клуб «Кому до 100» собрались одинаковое количество мужчин и женщин. Надо подобрать пару каждому мужчине так, чтобы сумма разниц в росте мужчины и женщины в паре была наименьшей. Вместимость клуба – 100 человек.
Входные данные:
В первой строке количество людей, во второй – список ростов мужчин, в третьей – список ростов женщин. Каждый рост не более 255 целых сантиметров.
Выходные данные:
Наименьшая сумма разниц в росте.
Пример входных данных:
6
180 150 205
150 180 100
Пример выходных данных:
105

D. Хакер.
Хакер Вася сконструировал аппарат, который может перепрограммировать телефонные пластиковые карточки, изменяя количество оставшихся минут разговора. Помогите Васе выяснить, какую наибольшую сумму времени разговора он может получить из имеющихся у него карточек.
Входные данные:
В первой строке список чисел (время в целых минутах) в порядке возрастания, которые аппарат может изменить, во второй строке – список чисел, в которые преобразуется соответствующее время из первой строки, в третьей – список минут разговора на имеющихся у Васи карточках.
Выходные данные:
Наибольшая сумма времени разговора.
Пример входных данных:
1 2 5
2 3 1
2 5
Пример выходных данных:
8
Технические ограничения: Емкость любой карточки – не более часа, для проведения испытаний аппарата Вася смог достать не более 100 карточек.

E. Телепортация.
Знайка изобрел космический корабль новейшего типа, который может только телепортироваться. Одна телепортация занимает 1 минуту и перемещает корабль ровно на P парсеков. Теперь коротышки во главе со Знайкой собираются слетать до Альфы Центавра, до которой R парсеков. Помогите Знайке рассчитать наименьшее время, за которое они смогут добраться до цели.
Входные данные:
В одной строке – натуральные числа P и R, не превосходящие 10000.
Выходные данные:
Наименьшее время в минутах.
Пример входных данных:
3 5
Пример выходных данных:
2

[Lapp]

Игра с калькулятором

В калькулятор вводится натуральное число К и нажимается клавиша "+". Калькулятор все еще показывает К. Цель игры: получить на экране число, состоящее из одинаковых цифр. Для ее достижения можно производить только одно действие - нажимать на клавишу "=" (возможно, 0 раз). После первого нажатия получается результат К+К, после очередного нажатия результат увеличивается на К. Требуется определить, удастся ли достичь цели, а если удастся, то какое число, состоящее из одинаковых цифр, будет получено первым. Количество отображаемых калькулятором цифр считать неограниченным, время работы батареек - тоже.
Ограничения: 1<=K<=999, время 1с.
Вводится одно число - К.
Вывести если цели достичь невозможно "No", если возможно, вывести два числа через пробел: цифру, из которой состоит искомое число, и количество цифр в числе.

Пример.
ввод№1
37
вывод№1
1 3

ввод№2
25
вывод
No

Решение: основано на алгоритме деления 'уголком' (Показать/Скрыть)

var
  i,j,k,m,n,a: integer;
  c,d: byte;
  r: array[1..999]of boolean;

begin
  ReadLn(k);
  c:=0;
  m:=MaxInt;
  for d:=1 to 9 do begin
    for j:=1 to k do r[j]:=false;
    a:=d;
    n:=1;
    repeat
      r[a]:=true;
      while a<k do begin
        a:=a*10+d;
        Inc(n)
      end;
      while a>=k do a:=a-k
    until (a=0) or r[a];
    if a=0 then if n<m then begin
      c:=d;
      m:=n
    end
  end;
  if c=0 then WriteLn('No') else WriteLn(c,' ',m)
end.

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

function solve(const k: integer): longint;
var
  i, count: byte;
  n, value: longint;
  found: boolean;
begin
  found := false;
  i := 1;
  while not (found) and ( i < 10 ) do begin
    n := 10;
    value := i;
    count := 1;
    while not(found) and (n <= 1000000) do begin
      inc(count);
      inc(value, i * n);
      found := value mod k = 0;
      if not found then n := n * 10;
    end;
    if not found then inc(i);
  end;
  if found and ( value <> k ) then writeln(i, ',', count) else writeln('no');
end;

var
  k, v: longint;

begin
  {* for k := 1 to 999 do *}
  k := 123; 
  solve(k);
end.

[Witaliy]

Задание
Однажды Петрику поручили проверить надежность военного гарнизона. А именно надежность его инфраструктуры. Инфраструктура гарнизона - это система дорог, которые соединяют тайные объекты. Надежность гарнизона - это минимальное количество взрывчатки, необходимое для того, чтобы взорвав некоторые дороги, существовали два тайных объекта таких, что невозможно было бы добраться с одного объекта до другого используя только дороги.
Входные данные
Вам задана структура гарнизона - в первой строке N,m - к-сть тайных объектов и количество дорог соответственно, в следующих M строках описания дорог в виде f l c - объекты, которые соединяет дорога и количество взрывчатки, которая необходима для ее уничтожения, это количество взрывчатки для одной дороги не будет превышать 1000. Все дороги двусторонние. Количество объектов не превышает 50, а количество дорог 10000. В гарнизоне ни одна дорога не соединяет секретный объект сам с собой.
Выходные даны
Вам нужно вывести надежность данного гарнизона.
Пример введения 1

3 3

1 2 1

2 3 2

1 3 1

Пример выведения 1

2

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

[passat]

Вот тут много задач на любой вкус.

<ссылка удалена>

Приветствуются все решения.

[Lapp]

Вот тут много задач на любой вкус.

1. В этой теме публикуются задачи в явном виде и их решения.
2. Формат .doc запрещен, см. Правила.

Если хочешь обсудить эти задачи - создай другую тему. Если просто хочешь показать ссылку - пость в раздел Ссылки (например. в тему Сайты с олимпиадными задачами )

[ZeroQ]

"Проще простого"

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

Вход:файл input.txt, в котором записано единственное число N
Ограничения: 1<N≤30000
Выход: файл output.txt, содержащий единственное число (минимальное количество групп)
Пример:
input.txt 18
output.txt 3

Примечание к примеру: числа от 1 до 18 можно разбить на три группы с нужным свойством
(например, 1+3+4+5+6+18, 2+7+8+9+10+11+12+13+14+17 и 15+16 с суммами 103, 37 и 31), на меньшее число групп, как легко показать, нельзя.


Добавлено через 6 мин.
"Острова"
В океане расположен архипелаг из N островов, каждый из которых имеет форму выпуклого многоугольника. Острова не соприкасаются и не пересекаются. Эти острова необходимо соединить между собой мостами так, чтобы от любого острова архипелага можно было добраться до любого другого. Каждый мост должен соединять пару островов, при этом суммарная длина мостов должна быть минимальной.

Вход: файл input.txt, имеющий следующую структуру: в первой строке входного файла записано число N – количество островов в архипелаге. Далее идет N строк с описанием островов. В каждой строке описывается один остров, который задаётся числом вершин (первое число строки) и далее их координатами в порядке обхода по часовой стрелке (у каждой вершины первой идет абсцисса, а второй - ордината). Координаты внутри строки разделяются пробелами.
Ограничения: число N – натуральное от 2 до 50 (включительно), для каждого острова число вершин не превосходит 20, все координаты – целые числа, не превосходящие по модулю 30000.
Выход: файл output.txt, содержащий два числа (по одному в строке), первая строка ¬- число: количество мостов; второе строка - число: суммарная длина мостов с точностью до 0.001

Пример 1:
Входной файл input.txt содержит:
2
4 –2 –2 –2 2 2 2 2 –2
3 3 –2 3 2 6 0
Результат (файл output.txt):
1
1
Пример 2:
Входной файл input.txt содержит:
3
4 –2 –2 –2 2 2 2 2 –2
3 -3 0 –5 –1 –5 1
3 6 –5 8 –4 8 -5
Результат (файл output.txt):
2
6

[Лисенок]

Здравствуйте, у меня есть любопытная задача без решения. На первый взгляд кажется довольно легкой, но это только маскировка) Итак, задача про Боулинг. Выполняется только в Паскале.
Цель при игре в боулинг - сбить шаром максимальное количество кеглей. Партия в этой игре состоит из 10 туров. Задача игрока - сбить все 10 кеглей в каждом туре. Для этого игрок может совершить 2 броска шара, за исключением:
- если 10 кеглей сбиты первым броском, то второй бросок не совершается;
- если 10 кеглей сбиты первым броском в десятом туре, то игроку предоставляются два призовых броска, а если двумя бросками - один.
Количество очков в каждом туре равно количеству сбитых кеглей, кроме двух бросков, называемых "Strike" и "Spire".
Strike: игрок сбивает 10 кеглей первым броском, очки в этом туре начисляются из расчета: 10 + сумма очков за два предыдущих броска.
Spire: игрок сбивает 10 кеглей двумя бросками, очки в этом туре начисляются из расчета: 10 + сумма очков за один последующий бросок.
Результат партии складывается из результатов всех 10 туров.
Требуется написать программу, которая определит количество набранных игроком очков.

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

Входной файл INPUT.TXT содержит в первой строке одно натуральное число, определяющее кол-во совершенных бросков. Вторая строка содержит натуральные числа(разделенные пробелом), обозначающие количество сбитых кеглей за каждый совершенный бросок.

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

Выходной файл OUTPUT.TXT должен содержать одно целое число - количество набранных игроком очков.

Примеры

Код

№          INPUT.TXT                                                                       OUTPUT.TXT
1          12                                                                                    300
            10 10 10 10 10 10 10 10 10 10
2          15                                                                                    173  
            10 10 10 8 2 10 3 4 8 2 4 5 10 4 5

Личное мнение: я очень хочу решить эту задачу, но испытываю некоторые трудности, вы можете мне помочь с решением?

Сообщение отредактировано: Лисенок - 4.12.2009 19:01

[Lapp]

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

[DarkWishmaster]

Сообщество роботов:
Сообщество роботов живет по следующим законам: один раз в год они объединяются в полностью укомплектованные группы по 3 или 5 роботов, причем число групп из 3 роботов - максимально возможное. За год группа из 3 роботов собирает 5 новых собратьев, а группа из 5 - 9 новых собратьев. Каждый робот живет 3 года после сборки. Известно начальное количество роботов K (К>7), все они только что собраны. Определить сколько роботов будет
через N лет.

Input: Числа К и N (N,K≤32767) вводятся с клавиатуры.
Output: На экране выводится количество роботов через N лет.
Пример: Input: 11 2
Output: 80

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

Program Robot_Society;
Uses CRT;
Var A:Array[1..3] Of Longint;
	//в векторе храним число роботов возрастов 1, 2 и 3.
N,K,I:Integer;
X,Y,Rb,Nt:Longint;
// X- группы по 3, Y- группы по 5
Begin
ClrScr;
Write('nr robots=');ReadLn(K);
Write('nr years=');ReadLn(N);
A[1]:=K; A[2]:=0; A[3]:=0; Nt:=K;
For I:=1 To N Do Begin
X:=0; Y:=0; Rb:=Nt;  //Nt будет нашим результатом
While (Rb mod 3<>0) And (Rb>0) Do Begin Y:=Y+1; Rb:=Rb-5 End;  // делаем групы по 3 и 5 
If Rb>0 Then X:=Rb div 3;   
A[3]:=A[2]; A[2]:=A[1]; A[1]:=5*X+9*Y;
Nt:=A[1]+A[2]+A[3]
End;
WriteLn('nr total=', Nt);
ReadKey; End. 

Добавлено через 5 мин.
Максимальная прибыль.
Для ускорения работы столовой, директор купил апарат, который успевает готовить любое меню за 1 час с минимальными затратами.
Столовая работает «nonstop» и принимает очень много заказов. Для каждого заказа существует лимит до которого нужно успеть приготовить заказ. Один заказ соответствует одному меню, а в столовой существует только один аппарат, который может приготовить за 1 час одно меню, поэтому помогите директору получить максимальную прибыль, используя аппарат для приготовления тех заказов, стоимость которых (прибыль) больше.

Input: Входной файл CANTINA.IN содержит в первой строке натуральное число n – которое соответствует числу заказов полученных за 1 день, а на следующих n строках – пары 2 чисел (час стоимость), разделенные пробелом, где: час это максимальное время до которого нужно успеть приготовить заказ, а стоимость это значимость этого заказа.

Output: На экран выводится натуральное число, что соответствует максимальной прибыли, которую можно получить при помощи купленного аппарата.
Пример:
CANTINA.IN
7
2 100
7 220
15 300
10 125
2 400
1 350
2 400
Ответ=1445

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

Program Cantina;
Uses CRT;
Type Meniu=Record
Hour:1..24;
Val:100..500 End;
T=Array[1..100] Of Meniu;
Lin=Array[1..24] Of Meniu;
Var A:T; B:Lin; F:Text;
N,I:Byte; S:Longint;
Procedure Writing;
Begin
Assign(F,'cantina.in'); Reset(F);
ReadLn(F,N);
For I:=1 To N Do
ReadLn(F,A[I].Hour,A[I].Val); Close(F)
End;
Procedure Sort;
Var V:Boolean; C:Meniu;
Begin V:=True;
While V Do Begin V:=False;
For I:=1 To N-1 Do
If (A[I].Val<A[I+1].Val) Or
(A[I].Val=A[I+1].Val) And (A[I].Hour>A[I+1].Ora)
Then Begin C:=A[I]; A[I]:=A[I+1]; A[I+1]:=C;V:=True End
End
End;
Procedure Print;
Var L:Byte;
Begin B[A[1].Hour]:=A[1]; S:=A[1].Val;
For I:=2 To N Do Begin
L:=A[I].Hour;
While (L>=1) And (B[L].Hour>0) Do Dec(L);
If L>=1 Then Begin B[L]:=A[I]; S:=S+A[I].Val End
End;
WriteLn(S)
End;
Begin ClrScr;
Writing; Sort; Print;
ReadKey End.

Сообщение отредактировано: DarkWishmaster - 30.03.2011 21:37

[vasia_borovec]

У мене на олімпіаді ( школьной ) була похожа задача до першої різниця в тому що серфя з 111111 до 999999 !!
Ось її розв*язок

var
 a,b,c,d,s,f,v : integer;
begin
v:=0 ;
 for a:=1 to 9  do
                for b:=1 to 9 do
                               for c:=1 to 9 do
                                              for d:=1 to 9 do
                                                             for s:=1 to 9 do
                                                                            for f:=1 to 9 do

                                                                            if (a+b+c=d+s+f) and (d+f+s=a+b+c)  then v:=v+1 ;

                                                                                    WriteLn (v) ;
                                                                                    readln ;
                                                                            end.

.

[Krjuger]

if (a+b+c=d+s+f) and (d+f+s=a+b+c)  then v:=v+1 ;

Вопрос зачем and (d+f+s=a+b+c) разве от перемены мест слагаемых результат суммы меняется??????

В этом разделе только условия и проверешнные решения!!!
Есть вопрос создайте тему.

Сообщение отредактировано: Krjuger - 13.11.2011 17:04

[vasia_borovec]

and (d+f+s=a+b+c) он не нужен ето просто моя ошибка

[APAL]

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

21649*513239=11111111111


Немного "размял" мозги:

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

{ ХРУСТ*ГРОХОТ=РРРРРРРРРРР  - RUS
  ABCDE*FBGAGE=BBBBBBBBBBB  - LAT
  Must by: 21649*513239=11111111111 }

{ stepen a^b }
Function sq(a,b : Longint) : Longint;
Begin
  If b<>0 then sq:=Round(exp(b*ln(a))) else sq:=1;
end;

{GetNumFromPos}
Function GNFP (a : Longint; n : byte) : Byte;
Var iii  : Byte;
    aaa  : Longint;
Begin
  aaa:=a;
  If n>1 then
    For iii:=1 to n-1 do aaa:=aaa div 10;
  GNFP:=aaa mod 10;
end;

{ aa*bb=xx1*1000000000+xx2 }
Procedure mulBigNum(aa,bb : Longint; var xx1,xx2 : Longint);
Var k,i,ii,j,jj  : Byte;
    xx           : array [1..20] of Byte;
    St           : String;

  Procedure Perenos;
  Var p : Byte;
  Begin
    For p:=1 to 19 do
      If xx[p]>9 then
      Begin
        Inc(xx[p+1],xx[p] div 10);
        xx[p]:=xx[p] mod 10;
      end;
  end;

Begin
  xx1:=0; xx2:=0;
  For i:=1 to 20 do xx[i]:=0;
  Str(aa,St); ii:=Length(St);
  Str(bb,St); jj:=Length(St);

  For i:=1 to ii do
  Begin
    k:=i;
    For j:=1 to jj do
    Begin
      Inc(xx[k],GNFP(aa,i)*GNFP(bb,j));
      Perenos;
      Inc(k);
    end;
  end;

  For i:=1 to 9 do
  Begin
    Inc(xx2,xx[i]*sq(10,i-1));
    Inc(xx1,xx[i+9]*sq(10,i-1));
  end;
end;

Var
  A,B,C,D,E,F,G : byte;
  x1,x2         : LongInt;

Begin
  For A:=0 to 9 do
   For B:=0 to 9 do
    For C:=0 to 9 do
     For D:=0 to 9 do
      For E:=0 to 9 do
       For F:=0 to 9 do
        For G:=0 to 9 do
        Begin       {ABCDE*FBGAGE=BBBBBBBBBBB}
          mulBigNum(A*10000+B*1000+C*100+D*10+E,
                    F*100000+B*10000+G*1000+A*100+G*10+E,
                    x1,x2);
          Writeln(A,B,C,D,E,' * ',F,B,G,A,G,E,' = ',x1,x2);
          If (x1=B*10+B) and (x2=B*100000000+
                                 B*10000000+
                                 B*1000000+
                                 B*100000+
                                 B*10000+
                                 B*1000+
                                 B*100+
                                 B*10+B) and
                                 ((x1<>0) and (x2<>0))then Halt;
        end;
        Writeln('No match found!');
end.

Turbo Pascal 7.0 под MS Windows 7 нашел решение примерно через 2 мин. 10 сек.

Сообщение отредактировано: APAL - 22.05.2013 15:42