Opencup.ru - Northern Grand Prix

В минувшее воскресенье 13.03.2011 на довольно-таки известном сайте по программированию opencup.ru проводился турнир Northern Grand Prix, участником которого был и я. Необходимо было решить 10 задач, на которые отводилось 5 часов.

У большинства людей бытует мнение, что турниры/олимпиады по программированию представляют из-за себя решение очень сложных задач. В большинстве своем - это так. Однако, хочется сказать, что практически всегда бывают задачи, которые не требуют наличия большого количества знаний и являются не такими уж и сложными. Несколько таких задач из прошедшего турнира я решил разместить здесь.

Investments

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

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

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

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

Первая строка содержит целое число T - количество тестовых примеров (1 ≤ T ≤ 255). Каждый тестовый пример описывает новый проект. Первая строка описания содержит два числа: стоимость проекта N (1 ≤ N ≤ 10⁶), которую надо покрыть за счёт инвестиций и количество потенциальных инвесторов C (1 ≤ C ≤ 1000). Вторая строка содержит C целых чисел, i-e из которых задает максимальную сумму M_i, которую i-я компания готова вложить в проект.

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

Для каждого тестового примера необходимо вывести одну строку - наименьшее количество инвесторов, которое следует привлечь профессору Громову для того, чтобы начать производство. Если денег на проект не хватит ни при каком количестве инвесторов, необходимо вывести "impossible".

Пример:

Входной файл:

3

101 6

23 27 41 19 23 57

100 7

20 22 33 8 24 67 9

1001 3

123 456 123

Выходной файл:

3

2

impossible

Решение:

Задачка является довольно-таки простой. Для того, чтобы получить минимальное количество инвесторов, мы должны выбрать тех, которые готовы вложить в проект максимальные суммы денег.

1. #include <stdio.h>
2. #include <algorithm>
3. using namespace std;
4. 
   
5. int main()
6. {
7.         FILE *in, *out;
8.         // количество тестовых примеров
9.         int T(0);
10.         // стоимость проекта и количество потенциальных инвесторов соответственно
11.         int N (1), C(1);
12. 
    
13.         in = fopen("invest.in", "r");
14.         fscanf(in, "%d", &T);
15.         out = fopen("invest.out", "w");
16. 
    
17.         // каждый тестовый пример будем обрабатывать отдельно
18.         // и сразу же записывать результат в файл
19.         for(int i = 0; i < T; i++)
20.         {
21.                 // массив сумм, которые готовы предоставить инвесторы
22.                 int M[1000] = {0};
23.                 
24.                 fscanf(in, "%d %d", &N, &C);
25.                 for(int i = 0; i < C; i++)
26.                         fscanf(in, "%d", &M[i]);
27. 
    
28.                 // сортируем суммы, которые готовы
29.                 // предоставить инвесторы, по возрастанию
30.                 sort(M, M+C);
31. 
    
32.                 // минимальное количество инвесторов,
33.                 // которое следует привлечь профессору
34.                 int count = 0;
35.                  // сумма, которую готовы предоставить эти инвесторы
36.                 int sum = 0;
37. 
    
38.                 /* увеличиваем сумму инвестиций до тех пор,
39.                 пока она не превысит/не станет равной требуемой сумме инвестиций,
40.                 или же пока не переберем всех инвесторов;
41.                 начинаем брать суммы с конца, так как они максимальны,
42.                 а, следовательно, количество инвесторов будет минимальным */
43.                 for(int i = C-1; i >= 0; i--)
44.                 {
45.                         sum += M[i];
46.                         count++;
47.                         if(sum >= N)
48.                                 break;
49.                 }
50. 
    
51.                 /* если общая сумма, которую могут предоставить инвесторы
52.                 меньше требуемой суммы, то выводим "impossible",
53.                 иначе выводим требуемое количество инвесторов */
54.                 if(sum < N)
55.                         fprintf(out, "impossible\n");
56.                 else
57.                         fprintf(out, "%d\n", count);
58.         }
59. 
    
60.         fclose(in);
61.         fclose(out);
62. 
    
63.         return 0;
64. }

OCR

Для нового поколения роботов профессора Громова компания-поставщик разработала улучшенный модуль распознавания символов (OCR). Подобные модули используются при чтении роботом "бумажного" текста. К сожалению, распознавание не всегда работает успешно, так что некоторые символы остаются нераспознанными. Наша задача - вычислить коэффициент распознавания. Коэффициент распознавания определяется как R/A * 100%, где R - количество распознанных символов и А общее количество символов в тексте. При этом переводы строк символами не считаются.

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

Входной файл содержит как минимум одну непустую строку распознанного текста. Нераспознанные символы представлены символом "#". При этом длина строки не превосходит 100 символов, строки содержат только символы с ASCII-кодами от 32 до 126 включительно, при этом "#" не встречается в исходном тексте.

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

Необходимо вывести коэффициент распознавания (в %), округлённый до ближайшего числа, десятичная запись которого содержит не более одного знака после точки (0.05 округляется до 0.1). При этом лишние нули после точки выводить запрещено (то есть вывод 0.50 вместо 0.5 или 25.0 вместо 25 будет признан некорректным).

Пример:

Входной файл:

Pr#nt the r#tio in perce##,

rounde##to t#e nearest number.

Professor Gromov.

Выходной файл:

87.7

100

Решение:

Сложность данной задачи состоит лишь в правильном подсчёте всех символов строки и округлении результирующего значения. Довольно-таки просто ее решить, если знать некоторые технические аспекты и средства языка С++.

В данном случае, считывание текста из файла и запись в файл необходимо осуществлять с помощью потоков ifstream и ofstream из библиотеки fstream в переменную типа string из библиотеки string, а для указания точности выводимого результата использовать функцию setprecision из библиотеки iomanip. Она выводит указанное количество символов и при необходимости округляет число.

1. #include <fstream>
2. #include <string>
3. #include <iomanip>
4. using namespace std;
5. 
   
6. int main()
7. {
8.         ifstream cin("ocr.in");
9.         ofstream cout("ocr.out");
10. 
    
11.         // буфер, необходимый для считывания каждой строки, 
12.         // и итоговая строка соответственно
13.         string bufer, str;
14.         // считываем данные из файла построчно в буфер
15.         // и формируем итоговую строку
16.         while(!cin.eof())
17.         {
18.                 getline(cin, bufer);
19.                 str.append(bufer);
20.         }
21. 
    
22.         // длина исходного текста
23.         int m = str.length();
24.         // количество нераспознанных символов
25.         int count (0);
26. 
    
27.         // проходим по итоговой строке и подсчитываем количество символов "#"
28.         for(int i = 0; i < m; i++)
29.                 if(str[i] == '#')
30.                         count++;
31. 
    
32.         // подставляем данные в исходную формулу
33.         float result = (float)(m - count) / (float)m * 100;
34. 
    
35.         /* если коэффициент распознавания больше десяти,
36.         то нам необходимо вывести число, состоящее из 3 цифр:
37.         2 первые цифры - целая часть, 3-я цифра - дробная часть;
38.         если коэффициент распознавания меньше либо равен десяти,
39.         то нам необходимо вывести число, состоящее из 2 цифр:
40.         1-ая цифра - целая часть, 2-ая цифра - дробная часть,
41.         для числа 10 - 2 цифры представляют целую часть */
42.         if(result > 10)
43.                 cout << setprecision(3) << result;
44.         else
45.                 cout << setprecision(2) << result;
46. 
    
47.         cin.close();
48.         cout.close();
49. 
    
50.         return 0;
51. }

Spinity

Некоторые строчные латинские буквы обладают следующим свойством: при повороте на 180 градусов они переходят или сами в себя, или в другие буквы. Можно составить даже целые слова, которые будут переходить сами в себя при повороте на 180 градусов, например, "sos" или "mow". Введем для слова w параметр "вращаемость" Sp(w) следующим образом:

Будем считать, что буквы 'o', 'l', 's', 'x' автосимметричны при повороте, и что существуют следующие пары взаимно симметричных букв: 'b' и 'q', 'd' и 'p', 'm' и 'w', 'n' и 'u'.

Для двух букв c₁ и c₂ s(c₁, c₂) равно 3, если буквы совпадают и являются автосимметричными, 2, если буквы не совпадают, но составляют симметричную пару, 1, если буквы совпадают, но не являются автосимметричными, и 0 в оставшихся случаях.

Наконец, определим вращаемость Sp(w) как сумму значений функции s для симметрично расположенных пар букв: для n-буквенного слова w Sp(w) = s(w₁, w_n) + s(w₂, w_n-1) + ... + s(w_n, w₁).

Наша задача - для каждого из заданных слов вычислить его вращаемость.

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

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

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

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

Пример:

Входной файл:

spellers

ololo

meow

axe

pad

sos

nu

Выходной файл:

spellers 14

ololo 15

meow 4

axe 3

pad 5

sos 9

nu 4

Решение:

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

Функция s определяет вес пары букв согласно поставленным условиям. Функция Sp подсчитывает сумму весов для симметрично расположенных пар букв проверяемого слова.

1. #include <stdio.h>
2. #include <string.h>
3. 
   
4. int Sp(char*);
5. int s(char, char);
6. 
   
7. int main()
8. {
9.         FILE *in, *out;
10.         // проверяемое слово
11.         char *str = new char[11];
12. 
    
13.         in = fopen("spinity.in", "r");
14.         out = fopen("spinity.out", "w");
15. 
    
16.         // считывает по одному слову из файла,
17.         // подсчитываем его вращаемость
18.         // и сразу же записываем результат в файл
19.         while(fscanf(in, "%s", str) != EOF)
20.         {
21.                 fprintf(out, "%s %d\n", str, Sp(str));
22.         }
23. 
    
24.         fclose(in);
25.         fclose(out);
26. 
    
27.         return 0;
28. }
29. 
    
30. int Sp(char *str)
31. {
32.         // вращаемость слова как сумма значений функции s
33.         int sum = 0;
34. 
    
35.         // перебираем симметрично расположенные пары букв
36.         // и для каждой пары вызываем функцию s
37.         for(int i = 0; i < strlen(str); i++)
38.                 sum += s(str[i], str[strlen(str)-1-i]);
39. 
    
40.         return sum;
41. }
42. 
    
43. int s(char c1, char c2)
44. {
45.         // если буквы совпадают и являются автосимметричными
46.         if(((c1 == 'o') && (c2 == 'o')) || ((c1 == 'l') && (c2 == 'l')) ||
47.            ((c1 == 's') && (c2 == 's')) || ((c1 == 'x') && (c2 == 'x')))
48.                 return 3;
49.         // если буквы не совпадают, но составляют симметричную пару
50.         else if((((c1 == 'b') && (c2 == 'q')) || ((c2 == 'b') && (c1 == 'q'))) ||
51.                   (((c1 == 'd') && (c2 == 'p')) || ((c2 == 'd') && (c1 == 'p'))) ||
52.                   (((c1 == 'm') && (c2 == 'w')) || ((c2 == 'm') && (c1 == 'w'))) ||
53.                   (((c1 == 'n') && (c2 == 'u')) || ((c2 == 'n') && (c1 == 'u'))))
54.                 return 2;
55.         // если буквы совпадают, но не являются автосимметричными
56.         else if(c1 == c2)
57.                 return 1;
58.         // во всех остальных случаях
59.         else
60.                 return 0;
61. }