10132 - File Fragmentation

[tottinbot]

i got WA but cant find whats wrong

Code: Select all

removed

[tottinbot]

already found - it was because of excessive gets() before while

[helloneo]

already found - it was because of excessive gets() before while

You should remove your code if you got AC..

[clivant]

Anyone can advise on the exact format of the output?

[hpjhc]

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <limits.h>
#include <math.h>

int cmp(const void *, const void *);
void compare(int, int, int);
char str[144][260];
char s[600], t[600];
int main(void)
{
int n, i, k, len, ok;
scanf("%d", &n);
getchar();
for(i = 0; i < n; i++)
{
k = 0;
gets(s);
while(gets(str[k++]), str[k-1][0] != 0);
len = k-1;
qsort(str, len, sizeof(str[0]), cmp);
ok = 0;
if(len == 2)
printf("%s\n", strcat(str[0], str[1]));
else if(strlen(str[0]) == strlen(str[1]))
compare(0, 1, len);
else if(len >= 6)
{
if(strlen(str[1]) == strlen(str[2]))
compare(1, 2, len);
else
compare(0, 1, len);
}
else
compare(0, 1, len);
if(i < n-1)
printf("\n");
}
return 0;
}

int cmp(const void *a, const void *b)
{
int len1, len2;
len1 = strlen((char *)a);
len2 = strlen((char *)b);
return len1-len2;
}

void compare(int i, int j, int len)
{
strcpy(s, str);
strcpy(t, str[j]);
strcat(s, str[len-1-i]);
strcat(t, str[len-1-j]);
if(strcmp(s, t) == 0)
{
printf("%s\n", s);
return;
}
strcpy(s, str);
strcpy(t, str[j]);
strcat(s, str[len-1-j]);
strcat(t, str[len-1-i]);
if(strcmp(s, t) == 0)
{
printf("%s\n", s);
return;
}
strcpy(s, str[len-1-i]);
strcpy(t, str[len-1-j]);
strcat(s, str);
strcat(t, str[j]);
if(strcmp(s, t) == 0)
{
printf("%s\n", s);
return;
}
strcpy(s, str[len-1-i]);
strcpy(t, str[len-1-j]);
strcat(s, str[j]);
strcat(t, str);
if(strcmp(s, t) == 0)
{
printf("%s\n", s);
return;
}
strcpy(s, str);
strcpy(t, str[len-1-i]);
strcat(s, str[len-1-j]);
strcat(t, str[j]);
if(strcmp(s, t) == 0)
{
printf("%s\n", s);
return;
}
strcpy(s, str);
strcpy(t, str[len-1-j]);
strcat(s, str[len-1-i]);
strcat(t, str[j]);
if(strcmp(s, t) == 0)
{
printf("%s\n", s);
return;
}
strcpy(s, str[len-1-i]);
strcpy(t, str[j]);
strcat(s, str);
strcat(t, str[len-1-j]);
if(strcmp(s, t) == 0)
{
printf("%s\n", s);
return;
}
strcpy(s, str[len-1-j]);
strcpy(t, str[j]);
strcat(s, str);
strcat(t, str[len-1-i]);
if(strcmp(s, t) == 0)
{
printf("%s\n", s);
return;
}
}

[brianfry713]

Input:

Code: Select all

2

011
0111
01110
111
0111
10111

011
0111
01110
111
0111
10111

output should be:

Code: Select all

01110111

01110111

[Alew]

here is my algorithm (sorry for my english):
1) compute the length of the original string and the number of ones and zeroes in it
2)make a table of the fragments(with width of the original string). Align each fragment to the left and to the right:
110***
***110
11****
****11
3)count the number of ones and zeroes in each column. If ones > zeroes then in the string there is 1 in this position;
the same for zeroes;
if ones == zeroes then it can be any of it(according to the counted number of 1 and 0 in the original string)

[Zyaad Jaunnoo]

I used a brute force approach to find the correct fragment combination. Complexity = O(n^2).

Here is the pseudocode:
1) Use a map<string, int> to store the combined fragments and a count of how many fragments of that kind can be made.
2) Concatenate fragment with fragment[j], where 0 <= i, j <= number of fragments and i <> j.
3) Increment the count of map<string, int>

Solution:
The fragment we are looking for is the one having the greatest count.

Hope it helps

[TryCatchMe]

I solved this problem with backtracking in 0.015. A hint to those who are lost: for each test case compute the length of the solution string by summing all the input string lengths and dividing by (number of lines / 2) and exploit this in your pruning.

[Mukit Chowdhury]

Accepted