Задача A. Малыш и Карлсон

Автор:Южно-Уральский открытый командный чемпионат
Входной файл: input.txt   Ограничение времени:5 сек
Выходной файл: output.txt   Ограничение памяти:64 Мб

Условие

Малыш может съесть банку варенья за А1 минут, корзину печенья за B1 минут, выпить бутылку молока за C1 минут. А Карлсон может сделать это за A2, B2, C2 минут соответственно. Напишите программу, вычисляющую, за какое минимальное время они смогут покончить с завтраком, состоящим из банки варенья, корзины печенья и бутылки молока?

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

В первой строке входного файла содержится три целых числа, разделенных пробелами — значения параметров A1, B1, C1. Во второй строке входного файла содержится три целых числа, разделенных пробелами — значения параметров A2, B2, C2.

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

В выходной файл вывести одно число — минимальное время завтрака с точностью 105.

Ограничения

Все числа в диапазоне от 1 до 106.

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
13 10 14
6 6 7
12.00000

Задача B. Треугольники

Автор:Южно-Уральский открытый командный чемпионат
Входной файл: input.txt   Ограничение времени:5 сек
Выходной файл: output.txt   Ограничение памяти:64 Мб

Условие

Будем различать следующие варианты взаимного расположения двух треугольников в пространстве:

  1. треугольники не пересекаются;
  2. угол первого треугольника "протыкает" второй треугольник;
  3. угол второго треугольника "протыкает" первый треугольник;
  4. контуры треугольников сцеплены между собой.
Напишите программу, определяющую вариант расположения двух треугольников, заданных координатами своих вершин.

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

В первой строке входного файла содержится девять чисел x1, y1, z1, x2, y2, z2, x3, y3, z3, разделенных пробелами — координаты вершин первого треугольника. В второй строке входного файла содержится девять чисел x4, y4, z4, x5, y5, z5, x6, y6, z6, разделенных пробелами — координаты вершин второго треугольника.

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

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

Ограничения

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

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
0 0 0 10 0 0 0 10 0
1 1 -1 10 10 -1 1 1 10
3

Задача C. Комментарии

Автор:Южно-Уральский открытый командный чемпионат
Входной файл: input.txt   Ограничение времени:5 сек
Выходной файл: output.txt   Ограничение памяти:64 Мб

Условие

Джон, хотя и пишет на языке С, дает файлам расширение CPP, чтобы использовать в своих программах комментарии в С++-стиле (от // до конца строки). Обычный С-комментарий, который начинается с символов "/*" и заканчивается символами "*/", Джон также иногда использует, обычно для многострочных комментариев. Для участия в конкурсе программ необходимо, чтобы программа соответствовала стандартам языка ANSI С, и Джону нужно заменить все C++-комментарии на стандартные. Для этого в C++-комментарии можно заменить "//" на "/*" и добавить "*/" в конце строки. Иногда в C++-комментарии может встретиться последовательность символов "*/", в этом случае нужно вставить пробел между двумя этими символами: "* /". К счастью внутри строковых констант в программе Джона не встречаются последовательностей "//", "/*" и "*/".

Напишите программу, которая преобразует в программе Джона C++-комментарии в C-комментарии.

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

Во входном файле содержится программа Джона.

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

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

Ограничения

Файл состоит из не более 100 строк длиной не более 100 символов.

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
#include <stdio.h>
/* Пример программы
 */
int main() 
{ printf( //Печать
      "Hello, world");
  return 0; //*/*
}
#include <stdio.h>
/* Пример программы
 */
int main() 
{ printf( /*Печать*/
      "Hello, world");
  return 0; /** /**/
}

Problem D. Divide by Squares

Author:Южно-Уральский открытый командный чемпионат
Input file: input.txt   Time limit:5 sec
Output file: output.txt   Memory limit:64 Mb

Statement

Divide by Squares is played on a rectangular grid. Some of the squares in the grid are numbered. The objective is to divide the grid into rectangular and square pieces such that each piece contains exactly one number, and that number represents the area of the rectangle (from Wikipedia).

On the pictures you can see a sample of the puzzle and its solution.

You are to write program that solves this puzzle.

Input file format

The first line of the input file contains three integers, separated by spaces — the height H, the width W of the grid, and total amount K of numbers on the grid. Each of the next K lines contains three integers, separated by spaces — position (i, j) of the number and the number itself. The puzzle in the input has at least one solution.

Output file format

The output file must contain K lines. For each number in the input you should print four integers on corresponding line — coordinates of left upper corner of the rectangle that contains this number and its height and width. You have to print arbitrary solution.

Constraints

1 ≤ H ≤ 10, 1 ≤ W ≤ 10, 1 ≤ K ≤ W*H

Sample tests

No. Input file (input.txt) Output file (output.txt)
1
4 4 4
2 1 4
2 3 6
3 1 4
4 4 2
1 1 2 2
1 3 3 2
3 1 2 2
4 3 1 2

Задача E. Плотность населения

Автор:Южно-Уральский открытый командный чемпионат
Входной файл: input.txt   Ограничение времени:5 сек
Выходной файл: output.txt   Ограничение памяти:64 Мб

Условие

После проведения переписи населения Флатландии все данные были нанесены на карту. Прямоугольная карта Флатландии была разделена на клетки единичного размера. Число жителей в каждой клетке изменяется от 0 до 9.

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

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

В первой строке входного файла содержится три целых числа, разделенных пробелами — размеры Флатландии N, M и заданная плотность населения K. Далее следует N строк, каждая из которых содержит M цифр от 0 до 9 — карта распределения населения Флатландии.

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

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

Ограничения

1 ≤ N ≤ 100, 1 ≤ M ≤ 100, 1 ≤ K ≤ 9

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
3 3 1
020
102
020
1 2 3 2

Задача F. Контрольная сумма

Автор:Южно-Уральский открытый командный чемпионат
Входной файл: input.txt   Ограничение времени:5 сек
Выходной файл: output.txt   Ограничение памяти:64 Мб

Условие

Напишите программу, которая копирует текст из входного файла и добавляет к нему фразу "Это сообщение содержит ровно K букв и ровно M цифр.", при этом K и M должны учитывать буквы и цифры в добавленной фразе. Буквами считаются строчные и прописные латинские буквы, а также все символы с ASCII-кодами от 128 до 255. Слова "буквы" и "цифры" во фразе должны иметь окончание, соответствующее числительному, например, "21 цифру", "4 цифры", "15 цифр". При необходимости в контрольной фразе можно не выводить одно или оба слова "ровно".

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

Входной файл содержит одну строку.

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

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

Ограничения

Длина строки не более 200 символов. Русские буквы должны быть в кодировке WINDOWS-1251.

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
Сегодня contest.
Сегодня contest.
Это сообщение содержит ровно 49 букв и 3 цифры.

Задача G. Газовые войны

Автор:Южно-Уральский открытый командный чемпионат
Входной файл: input.txt   Ограничение времени:5 сек
Выходной файл: output.txt   Ограничение памяти:64 Мб

Условие

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

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

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

Первая строка входного файла содержит три целых числа, разделенных пробелами — количество потребителей N, количество промежуточных насосных станций K и количество труб для транспортировки газа M.

Вторая строка содержит N целых чисел Vi, разделенных пробелами — объемы газа, которые необходимо поставить потребителям.

Далее следует M строк, содержащих по четыре целых числа, разделенных пробелами — номера узлов aj (0 ≤ aj ≤ K+N) и bj (0 ≤ bj ≤ K+N), связанных трубой, максимальный объем газа fj, который можно подать на вход этой трубы и процент газа dj, который выкачивается из этой трубы при транспортировке.

Узел c номером 0 соответствует компании-поставщику. Потребителям соответствуют узлы с номерами от 1 до N. Промежуточные насосные станции имеют номера от N+1 до N+K. Между двумя узлами проходит не более одной трубы.

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

В выходной файл вывести одно число — минимальный объем поставок газа для обеспечения всех потребителей с точностью 105. Если для какого-нибудь из потребителей невозможно выполнить поставку в требуемом объеме, то вывести число 1.

Ограничения

1 ≤ N ≤ 10, 0 ≤ K ≤ 100, 1 ≤ M ≤ 1000, 0 < Vj ≤ 100, 0 < fj ≤ 100, 0 ≤ dj ≤ 100

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
1 1 3
10
0 1 5 20
0 2 10 5
2 1 10 5
11.21875

Задача H. Задача Пифагора

Автор:Южно-Уральский открытый командный чемпионат
Входной файл: input.txt   Ограничение времени:5 сек
Выходной файл: output.txt   Ограничение памяти:64 Мб

Условие

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

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

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

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

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

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

Ограничения

Все числа вещественные, больше 0 и меньше 1000.

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
10.0 10.0 10.0
25.00000

Problem I. The Picture Drawing

Author:Южно-Уральский открытый командный чемпионат
Input file: input.txt   Time limit:5 sec
Output file: output.txt   Memory limit:64 Mb

Statement

Your mission, if you decide to accept it, is to create a picture drawing program. A picture will consist of the alphabetic characters A-Z and spaces.

Input file format

Your program will get the information for the picture from the input file. This file will contain lines of characters which your program must interpret to draw a picture. Each row of the picture will be described by a series of numbers and characters, where the numbers before a character tell how many times that character will be used. If there are multiple digits in a number before a character, then the number of times to repeat the character is the sum of the digits before that character.

The character "." (dot) will be used in the input file to represent spaces in the picture. The descriptions for different rows in the picture will be separated by an end of line.

The input file will be terminated by an end of file.

Constraints

There is no limit to the number of rows in a picture, though no row will contain more than 200 characters.

Sample tests

No. Input file (input.txt) Output file (output.txt)
1
2X3.1X
13X1.1X
XX   X
XXXX X

0.083s 0.004s 31