Разбор и решение задач с областной олимпиады 2013-14 года
У многих учителей информатики стоит вопрос: как найти задачи с областных олимпиад?, их решение и разбор? Я нашла это, как не странно, на сайте “Олимпиады по информатике” г. Санкт-Петербурга в разделе “Архив олимпиад” - там всё расписано по годам и в рубрике “Региональный этап” размещены условия задач, разбор, тесты и решения жюри. Сейчас эти задачи выложены на сайте “Дистанционная подготовка по информатике” в разделе “Личные олимпиады”- “Региональные олимпиады”. Здесь можно потренироваться в подготовке к такого уровня олимпиад.
Я попробовала решить несколько задач с 2013-14 года на С++ в среде CodeBlocks. Вот что у меня получилось:
При регистрации на портале интернет-олимпиады все участники заполняют регистрационную форму, где они указывают название школы, в которой они учатся. Разные участники могут по-разному писать название школы, например, «Физико-математическая школа №18», «ФМШ №18».
Организаторам олимпиады предоставлена информация о названиях школ, которые написали регистрируемые участники олимпиады. Точно известно, что цифры в названии школы встречаются только в номере школы, а число в записи названия школы встречается ровно один раз и оно однозначно определяет номер школы. Номер школы является положительным целым числом и не может начинаться с нуля.
Требуется написать программу для сайта интернет-олимпиады, которая поможет организаторам олимпиады получить следующую информацию: количество школ и номера школ, из которых зарегистрировалось не более пяти участников.
Формат входного файла
Первая строка входного файла содержит одно целое число n (1 ≤ n ≤ 1000) – количество названий школ, указанных всеми участниками при регистрации.
Последующие n строк содержат названия школ, указанные всеми участниками. Название школы содержит только заглавные и строчные буквы латинского алфавита, цифры и пробелы, длина названия не превышает 100 символов.
Формат выходного файла
Первая строка выходного файла должна содержать одно число m – количество школ, от которых на олимпиаду зарегистрировалось от одного до пяти участников. Последующие m строк должны содержать только номера таких школ, при этом номера должны располагаться по одному в строке в произвольном порядке.
Пояснения к примеру
В приведенном примере для участия в интернет-олимпиаде зарегистрировались: два ученика из школы с номером 18, один ученик из школы с номером 42 и шесть учеников из школы с номером 9. Таким образом, от 1 до 5 участников зарегистрировано от школ с номерами 18 и 42.
Система оценивания
Частичные правильные решения для тестов, в которых все номера школ являются однозначными числами, будут оцениваться из 30 баллов.
Частичные правильные решения для тестов, в которых номера школ – это числа строго меньше 1000, будут оцениваться из 50 баллов.
Частичные правильные решения для тестов, в которых номера школ – это числа строго меньше 109, будут оцениваться из 80 баллов.
Несмотря на выделение отдельных групп тестов, на окончательную проверку будут приниматься только решения, правильно работающие для теста из условия задачи.
Примеры
Входные данные
9
Physics and Mathematics School 18
9ya shkola imeni Pushkina
Lyceum 9
PaMS 18
Gymnasium 42
School 9
Shkola nomer 9
High school 9
School N 9
Выходные данные
2
18
42
В начале идея (спецификация) - считываем каждую строчку в цикле, выделяем только номер школы и сохраняем в массив. При этом массив может хранить все номера (после этого можно отсортировать и выделить неповторяющиеся и сколько раз они встречаются в новый массив) или только неповторяющиеся (в этом случае нужен массив для хранения количества повторений).
Приведу пример программы на 50 баллов:
#include <iostream>
#include <fstream>
#include <string.h>
#include <sstream>
#include <stdlib.h>
using namespace std;
int main()
{ifstream fin("input.txt");
long int n;
string s;
fin>>n;getline(fin,s);/*если считать fin>>n; - то курсор останется на первой строке и первая команда getline считает “остаток” строки и перейдет на новую*/
long int maxin=100000, k,l,B[1001];//массив номеров школ
long int A[maxin];//массив количества неповторяющихся номеров школ
char c;//символ
char d[100];//строка из не более 100 символов
for (long int i=0;i<maxin;i++)A[i]=0;/*зануляем массив, который будет содержать количество повторений для каждого i-го номера школы*/
for (long int i=0;i<n;i++)
{//выделяем из строки номер школы
d[0]='\0';k=0;
while ( (c=fin.get()) != 10)//пока нет конца строки - код 10 и 13
if (c>='0' && c<='9') {d[k]=c;++k;}/*проверяем символ на цифру и добавляем к новой строке d*/
d[k]='\0';//добавляем символ конца строки
l=atol(d);//и переводим строку d в число l
A[l]=A[l]+1;//увеличиваем счетчик для школы с номером l
}
k=0;
for (long int i=1;i<=maxin;i++)
{
if(A[i]<=5&&A[i]>0){B[k]=i;k++;}/*считаем количество школ, которые повторяются не более 5 раз, и запоминаем номер школы в новы массив В*/
}
cout<<k<<endl;//вывод количества школ
for (long int i=0;i<k;i++)
cout<<B[i]<<endl;//вывод номеров школ
return 0;
}
Пример программы на 80 баллов:
#include <iostream>
#include <fstream>
#include <string.h>
#include <sstream>
#include <stdlib.h>
using namespace std;
struct num{long long int a; int b;};/*объединим номер школы и количество в структуру (запись)*/
int main()
{ifstream cin("input.txt");
int n;
string s;
getline(cin, s);stringstream(s)>>n;/*считываем первую строку s и переводим в число n*/
int m,k,h,z;
long long int l;
num B[n];//массив записей
char c;//символ
char d[100];//строка из не более 100 символов
m=0;z=0;
for (int i=0;i<n;i++)
{
d[0]='\0';k=0;
while ( (c=cin.get()) != 10)
if (c>='0' && c<='9') {d[k]=c;++k;}
d[k]='\0';
l=atoll(d);//перевод из строки в длинное целое
//проверяем, есть ли такая школа в нашем списке
h=-1;
for (int j=0;j<m;j++)
{
if(B[j].a==l){h=j;break;}//если найдена, то выходим из цикла
}
if (h==-1){B[m].a=l;B[m].b=1;++m;}/* если нет, то добавляем в список школ и устанавливаем счетчик на 1 */
else B[h].b+=1;//увеличиваем счетчик на 1
}
k=0;
for (int i=0;i<m;i++)
{
if(B[i].b<=5 && B[i].b>0)k++;/*считаем количество школ, удовлетворяющих условию*/
}
cout<<k<<endl;//вывод количества школ
for (int i=0;i<m;i++)
if(B[i].b<=5 && B[i].b>0) cout<<B[i].a<<endl;/*вывод номеров школ, удовлетворяющих условию*/
return 0;
}
Мы рассмотрели варианты с целыми числами. А если номер школы занимает всю строку из 100 символов?
Пример программы на 100 баллов:
#include <iostream>
#include <fstream>
#include <string.h>
#include <sstream>
#include <stdlib.h>
#include <algorithm>
using namespace std;
struct num{string a; int b;};//меняем только тип данных в структуре
int main()
{ifstream cin("input.txt");
int n;
string s,l;
getline(cin,s);stringstream(s)>>n;
int m,k,h,z;
num B[n];
char c;
char d[100];
m=0;z=0;
for (int i=0;i<n;i++)
{
l="";k=0;
while ( (c=cin.get()) != 10)
if (c>='0' && c<='9') {l=l+c;++k;}//и работаем со строкой l типа string
h=-1;
for (int j=0;j<m;j++)
{
if(B[j].a==l){h=j;break;}
}
if (h==-1){B[m].a=l;B[m].b=1;++m;}
else B[h].b+=1;
}
k=0;
for (int i=0;i<m;i++)
{
if(B[i].b<=5 && B[i].b>0)k++;
}
cout<<k<<endl;
for (int i=0;i<m;i++)
if(B[i].b<=5 && B[i].b>0) cout<<B[i].a<<endl;
return 0;
}
А если применить ассоциативные массивы map из STL?
И еще на 100 баллов:
#include <iostream>
#include <string>
#include <map>
#include <fstream>
using namespace std;
int main()
{
map <string,int> A;/*объявляем ассоциативный массив, где индексом будет строка “номер школы”, а значение элемента массива - количество повторений*/
ifstream in("input.txt");
string l;
char c;
int n;
in>>n;getline(in,l);
for (int i=0;i<n;i++)
{
l="";
while ( (c=in.get()) != 10)
if (c>='0' && c<='9') {l=l+c;}//формируем строку l - “номер школы”
A[l]++;/*увеличиваем счетчик в массиве А по индексу l (номер школы как строка типа string). Проверять, есть или нет такой номер в списке не надо, так как индекс работает как “множество” (если элемента нет, то добавит, если есть - то нет), точно также не надо заранее обнулять значения массива */
}
ofstream out("output.txt");
long int k=0;
map <string,int>::iterator cur;//объявляем итератор по массиву А
for (cur=A.begin();cur!=A.end();cur++)//цикл по всем элементам массива
if (((*cur).second)<=5 and ((*cur).second)>0) k++;/*сравниваем по второму типу int - значение элементов массива*/
out<<k<<endl;//вывод количества школ
if(k==0)return 0;//это для быстроты
for (cur=A.begin();cur!=A.end();cur++)
if (((*cur).second<=5) and ((*cur).second)>0) out<<(*cur).first<<endl;//выводим по первому типу string - номер школы
return 0;
}
При реализации проекта «Умная школа» было решено в каждый учебный класс выбранной для этого школы установить по кондиционеру нового поколения для автоматического охлаждения и вентиляции воздуха. По проекту в каждом классе должен быть установлен только один кондиционер и мощность кондиционера должна быть достаточной для размеров класса. Чем больше класс, тем мощнее должен быть кондиционер.
Все классы школы пронумерованы последовательно от 1 до n. Известно, что для каждого класса с номером i, требуется ровно один кондиционер, мощность которого больше или равна ai ватт.
Администрации школы предоставили список из m различных моделей кондиционеров, которые можно закупить. Для каждой модели кондиционера известна его мощность и стоимость. Требуется написать программу, которая определит, за какую минимальную суммарную стоимость кондиционеров можно оснастить все классы школы.
Формат входного файла
Первая строка входного файла содержит одно целое число n (1 ≤ n ≤ 50 000) количество классов в школе. Вторая строка содержит n целых чисел ai (1 ≤ ai ≤ 1000)- минимальная мощность кондиционера в ваттах, который можно установить в классе с номером i. Третья строка содержит одно целое число m (1 ≤ m ≤ 50 000) - количество предложенных моделей кондиционеров. Далее, в каждой из m строк содержится пара целых чисел bj и cj (1 ≤ bj ≤ 1000, 1 ≤ cj ≤ 1000) мощность в ваттах j-й модели кондиционера и его цена в рублях соответственно.
Формат выходного файла
Выходной файл должен содержать одно число минимальную суммарную стоимость кондиционеров в рублях. Гарантируется, что хотя бы один корректный выбор кондиционеров существует, и во всех классах можно установить подходящий кондиционер.
Пояснения к примерам
В первом примере нужно купить один единственно возможный кондиционер за 1000 рублей.
Во втором примере оптимально будет установить в первом и втором классах кондиционеры четвертого типа, а в третьем классе – кондиционер третьего типа. Суммарная стоимость этих кондиционеров будет составлять 13 рублей (3 + 3 + 7).
Система оценивания
Частичные решения для n, m ≤ 1000 будут оцениваться из 50 баллов.
Примеры
Входные данные
1
800
1
800 1000
Выходные данные
1000
Входные данные
3
1 2 3
4
1 10
1 5
10 7
2 3
Выходные данные
13
Будем сравнивать каждую мощность кондиционера в классе с представленными и находить минимальную стоимость.
Пример программы на 55 баллов:
#include <iostream>
using namespace std;
struct num{int b,c;};
int main()
{
int n,m,i,j,min;
cin>>n;
int A[n];
for (i=0;i<n;i++)
cin>>A[i];
cin>>m;
long int s=0;
num K[m];
for (i=0;i<m;i++)
cin>>K[i].b>>K[i].c;
for (i=0;i<n;i++)
{min=1001;
for (j=0;j<m;j++)
{
if(A[i]<=K[j].b&&K[j].c<min)min=K[j].c;
}
s+=min;
}
cout<<s;
return 0;
}
Эта программа будет работать дольше на больших массивах или если мощности кондиционеров повторяются. Итак, нужно запомнить количество повторяемых мощностей (пусть это будет массив D, где индекс - это значение мощности, тогда размер массива не превышает 1000+1 для 0) и находить только их минимальную стоимость по заданным параметрам кондиционеров (пусть это будет массив C, где индекс - это значение мощности).
Пример программы на 100 баллов:
#include <iostream>
#include <fstream>
using namespace std;
int main()
{
int n,m,i,j;
cin>>n;
int b, c, a, C[1001],D[1001];
for(int i=0;i<1001;i++){C[i]=0;D[i]=0;}//обнуляем массивы
for (i=0;i<n;i++)
{
cin>>a;//считываем значение мощности
D[a]++;/*увеличиваем счетчик - количество комнат c заданным значением мощности а*/
}
cin>>m;
long int s=0;
for (i=0;i<m;i++)
{
cin>>b>>c;
for (j=1;j<=b;j++)// для всех мощностей от 1 до b
if((C[j]>c || C[j]==0))C[j]=c;/*определяем минимальное среди уже введенной стоимости C[j] и заданной стоимости c для кондиционера мощности b, если стоимости еще не было определено (C[j]==0), то присваиваем заданную стоимость c*/
}
s=0;
for (i=1;i<1001;i++)
{
s+=C[i]*D[i];/*сcумируем стоимость всех кондиционеров мощностью i в количестве D[i]*/
}
cout<<s;
return 0;
}