1027 - Toll

All about problems in Volume 10. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Post Reply
brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

1027 - Toll

Post by brianfry713 » Thu Aug 28, 2014 12:22 am

Use this thread to discuss this problem.
Check input and AC output for thousands of problems on uDebug!

metaphysis
Experienced poster
Posts: 130
Joined: Wed May 18, 2011 3:04 pm

Re: 1027 - Toll

Post by metaphysis » Sat Feb 10, 2018 6:07 pm

Test data generator.

Code: Select all

#include <iostream>
#include <cstdlib>
#include <ctime>
#include <cstring>

using namespace std;

int visited[52], edges[52][52];

void dfs(int u)
{
    visited[u] = 1;
    for (int v = 0; v < 52; v++)
        if (edges[u][v] && !visited[v])
            dfs(v);
}

char getChar(int x)
{
    if (x <= 25) return (char)('a' + x);
    else return (char)('A' + x - 26);
}

int main(int argc, char *argv[])
{
    srand(time(NULL));

    int n = 0;
    while (true)
    {
        int u = rand() % 52, v = rand() % 52;
        if (u == v) continue;
        if (edges[u][v]) continue;
        edges[u][v] = 1;
        if (++n == 20) break;
    }

    for (int i = 0; i < 52; i++)
        for (int j = 0; j < 52; j++)
            if (edges[i][j])
            {
                memset(visited, 0, sizeof(visited));
                dfs(i);
                for (int k = 0; k < 52; k++)
                    if (visited[k] && k != i && k != j)
                    {
                        cout << n << '\n';
                        for (int x = 0; x < 52; x++)
                            for (int y = 0; y < 52; y++)
                                if (edges[x][y])
                                    cout << getChar(x) << ' ' << getChar(y) << '\n';
                        cout << (rand() % 1000 + 1) << ' ' << getChar(i) << ' ' << getChar(k) << '\n';
                    }
            }
    cout << "-1\n";

    return 0;
}

Post Reply

Return to “Volume 10 (1000-1099)”