Решения некоторых задач с сайта informatics.msk.ru

Irval · 26 Дек 2020

Довольно часто мне пишут насчет задачек с этого сайта. Я подумал, что неплохо было бы делиться всеми решениями, которые я отправляю людям. Тема будет обновляться нерегулярно, но все равно постараюсь на нее не забивать.
Язык программирования в основном C#, но иногда буду публиковать и C++, Python. Предложить задачку можно мне в Telegram или ВКонтакте, по возможности отвечу.
Можете также выкладывать свои решения задачек, соблюдая шаблон сообщения ниже :)

Irval · 26 Дек 2020

Номер задачи: 112366
Язык программирования: C#
Личное мнение: легкая задача, но много нюансов
Исходный код:

C#:

using System;
using System.Linq;

namespace Informatics
{
    class Program
    {
        static void Main(string[] args)
        {
            int n, m;
            var data = Console.ReadLine().Split(' ');
            n = Convert.ToInt32(data[0]);
            m = Convert.ToInt32(data[1]);
            int min = 0, max = 0;
            bool Min = true, Max = true;
            int[] _min = new int[2];
            int[] _max = new int[2];
            for (int i = 0; i < n; i++)
            {
                string str = Console.ReadLine();
                var d = str.Split(' ').Select(int.Parse).ToList();
                int _Min = d.Min();
                int _Max = d.Max();
                if (Min || _Min < min || (_Min == min && (_min[0] > i || (_min[0] == i && _min[1] > d.IndexOf(_Min)))))
                {
                    min = _Min;
                    _min[0] = i;
                    _min[1] = d.IndexOf(_Min);
                    Min = false;
                }
                if (Max || _Max > max || (_Max == max && (_max[0] > i || (_max[0] == i && _max[1] > d.IndexOf(_Max)))))
                {
                    max = _Max;
                    _max[0] = i;
                    _max[1] = d.IndexOf(_Max);
                    Max = false;
                }

            }
            Console.WriteLine($"{_min[0] + 1} {_min[1] + 1} {min}");
            Console.WriteLine($"{_max[0] + 1} {_max[1] + 1} {max}");
            Console.ReadKey();
        }
    }
}

Готовый файл .cs/.py/.cpp:

Пожалуйста, авторизуйтесь для просмотра ссылки.

Irval · 26 Дек 2020

Номер задачи: 112400
Язык программирования: C#
Личное мнение: достаточно легкая задача. Однако, информатикс просто не хочет ее принимать (такая проблема не только с моим решением)
Исходный код:

C#:

using System;
using System.Collections.Generic;
using System.IO;

namespace Informatics
{
    class Program
    {
        static void Main(string[] args)
        {
            int? min = null;
            List<string> members = new List<string>();
            using (StreamReader sr = new StreamReader("input.txt"))
            {
                string line;
                while (!sr.EndOfStream)
                {
                    line = sr.ReadLine();
                    if (min == null)
                        min = Convert.ToInt32(line);
                    else
                    {
                        var data = line.Split(' ');
                        if (Convert.ToInt32(data[2]) > min)
                            members.Add($"{members.Count + 1}) {data[1][0]}. {data[0]}");
                    }
                }
            }
            members.Add(members.Count.ToString());
            File.WriteAllLines("output.txt", members);
        }
    }
}

Готовый файл .cs/.py/.cpp:

Пожалуйста, авторизуйтесь для просмотра ссылки.

Irval · 26 Дек 2020

Номер задачи: 357
Язык программирования: C#
Личное мнение: достаточно легкая задача
Исходный код:

C#:

using System;
using System.Collections.Generic;
using System.Linq;

namespace Informatics
{
    class Program
    {
        static void Main(string[] args)
        {
            int n, m;
            var data = Console.ReadLine().Split(' ');
            n = Convert.ToInt32(data[0]);
            m = Convert.ToInt32(data[1]);
            List<int> m1 = new List<int>();
            List<int> m2 = new List<int>();

            for (int i = 0; i < n; i++)
            {
                var list = Console.ReadLine().Split(' ').Select(int.Parse).ToList();
                m1.Add(list.Max());
                m2.Add(list.IndexOf(m1[i]));
            }

            int max = m1.Max();

            Console.WriteLine(max.ToString());
            Console.WriteLine($"{m1.IndexOf(max)} {m2[m1.IndexOf(max)]}");
            Console.ReadKey();
        }
    }
}

Готовый файл .cs/.py/.cpp:

Пожалуйста, авторизуйтесь для просмотра ссылки.

Irval · 26 Дек 2020

Номер задачи: 112367
Язык программирования: C#
Личное мнение: достаточно легкая задача
Исходный код:

C#:

using System;
using System.Collections.Generic;
using System.Linq;

namespace Informstics
{
    class Program
    {
        static void Main(string[] args)
        {
            int n, m;
            var data = Console.ReadLine().Split(' ');
            n = Convert.ToInt32(data[0]);
            m = Convert.ToInt32(data[1]);
            List<List<int>> strs = new List<List<int>>();
            string minStr = "";
            int min = -1;
            for (int i = 0; i < n; i++)
            {
                string str = Console.ReadLine();
                var d = str.Split(' ').Select(int.Parse).ToList();
                if (min == -1 || d.Sum() < min)
                {
                    min = d.Sum();
                    minStr = str;
                }
            }
            Console.WriteLine(minStr);
            Console.ReadKey();
        }
    }
}

Готовый файл .cs/.py/.cpp:

Пожалуйста, авторизуйтесь для просмотра ссылки.

Irval · 26 Дек 2020

Номер задачи: 119
Язык программирования: C++
Личное мнение: изначально легкая задача, но из-за доп. задания от моего препода становится не такой простой ;). Главная цель решения - максимальная оптимизация, из-за чего простой перебор становится бесполезным. За основу взял комбинаторику.
Исходный код:

C++:

#include <iostream>

using namespace std;

int getNum3(int s, int de)
{
    int i;
    for (i = 0; i * 10 + s <= de && i <= 9; i++){}

    return i;
}

int getNum4(int t, int sde)
{
    int i;
    for (i = 0; i * 100 + i * 10 + t <= sde && i <= 9; i++){}

    return i;
}

int getNum5(int tt, int tsde)
{
    int i, j = 0, k = 0;
    for (i = 0; i * 1000 + j * 100 + i * 10 + tt <= tsde && i <= 9; i++)
        for (j = 0; i * 1000 + j * 100 + i * 10 + tt <= tsde && j <= 9 ; j++)
            k++;

    return k;
}

int main()
{
    int num = 0, k = 1;
    int n1 = 0, n2 = 0, n3 = 0;

    cin >> num;

    for (int i = 10; i <= num; i *= 10)
        k++;

    switch (k)
    {
        case 1:
            cout << num;
            break;
    case 2:
            cout << 9 + num / 11;
            break;
    case 3:
            n1 = num / 100, n2 = num % 100 / 10;
            cout << 18 + (n1 - 1) * 10 + getNum3(n1, num % 100);
            break;
    case 4:
            n1 = num / 1000, n2 = num % 1000 / 100;
            cout << 108 + (n1 - 1) * 10 + getNum4(n1, num % 1000);
            break;
    case 5:
            n1 = num / 10000, n2 = num % 10000 / 1000, n3 = num % 1000 / 100;
            cout << 198 + (n1 - 1) * 100 + getNum5(n1, num % 10000);
            break;
    case 6:
            cout << 1098;
            break;
    }

    return 0;
}

Готовый файл .cs/.py/.cpp:

Пожалуйста, авторизуйтесь для просмотра ссылки.

Irval · 26 Дек 2020

Номер задачи: 3078
Язык программирования: C++
Личное мнение: обычная задача на обработку последовательности
Исходный код:

C++:

#include <iostream>
#include <cmath>

using namespace std;

int main()
{
    int num, last = 0, min = 0, max = 0;
    int dif = 0, last_dif = 0;
    int _max = 0, _min = 0;

    cin >> num;

    while (num != 0)
    {
        dif = num - last;

        if (last_dif >= 0 && dif > 0)
            _max++;
        else if (last_dif <= 0 && dif < 0)
            _min++;
        else
        {
            if (last_dif > 0)
            {
                if (_max > max)
                    max = _max;
                if (dif != 0)
                {
                    _max = 0;
                    _min = 2;
                }
                else {
                    _max = 1;
                    _min = 0;
                }
            }
            else
            {
                if (_min > min)
                    min = _min;
                if (dif != 0)
                {
                    _min = 0;
                    _max = 2;
                }
                else {
                    _max = 1;
                    _min = 0;
                }
            }
        }

        last = num;
        last_dif = dif;
        cin >> num;
    }
    
    max = (_max > max ? _max : max);
    min = (_min > min ? _min : min);

    cout << (max >= min ? max : min);

    return 0;
}

Готовый файл .cs/.py/.cpp:

Пожалуйста, авторизуйтесь для просмотра ссылки.

Irval · 28 Дек 2020

Номер задачи: 1425
Язык программирования: C++
Личное мнение: интересная оптимизация задачи на метод подсчета
Исходный код:

C++:

#include <iostream>
#include <string>

using namespace std;

int main() {
    long long mas[215] = {};
    long long first = 0;
    int N;
    cin >> N;
    cin >> first;
    mas[107]++;
    for (int i = 1; i < N; i++) {
        long long tmp;
        cin >> tmp;
        mas[107 - (first - tmp)]++;
    }
    for (int i = 0; i < 215; i++) {
        for (int j = 0; j < mas[i]; j++) {
            cout << first - (107 - i) << " ";
        }
    }

}

Готовый файл .cs/.py/.cpp:

Пожалуйста, авторизуйтесь для просмотра ссылки.

Irval · 1 Янв 2021

Номер задачи: 1444
Язык программирования: C++, C#
Личное мнение: обычная задача на двумерные массивы
Исходный код:

C++:

#include <iostream>
#include <iomanip>

using namespace std;

int main() {
    int N, M, W;
    cin >> N >> M >> W;
    int field[32][32] = {};
    for (int i = 0; i < W; i++) {
        int inf[2];
        cin >> inf[0] >> inf[1];
        inf[0]--; inf[1]--;
        field[inf[0]][inf[1]] = 10;
        for (int y = inf[0] != 0 ? inf[0] - 1 : inf[0]; y <= (inf[0] != N - 1 ? inf[0] + 1 : inf[0]); y++) {
            for (int x = inf[1] != 0 ? inf[1] - 1 : inf[1]; x <= (inf[1] != M - 1 ? inf[1] + 1 : inf[1]); x++) {
                if (!(y == inf[0] && x == inf[1]))
                    field[y][x]++;
            }
        }
    }
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++)
            cout << (field[i][j] < 9 ? (char)(field[i][j] + '0') : '*') << " ";
        cout << endl;
    }
    system("pause");
}

C#:

using System;

namespace ConsoleApp1
{
    class Program
    {
        static void Main(string[] args)
        {
            int N, M, W;
            string[] input = Console.ReadLine().Split(' ');
            N = Convert.ToInt32(input[0]);
            M = Convert.ToInt32(input[1]);
            W = Convert.ToInt32(Console.ReadLine());
            int[,] field = new int[32, 32];
            for (int i = 0; i < N; i++)
                for (int j = 0; j < M; j++)
                    field[i, j] = 0;
            for (int i = 0; i < W; i++)
            {
                input = Console.ReadLine().Split(' ');
                int[] inf = new int[2] { Convert.ToInt32(input[0]), Convert.ToInt32(input[1]) };
                inf[0]--; inf[1]--;
                field[inf[0], inf[1]] = 10;
                for (int y = inf[0] != 0 ? inf[0] - 1 : inf[0]; y <= (inf[0] != N - 1 ? inf[0] + 1 : inf[0]); y++)
                {
                    for (int x = inf[1] != 0 ? inf[1] - 1 : inf[1]; x <= (inf[1] != M - 1 ? inf[1] + 1 : inf[1]); x++)
                    {
                        if (!(y == inf[0] && x == inf[1]))
                            field[y, x]++;
                    }
                }
            }
            for (int i = 0; i < N; i++)
            {
                for (int j = 0; j < M; j++)
                    Console.Write((field[i, j] < 9 ? field[i, j].ToString() : "*") + " ");
                Console.Write("\n");
            }
            Console.ReadKey();
        }
    }
}

Готовый файл .cs/.py/.cpp:

Пожалуйста, авторизуйтесь для просмотра ссылки.

,

Пожалуйста, авторизуйтесь для просмотра ссылки.

Irval · 5 Фев 2021

Номер задачи: 1596
Язык программирования: C++
Личное мнение: интересная задача на матрицы, часто видел похожие в курсах геймдева
Исходный код:

C++:

#include <iostream>
#include <string>

using namespace std;

int Min(int mas[], int size, int& pos) {
    int _min = 10001;
    for (int i = 0; i < size; i++) {
        if (_min > mas[i]) {
            _min = mas[i];
            pos = i;
        }
    }
    return _min;
}

string isMax(int mas[], int size, int _pos[100][3], int _size, int& count) {
    int _max = 0, pos;
    for (int i = 0; i < size; i++) {
        if (_max < mas[i]) {
            _max = mas[i];
            pos = i;
        }
    }
    for (int i = 0; i < _size; i++) {
        if (_max == _pos[i][0] && pos == _pos[i][1]) {
            count++;
            return to_string(_pos[i][1] + 1) + " " + to_string(_pos[i][2] + 1) + "\n";
        }
    }
    return "";
}

void Input(int n, int m, int mas[100][100], int _pos[100][3]) {
    int pos;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++)
            cin >> mas[i][j];
        int min = Min(mas[i], m, pos);
        _pos[i][0] = min, _pos[i][1] = i, _pos[i][2] = pos;
    }
}

void Output(int n, int m, int mas[100][100], int _pos[100][3]) {
    auto _1 = _pos;
    int _mas[100][100];
    for (int j = 0; j < m; j++) {
        for (int i = 0; i < n; i++)
            _mas[j][i] = mas[i][j];
    }
    int count = 0;
    for (int i = 0; i < m; i++)
        cout << isMax(_mas[i], m, _pos, n, count);
    if (!count)
        cout << 0;
}

int main() {
    int n, m, mas[100][100], _pos[100][3];
    cin >> n >> m;
    Input(n, m, mas, _pos);
    Output(n, m, mas, _pos);
}

Готовый файл .cs/.py/.cpp:

Пожалуйста, авторизуйтесь для просмотра ссылки.

Irval · 5 Фев 2021

Номер задачи: 365
Язык программирования: C++
Личное мнение: более сложный вариант заполнения спиралью, решение немного облегчает квадратная форма матрицы
Исходный код:

C++:

#include <iostream>
#include <iomanip>
#include <math.h>

using namespace std;

int main() {
    int n;
    cin >> n;
    int mas[201][201] = {}, last = pow(2 * n + 1, 2) - 1, k = 0;
    int status = 0;
    while (last) {
        switch (status) {
        case 0:
            for (int i = k / 4; i <= 2 * n - k / 4; i++)
                mas[i][2 * n - k / 4] = last--;
            break;
        case 1:
            for (int j = 2 * n - k / 4 - 1; j >= k / 4; j--)
                mas[2 * n - k / 4][j] = last--;
            break;
        case 2:
            for (int i = 2 * n - k / 4 - 1; i >= k / 4; i--)
                mas[i][k / 4] = last--;
            break;
        case 3:
            for (int j = k / 4 + 1; j <= 2 * n - k / 4 - 1; j++)
                mas[k / 4][j] = last--;
            break;
        }
        k++;
        if (++status > 3)
            status = 0;
    }

    for (int i = 0; i < n * 2 + 1; i++) {
        for (int j = 0; j < n * 2 + 1; j++)
            cout << setw(3) << mas[i][j] << " ";
        cout << endl;
    }
}

Готовый файл .cs/.py/.cpp:

Пожалуйста, авторизуйтесь для просмотра ссылки.

Irval · 6 Фев 2021

Номер задачи: 1436
Язык программирования: C++
Личное мнение: простая задача на отображения состояния сортировки вставками
Исходный код:

C++:

#include <iostream>

using namespace std;

int main()
{
    long long N, mas[100];
    cin >> N;
    for (int i = 0; i < N; i++)
        cin >> mas[i];

    long long L, R, m;

    for (int i = 1; i < N; i++) {
        L = 0, R = i;
        m = i / 2;

        while (L < R) {
            if (mas[i] > mas[m]) L = m + 1;
            else if (mas[i] < mas[m]) R = m;
            else break;
            m = L + (R - L) / 2;
        }

        if (m < i) {
            int flag = 0;
            int t = mas[i];
            for (int j = i - 1; j >= m; j--) {
                flag += mas[j] != mas[j + 1];
                mas[j + 1] = mas[j];
            }
            flag += mas[m] != t;
            mas[m] = t;
            if (flag) {
                for (int i = 0; i < N; i++)
                    cout << mas[i] << " ";
                cout << endl;
            }
        }
    }
}

Готовый файл .cs/.py/.cpp:

Пожалуйста, авторизуйтесь для просмотра ссылки.

Irval · 19 Фев 2021

Номер задачи: 1600
Язык программирования: C++
Личное мнение: на первый взгляд не совсем тривиальная задача решается в 10 строк кода :3
Исходный код:

C++:

#include <iostream>
#include <string>

using namespace std;

bool Compare(string s) {
    return s == string(s.crbegin(), s.crend());
}

int main() {
    string s;
    getline(cin, s);
    if (Compare(s)) {
        cout << 0;
        return 0;
    }
    int ind = 1;
    while (!Compare(s.substr(ind)))
        ind++;
    cout << ind;
}

Готовый файл .cs/.py/.cpp:

Пожалуйста, авторизуйтесь для просмотра ссылки.

Irval · 2 Май 2021

Номер задачи: 747
Язык программирования: C++
Личное мнение: обычная задача на быстрый алгоритм перевода между системами счисления
Исходный код:

C++:

#include <iostream>
#include <string>
#include <map>

using namespace std;

int main() {
    string s, s1 = "";
    getline(cin, s);

    map<string, string> dict = { {"0", "0000"}, {"1", "0001"}, {"2", "0010"}, {"3", "0011"}, {"4", "0100"}, {"5", "0101"},
    {"6", "0110"}, {"7", "0111"}, {"8", "1000"}, {"9", "1001"}, {"A", "1010"}, {"B", "1011"}, {"C", "1100"}, {"D", "1101"},
    {"E", "1110"}, {"F", "1111"} };

    for (int i = s.length() - 1; i > 0; i--)
        s1 = dict[s.substr(i, 1)] + s1;

    string last = dict[s.substr(0, 1)];
    cout << atoi(last.c_str());
    cout << s1;
}

Готовый файл .cs/.py/.cpp:

Пожалуйста, авторизуйтесь для просмотра ссылки.

Irval · 2 Май 2021

Номер задачи: 748
Язык программирования: C++
Личное мнение: обычная задача на быстрый алгоритм перевода между системами счисления
Исходный код:

C++:

#include <iostream>
#include <string>
#include <map>

using namespace std;

int main() {
    string s, s1 = "";
    getline(cin, s);

    map<string, string> dict = { {"0000", "0"}, {"0001", "1"}, {"0010", "2"}, {"0011", "3"}, {"0100", "4"}, {"0101", "5"},
    {"0110", "6"}, {"0111", "7"}, {"1000", "8"}, {"1001", "9"}, {"1010", "A"}, {"1011", "B"}, {"1100", "C"}, {"1101", "D"},
    {"1110", "E"}, {"1111", "F"} };

    for (int i = s.length() / 4; i > 0; i--)
        s1 = dict[s.substr(s.length() % 4 + (i - 1) * 4, 4)] + s1;

    if (s.length() % 4) {
        string last = s.substr(0, s.length() % 4);
        while (last.length() < 4) last = "0" + last;
        cout << dict[last];
    }
    cout << s1;
}

Готовый файл .cs/.py/.cpp:

Пожалуйста, авторизуйтесь для просмотра ссылки.

Irval · 2 Май 2021

Номер задачи: 1611
Язык программирования: C++
Личное мнение: слишком много условий :confused:
Исходный код:

C++:

#include <string>
#include <iostream>

using namespace std;

void Correct(string& s) {
    for (int i = 0; i < s.size(); i++) {
        if (s[i] == ' ' && (i == 0 || s[i - 1] == ' ')) {
            s.erase(i, 1);
            i--;
        }
    }
    if (s[0] == ' ')
        s.erase(0, 1);
    if (s[s.length() - 1] == ' ')
        s.erase(s.length() - 1);
}

bool isP(string s) {
    if (s.find(' ') != s.npos)
        return false;

    bool isNum = true;
    for (int i = 0; i < s.length(); i++) {
        if (s[i] >= '0' && s[i] <= '9') {
            if (isNum)
                return false;
        }
        else if (s[i] >= 'a' && s[i] <= 'z' || s[i] >= 'A' && s[i] <= 'Z' || s[i] == '_') {
            if (isNum)
                isNum = false;
        }
        else
            return false;
    }
    return true;
}

int main() {
    string s;
    getline(cin, s);
    if (s.length() < 4) {
        cout << "NO";
        return 0;
    }
    Correct(s);
    int index = s.find(":=");
    if (index == s.npos) {
        cout << "NO";
        return 0;
    }

    string s1 = s.substr(0, index), s2 = s.substr(index + 2);
    if (s1.length() == 0 || s2.length() == 0) {
        cout << "NO";
        return 0;
    }
    Correct(s1), Correct(s2);
    if (s1 == "true" || s1 == "false" || s2 == "true" || s2 == "false" || !isP(s1)) {
        cout << "NO";
        return 0;
    }

    bool isBad = false;

    bool isFirst = true;
    bool wasMinus = false;
    int spaceEnd = 0;
    for (int i = 0; i < s2.length(); i++) {
        if (s2[i] == '-' && isFirst) {
            wasMinus = true;
            continue;
        }
        if (isFirst)
            isFirst = false;

        if (s2[i] == ' ' && wasMinus)
            continue;
        if (wasMinus) {
            wasMinus = false;
            spaceEnd = i;
        }
            
        if (!(s2[i] >= '0' && s2[i] <= '9')) {
            isBad = true;
            break;
        }
    }

    if (s2.substr(spaceEnd).find(' ') != s2.npos) {
        cout << "NO";
        return 0;
    }

    if (isBad)
        cout << (isP(s2) ? "YES" : "NO");
    else
        cout << "YES";
}

Готовый файл .cs/.py/.cpp:

Пожалуйста, авторизуйтесь для просмотра ссылки.

Решения некоторых задач с сайта informatics.msk.ru

Похожие темы