Поиск по этому блогу

воскресенье, 5 февраля 2017 г.

POBEDA-2014

Задача регионального этапа Всероссийской олимпиады школьников 2014 года.

Задача 1. POBEDA-2014
Имя входного файла: pobeda.in
Имя выходного файла: pobeda.out
Ограничение по времени: 2 секунды
Ограничение по памяти: 256 мегабайт

Как известно, современные видеокарты умеют формировать изображения с использованием только треугольников. Видеокарта POBEDA-2014 не отстает от современных тенденций. Известно, что она умеет отображать только прямоугольные равнобедренные треугольники четырех типов ориентации, представленные на рисунках ниже. Изменять ориентацию этих треугольников видеокарта не может.



Длина катета каждого из представленных выше треугольников равна одному сантиметру. За один такт видеокарта не может отобразить более чем ai треугольников i-того типа.
Необходимо определить максимально возможную длину стороны квадрата, который может быть изображен видеокартой на экране монитора за один такт. При этом квадрат должен быть расположен так, чтобы его стороны были параллельны краям монитора.
Требуется написать программу, которая решает поставленную задачу.
Формат входного файла
Первая строка входного файла содержит разделенные пробелами четыре целых числа: a1, a2, a3,a4 (0 ≤ a1, a2, a3, a4 ≤ 1018). Входные данные могут превышать максимальные значения для 32 битного типа данных.
Формат выходного файла
Выходной файл должен содержать одно число – максимально возможную длину стороны квадрата.
Примеры входных и выходных файлов
pobeda.in   pobeda.out
2 2 2 2          2
10 10 0 0      3
Решение
Анализируя условие задачи видим, что квадрат может получиться только маленьких (со стороной 1 см) квадратиков. Которые, в свою очередь могут получиться из треугольников определенных типов. Так, например, сочетаются 1 тип со 2 типом и 3 тип с 4 типом, но не сочетаются (не могут быть построены квадраты)  при другом наборе. 
Общее количество минимальных квадратов можно узнать найдя минимальные значения в парах (а1,а2) и (а3,а4) и сложив их. Тогда  длина стороны максимального квадрата, построенного из минимальных квадратов, будет равна   целой части корня из общего количества минимальных квадратов.
var d,a1,a2,a3,a4,k1,k2:real; {d - сторона максимального квадрата, k1 - минимальное значение (а1,а2), k2 -минимальное значение в паре (а3,а4)}
     f:text; {файловая переменная}
  begin
    assign(f,'pobeda.in'); {Связываем файловую переменную с файлом данных}
    reset(f); {Открываем файл pobeda.in для чтения}
    readln(f,a1,a2,a3,a4); {Считываем данные о количестве треугольников каждого типа}
    if a1<a2 then k1:=a1 else k1:=a2; {Минимальное первой пары}
    if a3<a4 then k2:=a3 else k2:=a4; {Минимальное второй пары}
    d:=trunc(sqrt(k1+k2)); {Определяем длину стороны максимального квадрата}
    close(f); {Закрываем файл pobeda.in для чтения}
    assign(f,'pobeda.out'); {Связываем файловую переменную с файлом результатов}
     rewrite(f); {Открываем файл pobeda.out для записи}
    write(f,d:1:0);  close(f); {Выводим результат и закрываем файл}
  end.

2 комментария:

  1. К сожалению ваша программа не проходит на http://acmp.ru/asp/do/index.asp?main=task&id_course=1&id_section=3&id_topic=37&id_problem=214

    ОтветитьУдалить
  2. У вас на каком тесте проваливается?

    ОтветитьУдалить