Ответы информатика ВСОШ СИРИУС 9-11 класс 24 октября группа 1

2. Поле в игре «Речной бой» представляет собой полоску длины м клеток и шириной в одну клетку. Где-то на поле расположен корабль из к клеток (к < п). Какое наименьшее число выстрелов необходимо, чтобы гарантированно потопить корабль? После каждого выстрела сообщается его результат: «мимо», «ранен» или «убит».

С++:

• #include <iostream>
• using namespace std;
• int main() {
• int n; cin >> n;
• int k; cin >> k;
• cout << n / k + k — 1;
• }

3. Алиса решила поздравить своего друга с началом нового учебного года. Впереди холодная осень, поэтому она решила связать для него собственными руками шарф. Незаметно для друга Алиса узнала, что ему большего всего нравятся K различных цветов.

Алиса приняла решение связать шарф размером п × т, в котором будут чередоваться полоски различных цветов. Её друг никогда не ищет лёгких путей, поэтому она решила, что шаро с горизонтальными или вертикальными полосками покажется ему слишком примитивным. Алиса решила? что полоски определенно должны быть диагональными!

Закончив вязать шарф, Алиса вспомнила, что один из к цветов её друг считает особенным

Это цвет с, который, по его мнению, приносит школьникам удачу на олимпиадах по информатике. И Алисе стало невероятно интересно, сколько фрагментов шарфа имеют именно такой цвет. Шарф получился очень большим, Алиса очень устала, пока его вязала, поэтому сама она уже не может ответить на этот вопрос и просит вас о помощи…

Более формально шарф можно представить в виде таблицы размером п × т, каждая клетка

которой покрашена в один из К цветов. Цвета нумеруются от 1 по k

Первая строка таблицы покрашена в цвета 1, 2,… ,k, 1,2…., k и т.д.

Каждая следующая строка получена из предыдущей сдвигом влево на одну клетку. Таким образом, таблица

состоит из диагональных полос

При n = 4, m = 8 и к = 3 таблица будет иметь следующий вид:

Ответ:

С++:

• #include <iostream>
• using namespace std;
• int main()
• {
• int n, m, k, c;
• cin >> n >> m >> k >> c;
• if (m % k == 0) {
• cout << n * k;
• }
• else {
• int sum = (n / k) * ((m / k + 1) * (m % k) + (m / k) * (k — m % k));
• if (n % k == 0) {
• cout << sum;
• }
• else {
• cout << sum + (k — 1) * (n % k) + min(c, n % k) + max(0, c — k — n % k);
• }
• }
• }

4. В гостинице пля жирафов администрация хочет запастись полушками так, чтобы удовлетворить потребности любого своего возможного постояльца. Известно, что жирафам в зависимости от длины их шеи нужно сложить стопку подушек (в стопке одна или несколько полушек) толщиной от 1 до n сантиметров. При этом администрация хочет обойтись как можно меньшим числом подушек, а среди наборов подушек, удовлетворяющих этим требованиям, администрация выберет набор минимальной суммарной толщины, чтобы он занимал минимальный объём в шкафу. Помогите администрации составить нужный набор подушек, позволяющий получить стопку любой высоты от 1 до n сантиметров включительно.

Ответ:

С++:

• #include <iostream>
• using namespace std;
• #define ll long long
• int main() {
•      ll n; cin >> n;
•      for (ll i = 1; i * 2 — 1 < n; i *= 2) {
•          cout << i << » «;
•          if (i * 4 — 1 >= n) {
•             cout << n — i * 2 + 1 << » «;
•             break;
•          }
•      }
• }

5. У радиолюбителя Алексея есть девятисегментный жидкокристаллический индикатор,  который может показывать цифры от 0 до 9 в виде цифр «почтового индекса». После неудачного эксперимента индикатор повредился, и часть сегментов могла перегореть. Когда сегмент перегорает, индикатор теряет возможность показывать шифры, использующие этот сегмент. Алексей уже выяснил, что индикатор всё ещё способен показать какие-то п цифр. Однако радиолюбитель не может проверить остальные цифры, равно как и каждый сегмент отдельно. Поэтому он просит вас помочь найти те цифры, которые гарантированно можно показать на этом индикаторе.

Ответ:

C++:

• #include <iostream>
• #include <vector>
• using namespace std;
• int main()
• {
•      int n; cin >> n;
•      vector<int> a(n);
•      vector<vector<int>> b = { {1, 2, 4, 6, 8, 9}, {3, 4, 8}, {1, 4, 7,
• 9}, {1, 3, 5, 7}, {2, 4, 5, 8}, {1, 2, 5, 8, 9}, {3, 5, 6, 8, 9}, {1,
• 3, 6}, {1, 2, 4, 5, 6, 8, 9}, {1, 2, 4, 5, 7} };
•       vector<int> c(10);
•       for (int i = 0; i < n; i++) {
•            cin >> a[i];
•            for (int j = 0; j < b[a[i]].size(); j++) {
•                 c[b[a[i]][j]] = 1;
•            }
•        }
•       for (int i = 0; i < 10; i++) {
•           bool ok = true;
•           for (int j = 0; j < b[i].size(); j++) {
•                if (!c[b[i][j]]) ok = false;
•           }
•          if (ok) cout << i << ‘\n’;
•       }
•      return 0;
• }