Быки и коровы

@Даня98 · Регистрация: 13.02.2010

Студворк — интернет-сервис помощи студентам

Есть такая задача быки о коровы. Условие: http://acmp.ru/?main=task&id_task=13. Код моего решения:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <fstream>
#include <string>
int main()
{
    std:: string t,f;
    int buki=0, korovy=0;
    std:: fstream ifs ("input.txt");
    ifs >> t >> f;   //чтение из файла
    ifs.close();
    
    for (int i=0; i<5; i++)
    if (t[i]==f[i])  //кол-во быков
    {
       buki++;
       f.erase (i-1,1);
    }
    for (int i=0;i<f.size(); i++)     //кол-во коров
    if (t.find(f[i])!=-1) korovy++;
    
    std:: ofstream ofs ("output.txt");
    ofs << buki << " " << korovy; //вывод
    ofs.close();
    return 0;
}

Но оно неправильно выдает кол-во коров. Т.к. я изучаю Си++ всего несколько недель, не могли бы Вы помочь найти здесь ошибку?

@don khuan · 10.08.2011, 16:23

Количество быков тоже неправильно выдает. все потому что во время выполнения цикла

C++
1
2
3
4
5
6
    for (int i=0; i<5; i++)
    if (t[i]==f[i])  //кол-во быков
    {
       buki++;
       f.erase (i-1,1);
    }

если бык найден, то удаляется символ из строки f, смещаются индексы и получается так, что к концу цикла в f не хватает элементов

как вариант - убрать удаление и в поиске коров добавить условие t[i]!=f[i]

Jupiter · 10.08.2011, 16:56

строки сдесь не нужны

решение

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <fstream>
 
int main()
{
    unsigned petya, vasya;
    std::fstream ifs("input.txt");
    std::ofstream ofs("output.txt");
    ifs >> petya >> vasya;   //чтение из файла
 
    unsigned peet[4], vas[4];
    for (unsigned i = 0; i < 4; ++i, petya /= 10, vasya /= 10)
    {
        peet[4-i-1] = petya % 10;
        vas[4-i-1]  = vasya % 10;
    }
 
    unsigned bulls(0), cows(0);
    for (unsigned i = 0; i < 4; ++i)
    {
        for (unsigned j = 0; j < 4; ++j)
        {
            if (peet[i] == vas[j])
            {
                if (i == j)
                    ++bulls;
                else
                    ++cows;
            }
        }
    }
 
    ofs << bulls << ' ' << cows;
    return 0;
}

@Даня98 · 10.08.2011, 16:58 **[ТС]**

Сообщение от Maxwe11

строки сдесь не нужны

Я не просил решение ибо мне надо понять свою ошибку.

Jupiter · 10.08.2011, 17:05

Сообщение от Даня98

мне надо понять свою ошибку.

тогда сначала распишите ваше решение на бумаге, потом еще раз прочитайте условие задачи

Добавлено через 1 минуту

Сообщение от Даня98

C++
1
for (int i=0; i<5; i++)

так как нумерация массивов с нуля, то правильным условием завершения цикла должно быть i < 4

@Даня98 · 10.08.2011, 17:08 **[ТС]**

Сообщение от Maxwe11

тогда сначала распишите ваше решение на бумаге, потом еще раз прочитайте условие задачи

Решение я расписал, быков переделаю но можете сказать как правильно сделать поиск коров со строками (не обращая внимания на быков). Как я уже говорил, Си++ я изучаю несколько недель и просто несколько сомневаюсь в коде а не псевдокоде на бумаге.

@talis · 10.08.2011, 17:42

Даня98, можно в двух циклах. В первом проходите первую группу символов, во втором вторую. Во втором цикле поверяете: если символы равны и стоят на одинаковой позиции, инкрементируете счётчик быков, если же символы равны, но стоят на разных позициях, то инкрементируете счётчик коров.

Посмотреть код

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
//#include <iostream> // для cerr
#include <fstream>
 
using namespace std;
 
int main()
{
    ifstream in  ( "input.txt" );
    ofstream out ( "output.txt" );
 
    char instr[10];
 
    in.get( instr, 10 );
 
    // опционально ------------------------
    //if( instr[4] != ' ' || instr[9] != 0 )
    //{
    //   cerr << "wrong format" << endl;
    //   return -1;
    //}
    // -------------------------------------
 
    char bulls = 0, cows = 0;
 
    for( char i = 0; i < 4; i++ )
    {
        for( char u = 5; u < 9; u++ )
        {
            if( instr[i] == instr[u] )
            {
                if( i == u - 5 )
                   bulls++;
                else
                   cows++;
            }
        }
    }
 
    out << (int)bulls << ' ' << (int)cows;
 
    return 0;
}

Таким образом за один раз находите и всех быков, и всех коров.

Добавлено через 2 минуты
Можно ещё больше сэкономить, если сделать на C

Добавлено через 6 минут

На C

C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <stdio.h>
 
int main()
{
    FILE * in = fopen( "input.txt", "r" );
    FILE * out = fopen ( "output.txt", "w" );
 
    if( !in || !out )
       return -1;
 
    char instr[10];
 
    fread( instr, 1, 10, in );
 
    unsigned char bulls = 0, cows = 0, i = 0, u;
 
    for( ; i < 4; i++ )
    {
        for( u = 5; u < 9; u++ )
        {
            if( instr[i] == instr[u] )
            {
                if( i == u - 5 )
                   bulls++;
                else
                   cows++;
            }
        }
    }
 
    instr[0] = bulls + 0x30;
    instr[1] = ' ';
    instr[2] = cows + 0x30;
 
    fwrite( instr, 1, 3, out );
 
    fclose( in );
    fclose( out );
 
    return 0;
}

@Olga_ · 10.08.2011, 19:02

Зачем алгоритмы с такой сложностью, во всех вариантах, представленных выше сложность алгоритма O(n^2), где n - количество разрядов в числе. Вот элегантный алгоритм сложности O(n):

C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
void Count(int *x, int *y, int n, int *bull, int *cow)
{
   int i, flag[10] = {0};
   *bull = *cow = 0;
   for (i = 0; i < n; i++)
      if (x[i] == y[i])
         (*bull)++;
      else
         flag[x[i]] = 1;
   for (i = 0; i < n; i++)
      if (flag[y[i]])
         (*cow)++;
}
 
int main()
{
   int x[4] = {1,2,3,4}, y[4] = {2,5,3,1};
   int bull, cow;
   Count(x, y, 4, &bull, &cow);
   printf("bull = %d cow = %d\n", bull, cow);
   return 0;
}

@diagon · 10.08.2011, 19:20

Сообщение от Olga_

Зачем алгоритмы с такой сложностью, во всех вариантах, представленных выше сложность алгоритма O(n^2), где n - количество разрядов в числе. Вот элегантный алгоритм сложности O(n):

Позвольте с вами не согласится =)
В настолько детской задаче не имеет значения сложность алгоритма, даже при O(n^2), получается O(16)...
Гораздо важнее случайно не допустить где-нибудь ошибку(я про условия настоящей олимпиады, ну или если не стоит цель попасть в лучшие попытки, как у меня =) ).
А с использованием контейнеров и алгоритмов STL ошибку допустить очень сложно.
Но есть специальные задачи, в которых важна именно оптимальность алгоритма. Порешайте задачи из темы "Динамическое программирование" на acmp, вам понравится =)

@talis · 10.08.2011, 19:25

Olga_, действительно, ваш алгоритм лучше. Если уж идти в сторону оптимизации, то можно отказаться от хранения чисел 0-9 в четырёх байтах int и хранить их в char, и выставлять 10 флагов не как 10 int по 4 байта каждый, а как 10 бит (в пределах двух байт). Уйму памяти сэкономим...

Оптимизируем дальше

C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
void Count(char *x, char *y, char n, char *bull, char *cow)
{
   char i;
   unsigned short flag = 0;
 
   *bull = *cow = 0;
 
   for ( i = 0; i < n; i++ )
   {
      if ( x[i] == y[i] )
         (*bull)++;
      else
         flag |= 1 << x[i];
   }
 
 
   for ( i = 0; i < n; i++ )
   {
      if ( flag & 1 << y[i] )
         (*cow)++;
   }
}
 
int main()
{
   char x[4] = { 0,2,3,4 },
        y[4] = { 1,8,6,3 };
 
   char bull, cow;
 
   Count( x, y, 4, &bull, &cow );
 
   printf( "bull = %d cow = %d\n", bull, cow );
   return 0;
}

Так же для ликвидации накладных расходов на вызов функции, можно и от неё отказаться :-)

@Olga_ · 10.08.2011, 19:28

Сообщение от diagon

Позвольте с вами не согласится...

Да вы правы, правы, Diagon, 100 раз правы, глупо было залезть в детскую тему. Пусть это будет как вариант, кто-то подумает, проанализирует, может понравится

Добавлено через 2 минуты

Сообщение от talis

Olga_, действительно, ваш алгоритм лучше. Если уж идти в сторону оптимизации, то можно отказаться от хранения чисел 0-9 в четырёх байтах int и хранить их в char, и выставлять 10 флагов не как 10 int по 4 байта каждый, а как 10 бит (в пределах двух байт).

И вы правы

С битами очень удобно

@Даня98 · 10.08.2011, 22:42 **[ТС]**

Сообщение от Olga_

Зачем алгоритмы с такой сложностью, во всех вариантах, представленных выше сложность алгоритма O(n^2), где n - количество разрядов в числе. Вот элегантный алгоритм сложности O(n):

У Вас не правильный алгоритм: введите 1234 1234 должно вывести 4 0, а у вас выводит 1 3.

Алгоритм O(N^2) работает правильнее чем O(N)

@Olga_ · 11.08.2011, 08:05

Сообщение от Даня98

У Вас не правильный алгоритм: введите 1234 1234 должно вывести 4 0, а у вас выводит 1 3.

Алгоритм O(N^2) работает правильнее чем O(N)

Даня98, вы как проверяли? Проверьте еще раз

C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void Count(int *x, int *y, int n, int *bull, int *cow)
{
   int i, flag[10] = {0};
   *bull = *cow = 0;
   for (i = 0; i < n; i++)
      if (x[i] == y[i])
         (*bull)++;
      else
         flag[x[i]] = 1;
   for (i = 0; i < n; i++)
      if (flag[y[i]])
         (*cow)++;
}
 
int main()
{
   int x[4] = {1,2,3,4}, y[4] = {1,2,3,4};
   int bull, cow;
   Count(x, y, 4, &bull, &cow);
   printf("bull = %d cow = %d\n", bull, cow);
   getchar();
   return 0;
}

Ответ выводит bull = 4, cow = 0. Зачем народ баламутить

Новые блоги и статьи Все статьи Все блоги /
Реалии Hrethgir 01.03.2026 Нет, я не закончил до сих пор симулятор. Эта задача сложнее. Не получилось уйти в плавсостав, но оно и к лучшему, возможно. Точнее получалось - но сварщиком в палубную команду, а это значит, в моём. . .	Ритм жизни kumehtar 27.02.2026 Иногда приходится жить в ритме, где дел становится всё больше, а вовлечения в происходящее — всё меньше. Плотный график не даёт вниманию закрепиться ни на одном событии. Утро начинается с быстрых,. . .	SDL3 для Web (WebAssembly): Сборка библиотек: SDL3, Box2D, FreeType, SDL3_ttf, SDL3_mixer и SDL3_image из исходников с помощью CMake и Emscripten 8Observer8 27.02.2026 Недавно вышла версия 3. 4. 2 библиотеки SDL3. На странице официальной релиза доступны исходники, готовые DLL (для x86, x64, arm64), а также библиотеки для разработки под Android, MinGW и Visual Studio. . . .	SDL3 для Web (WebAssembly): Реализация движения на Box2D v3 - трение и коллизии с повёрнутыми стенами 8Observer8 20.02.2026 Содержание блога Box2D позволяет легко создать главного героя, который не проходит сквозь стены и перемещается с заданным трением о препятствия, которые можно располагать под углом, как верхнее. . .
Конвертировать закладки radiotray-ng в m3u-плейлист damix 19.02.2026 Это можно сделать скриптом для PowerShell. Использование . \СonvertRadiotrayToM3U. ps1 <path_to_bookmarks. json> Рядом с файлом bookmarks. json появится файл bookmarks. m3u с результатом. # Check if. . .	Семь CDC на одном интерфейсе: 5 U[S]ARTов, 1 CAN и 1 SSI Eddy_Em 18.02.2026 Постепенно допиливаю свою "многоинтерфейсную плату". Выглядит вот так: https:/ / www. cyberforum. ru/ blog_attachment. php?attachmentid=11617&stc=1&d=1771445347 Основана на STM32F303RBT6. На борту пять. . .	Камера Toupcam IUA500KMA Eddy_Em 12.02.2026 Т. к. у всяких "хикроботов" слишком уж мелкий пиксель, для подсмотра в ESPriF они вообще плохо годятся: уже 14 величину можно рассмотреть еле-еле лишь на экспозициях под 3 секунды (а то и больше),. . .	И ясному Солнцу zbw 12.02.2026 И ясному Солнцу, и светлой Луне. В мире покоя нет и люди не могут жить в тишине. А жить им немного лет.