Задачи муниципального этапа Всероссийской олимпиады школьников по программированию 2010 года (Башкортостан)

Выкладываю задачки с олимпиады по программированию в Башкортостане, который прошел 23 ноября 2010 года.  Для печати смотрите вложение.

Задача 1. " Сдача" (100 баллов)

    Имя входного файла:

    a.in

    Имя выходного файла:

    a.out

    Ограничение времени

    1 секунда на тест

    Ограничение по памяти

    64 Мб

     

     

    Когда Маша и Витя покупали подарок, возникла интересная ситуация. У них была в распоряжении только одна большая купюра, а у продавца – некоторое количество мелочи. Дело происходило утром, поэтому продавцу нужно было экономить мелочь, и он хотел отдать сдачу минимальным количеством монет. Подумав некоторое время, он точно определил, с каким количеством монет ему придется расстаться.

    А Вы сможете решить такую задачу?

     

    Формат входного файла.

    В первой строке входного файла записано целое число N (1<=N<=10) – количество различных номиналов монет, содержащихся в кассе. Можно считать, что количество монет каждого номинала достаточно.

    В следующей строке содержится n целых чисел аi (0<ai<2000) –номиналы монет.

    В третьей строке записано одно число k (1 <= k <=1000000) – сумма, которую нужно набрать

     

    Формат выходного файла.

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

     

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

     

    a.in

    a.out

    3

    1 3 5

    13

    3

     

    a.in

    a.out

    4

    5 6 7 8

    9

    -1

     

     

     

     

    Задача 2. «Приказ об отчислении» (50 баллов)

      Имя входного файла:

      b.in

      Имя выходного файла:

      b.out

      Ограничение времени

      1 секунда на тест

      Ограничение по памяти

      32 Мб

       

       

      В Тьмутараканском университете имени Кота Матроскина начинается очередное отчисление студентов за неуспеваемость. Для отчисления неуспевающих студентов каждой группы готовится отдельный приказ. Более того, теперь ректор требует, чтобы в одном приказе перечислялись только студенты, которые занимают некоторое количество подряд идущих строчек в лексикографически упорядоченном списке группы. Так, если в некоторой группе подлежат отчислению студенты, значащиеся в списке под номерами 1, 2, 5, 7, 8 и 9, то должно быть изготовлено не менее трёх приказов:  об отчислении студентов 1 и 2, об отчислении студента 5, об отчислении студентов 7, 8 и 9. Напишите программу, которая находит минимальное количество приказов об отчислении.

       

      Формат входного файла.

      В первой строке входного файла записано целое число N – количество отчисляемых студентов (0 <= N <= 106). Во второй строке записаны номера неуспевающих студентов в списке группы S1, S2, …, SN (1 <= Si <= 106). Номера записаны в порядке возрастания.

       

      Формат выходного файла.

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

       

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

       

       

      b.in

      b.out

      3

      3 4 5

      1

       

      b.in

      b.out

      6

      1 2 5 7 8 9

      3

       

       

       

      Задача 3. «Окружность и прямоугольник» (50 баллов)

        Имя входного файла:

        c.in

        Имя выходного файла:

        c.out

        Ограничение времени

        1 секунда на тест

        Ограничение по памяти

        32 Мб

         

         

        Вы имеете окружность радиуса R и прямоугольник со сторонами A и B. Ваша задача – определить, можно ли поместить окружность внутрь прямоугольника, или прямоугольник внутрь окружности. Касания разрешены.

         

        Формат входного файла.

        Во входном файле с.in записаны целые числа R, A и B (1 <= R, A, B <= 10000).

         

        Формат выходного файла.

        Если окружность можно поместить внутрь прямоугольника, то запишите в выходной файл с.out число 1, если прямоугольник можно поместить внутрь окружности, то запишите в выходной файл число 2, если ни то, ни другое нельзя сделать, запишите в выходной файл число 0.


         

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

         

         

        c.in

        c.out

        3 20 30

        1

         

        c.in

        c.out

        100 5 7

        2

         

        c.in

        c.out

        10 1 100

        0

         

        Задача 4. «Осмотр лабиринта» (100 баллов)

          Имя входного файла:

          d.in

          Имя выходного файла:

          d.out

          Ограничение времени

          1 секунда на тест

          Ограничение по памяти

          64 Мб

           

           

          Разведывательный робот предназначен для исследования опасных лабиринтов. Лабиринт, как обычно, представляет собой прямоугольник размером M на N, состоящий из одинаковых квадратов единичного размера. Некоторые квадраты заняты стенами, остальные свободны. Робот может перемещаться по горизонтали или по вертикали, если этому не препятствуют стены. Кроме того, робот снабжён четырьмя видеокамерами, которые позволяют ему видеть все квадраты лабиринта до ближайшей стены по горизонтали и по вертикали. Робот перемещается по лабиринту в соответствии с заданной ему программой. Программа для робота – это последовательность команд R, L, U, D. Команда R означает переместиться на один квадрат вправо, команда L – переместиться на один квадрат влево, U – на один квадрат вверх, и команда D – на один квадрат вниз. Если робот не может выполнить какую-либо команду (соответствующий квадрат занят стеной), то он пропускает эту команду и переходит к следующей. Ваша задача – по заданному плану лабиринта и заданной программе для робота подсчитать количество невыполненных команд и количество квадратов, осмотренных роботом. Квадрат, в котором находится робот в данный момент, ему не виден.

           

          Формат входного файла.

          В первой строке входного файла d.in записаны два целых числа N и M – размер лабиринта по вертикали и по горизонтали (3 <= N, M <= 100). В следующих N строках содержится план лабиринта. В каждой из этих строк записано по M символов ‘.’ или ‘#’ или ‘+’. Символы ‘.’ обозначают свободные квадраты, символы ‘#’ – квадраты, занятые стенами, и символ ‘+’ (который встречается в плане лабиринта ровно один раз) – начальное положение робота. Лабиринт всегда со всех сторон окружён стенами, так что робот не может выйти за его пределы. В следующей строке входного файла записано целое число L – длина программы для робота (1 <= L <= 10000). И в последней строке файла записана программа для робота. Программа состоит только из символов ‘R’, ‘L’, ‘U’, ‘D’.

           

          Формат выходного файла.

          Запишите в выходной файл d.out два целых числа через пробел – количество команд, которые робот не смог выполнить и количество квадратов, которые он осмотрел.


           

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

          d.in

          d.out

           

          d.in

          d.out

          3 4

          ####

          #+.#

          ####

          4

          RULD

          2 2

           

          7 7

          #######

          #.....#

          #.##.##

          #.#..##

          #.#.#.#

          #+#...#

          #######

          10

          UUUURRRDDL

          0 14

           

          Задача 5.«Деление» (50 баллов)

          Имя входного файла:

          e.in

          Имя выходного файла:

          e.out

          Ограничение времени

          1 секунда на тест

          Ограничение по памяти

          32 Мб

           

          Ваша задача – найти самое маленькое натуральное число, которое записывается в двоичной системе счисления в виде 1…10…0 (n единиц и m нулей, n, m > 0) и при этом делится на заданное число K.

           

          Формат входного файла.

          Во входном файле e.in записано натуральное число K (1 <= K <= 109).

           

          Формат выходного файла.

          Запишите в выходной файл e.out числа n и m – количество единиц и количество нулей в двоичной записи найденного числа.

           

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

           

           

          e.in

          e.out

          2

          1 1

           

          e.in

          e.out

          3

          2 1

           

           

          Задача 6.  «Банковский кризис» (100 баллов)

           

          Имя входного файла:

          f.in

          Имя выходного файла:

          f.out

          Ограничение времени

          1 секунда на тест

          Ограничение по памяти

          32 Мб

          В разгаре мировой финансовый кризис. Паника на биржах.  Банкротства компаний.  Банки лопаются один за другим из-за отсутствия средств. Но, по крайней мере, последнюю проблему – нехватку средств у банков решить очень легко. В наши дни банки кредитуют друг друга на огромные суммы. И когда какой-нибудь банк не имеет достаточно денег, чтобы возвратить взятые кредиты, на самом деле деньги у него есть, но они выданы другим банкам в качестве кредитов. Получается, что почти каждый банк должен огромные суммы другим банкам, но и другие банки должны ему огромные суммы. Рассмотрим в качестве примера денежные отношения четырёх банков, изображённые на рисунке (a).  К примеру, A кредитовал B на 50 миллионов и в то же самое время B кредитовал A на 150 миллионов (это вполне обычная банковская практика, когда два банка кредитуют друг друга).  Сумма долгов всех банков составляет 380 миллионов. Но можно обойтись существенно меньшей суммой, чтобы вернуть все кредиты.  Для этого:

          1.  C кредитовал D на ту же сумму, что D кредитовал A, поэтому мы можем считать, что C кредитовал A на 30 миллионов, а D вообще исключить из межбанковских расчётов.

          2.  Поскольку A уже кредитовал C на 100 миллионов, мы можем считать, что A выдал C 70 миллионов.

          3.  Аналогично будем считать, что B выдал A 100 миллионов. Так мы придём к состоянию, показанному на рисунке (b). Теперь для всех расчётов достаточно 190 миллионов (исходная сумма уменьшилась вдвое).

          4.  Но можно добиться ещё лучших результатов. Вместо того, чтобы B заплатил A 100 миллионов, и A заплатил 70 миллионов C,  B может заплатить 70 миллионов непосредственно С.  Так мы придём к графу взаиморасчётов, показанному на рисунке (c). Теперь все банки могут вернуть все свои долги, имея всего 120 миллионов оборотных средств. Исходная сумма уменьшилась на 260 миллионов или 68%.  Превосходно!

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

           

           

          рисунок (a)                 рисунок (b)                рисунок (c)


           

          Формат входного файла.

          В первой строке входного файла записано количество банков N (N < 1000). В остальных N строках записана целочисленная матрица межбанковских расчётов размером N x N.  i-я строка матрицы содержит суммы кредитов, выданные i-м банком. Все кредиты не превосходят 1000.

           

          Формат выходного файла.

          Запишите в выходной файл два целых числа – размер оборотных средств, необходимых для возврата всех кредитов до оптимизации и после оптимизации.

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

           

          f.in

          f.out

          4

            0 50 100  0

          150  0  20  0

            0  0  30

           30  0  0   0

          380 120

           

          Инструкция участнику

          Получите у организатора свой индивидуальный четырехзначный код. Файлы – решения должны быть названы следующим образом: pкод участника_номер задачи.расширение

          В качестве расширения допустимо использовать dpr для текстов на Delphi (pascal) или cpp для текстов на C++

          Язык программирования

          Компилятор

          Командная строка

          Паскаль

           

          Borland Delphi 7.0

          dcc32 –cc !.dpr

          Си

          Microsoft Visual C++ .NET 2003

          cl !.cpp

          Например, Ваш код 2301 и Вы пишете на паскале. Тогда решением четвертой задачи должен быть файл p2301_4.dpr (если расширение вашего файла pas, то во время проверки это расширение будет заменено на dpr членами жюри).

          Требования к решениям

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

          Разрешается использование библиотеки STL (для С++).

          Программа должна читать входные данные только один раз из файлов, указанных в условии задачи и выводить результат в выходные файлы, указанные в условии задачи. ВНИМАНИЕ имена файлов должны быть точно такими, как в условии. Проследите, чтобы у входных и выходных файлов не было расширений “txt”!

          Программа должна считать, что эти файлы находятся в текущем каталоге – не прописывайте пути к файлам в своих программах!

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

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

          Гарантируется, что входные файлы будут соответствовать формату, указанному в условии.

          Ввод с клавиатуры и вывод на экран строго запрещен.

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

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

          Программа не должна:

          • использовать расширенную память и защищенный режим процессора при использовании 16-битных компиляторов;

          • осуществлять чтение и запись векторов прерываний;

          • осуществлять любой ввод/вывод, кроме открытия, закрытия, чтения и записи файлов, указанных в условии задачи, в том числе создание подкаталогов, смену текущего каталога и ввод/вывод через порты;

          • осуществлять запуск других программ и создание новых процессов;

          • создавать или работать с любыми GUI объектами (окнами, диалогами и т.д.);

          • работать с внешними устройствами (принтером, сканером и т.д.);

          • иметь код завершения, отличный от нулевого.

           

          Пример программы, которая считывает из входного файла “sum.in” два числа и выводит в выходной файл “sum.out” сумму этих чисел.

          Borland Delphi 6.0

          Microsoft Visual C++ .NET 2003

          {$Apptype Console}

          Program Summa;

          Const InFile = ‘sum.in’;

          OutFile = ‘sum.out’;

          Var A, B : LongInt;

          Begin

          Assign(InPut, InFile);

          ReSet(InPut);

          Assign(OutPut, OutFile);

          ReWrite(OutPut);

          Read(A, B);

          Write(A + B);

          Close(Output);

          End.

          #include <vector>

          #include <string>

          #include <algorithm>

          #include <iostream>

          #include <fstream>

          #include <sstream>

          #include <cmath>

           

          using namespace std;

           

          int main() {

          ifstream infile ("sum.in");

          ofstream outfile ("sum.out");

          long a, b;

          infile >> a >> b;

          outfile << a + b;

          return 0;

          }

           

          ВложениеРазмер
          Usloviya_zadach.doc119 КБ

          Добавлено в копилку в раздел олимпиады: http://oivt.ru/olimp

          --------
          Ильфат Рифатович Исмагилов

          Сколько времени давалось на выполнение заданий? Сравниваю с предложенными у нас в Татарстане - 8 задач на 4 часа - ваши задачи вполне нормальные. Результат в РТ - не считая столицы Казании только в 7 районах и городах нащлись участники, сумевшие набрать 50% и более от максимума. В остальных 37 районах таких не оказалось.
          Решение Задачи 1 ... readln(n); for i:=1 to n do read(m[i]); readln; readln(k); for i:=1 to k do begin a[i]:=-1; for j:=1 to n do begin if i-m[j]<1 then begin if (i mod m[j]=0) then if (i div m[j]-1 then if (a[i]>a[i-m[j]]+1)or (a[i]=-1) then a[i]:=a[i-m[j]]+1; end; end; write(a[k]); ...
          Чтобы оценить шансы участия в республиканском туре выложите баллы своих лидеров. Кумертау 154(1), 130(2).
          Решение Задачи 5. ... readln(k); n0:=0; while k mod 2 =0 do begin k:=k div 2; inc(n0); end; if n0=0 then n0:=1; n1:=1; i:=1; if i mod k >0 then while i>0 do begin i:=i*2+1; i:=i mod k; inc(n1); end; writeln(n1,' ',n0); ...
          Гафурийский 1-169. 2-139
          Салаватский - 108

          --------
          Ильфат Рифатович Исмагилов

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

          Такая же статистика по всей стране, я предполагаю.

          --------
          Ильфат Рифатович Исмагилов

          поясните пожалуйчта решения задач!!ну очень нужно!!

          поясните пожалуйчта решения задач!!ну очень нужно!!