Задание 1. Региональный этап Всероссийской олимпиады по информатике 2010-2011 учебного года
Задача 1. Ролевая игра
Имя входного файла: game.in
Имя выходного файла: game.out
Ограничение по времени: 2 секунды
Ограничение по памяти: 256 Мбайт
Вася готовит инвентарь для ролевой игры. В игре
должны принять участие n игроков, каждый из которых будет изображать
персонажа фантастического мира. В процессе игры каждый персонаж будет
обладать некоторым уровнем х, который представляет собой целое число от
1 до m.
Для обозначения уровня планируется использовать специальные значки двух
цветов. Белый значок обозначает один уровень, а красный значок — k
уровней. Игрок, изображающий персонажа с уровнем х, должен иметь а
белых значков и b красных значков, чтобы сумма (а + bk) была равна х.
При этом персонажу не разрешается иметь более чем (k - 1) белых значков.
Значки для игры готовятся заранее, однако уровни персонажей заранее
неизвестны. Для успешного проведения игры всем персонажам необходимо
выдать соответствующее их уровням количество значков. Возникает вопрос:
какое минимальное суммарное количество значков необходимо подготовить
для успешного проведения игры при любых уровнях участвующих персонажей.
Требуется написать программу, которая по заданным числам n, m и k
вычисляет минимальное количество значков, которое необходимо
подготовить для успешного проведения игры. Решение: Математическая модель: n - количество игроков; m - число уровней; k - число уровней, обозначаемое одним красным значком; (k-1) - минимальное число белых значков на одного человека, необходимое для успешного проведения игры при любых уровнях участвующих персонажей. Тогда (k-1)*n - минимальное число белых значков, необходимое для успешного проведения игры при любых уровнях участвующих персонажей. Чтобы
найти минимальное число красных значков на одного человека,
удовлетворяющего условию задачи, нужно определить сколько целых k
выделяется из общего числа уровней m, т.е. [m/n]. И следовательно, число
красных значков [m/n]*n. И тогда суммарное минимальное число значков, необходимое для успешного проведения игры при любых уровнях участвующих персонажей (k-1)*n + [m/n]*n=(k-1+m/n)*n. Построение компьютерное модели (запись на языке программирования):
Тurbo Pascal
Perl
program game; var ft:text; n,m,k:integer; BEGIN Assign(ft,'game.in'); Reset(ft); Read(ft,n); Read(ft,m); Read(ft,k); close(ft); Assign(ft,'game.out'); Rewrite(ft); writeln(ft,((k-1)+m div k)*n); close(ft); END.
#!/usr/bin/perl #прописываем путь к perl #use strict; #включаем вывод сообщений об ошибках подключением модуля strict use IO::File; # подключаем модуль IO::FIle для работы с файлами в объектно-ориентированном контексте my $file_in="game.in"; my $fh1 = IO::File->new("<$file_in") or die "Can`t open $file_from: $!\n"; #определяем входной файл, в случае ошибки при открытии файла выводится соответствующее сообщение с указанием типа ошибки my $file_out="game.out"; my $fh2 = IO::File->new(">$file_out") or die "Can`t open $file_to: $!\n"; #то же для выходного файла. Если он не существует, то будет создан my $line = $fh1->getline; # читаем строку из файла в переменную my @numbers = split (/\s+/,$line); # режем переменную с числами на отдельные числа, записываем их в массив скаляров my $result = ($numbers[2]-1+int($numbers[1]/$numbers[2]))*$numbers[0]; # вычисляем результат по формуле $fh2->print ($result); # записываем результат в выходной файл
QBasic
Python
open fail "game.in" for input as#1 input #1, m input #1, n input #1, k close #1 z=((k-1)+int(m /k))*n open fail "game.out" for output as#1 print #1, z close #1
importos os.chdir('сдесь путь к файлу') f=open(os.getcwd()+’/game.in’, ’wb’) c=f.read() n=int(c[0]) m=int(c[1]) k=int(c[2]) f.close() z=((k-1)+int(m /k))*n ff=open(’/game.out’, ’r+’) ff.write(z) ff.close()
Решение на Perl предоставил Konstantinus, на QBasic и Pithon Bobrik-ms.