414 - Machined Surfaces

[iceb3rg]

============================================================================================================
SOME CRITICAL INPUT OUTPUT PLEASE
===========================================================================================================
There will be 'spaces' and 'zeros' ryt? or do they mean NULL via 'zero'
==========================================================================================================
#include <stdio.h>
#include <string.h>
#include <algorithm>

using namespace std;

char name[100][10000];
int sum[10000];

int main()
{
//freopen ("input4uva.txt","r",stdin);

int t,min,i,j,y=0;

while (scanf ("%d",&t)==1)
{

gets(name[0]);
if (t==0)
break;

int count=0;

for (j=0;j<t;j++)
{
gets(name[j]);

for (i=0;name[j]!='\0';i++)
if ((name[j]==' ') || (name[j]=='0'))
count++;

sum[j]=count;
count=0;
}
/*
for (int m=0;m<j;m++)
{
puts(name[m]);
printf ("%d ",sum[m]);
}
*/


sort(&sum[0],&sum[j]);
min=sum[0];

int result=0;

for (int k=0;k<j;k++)
{
result+=sum[k]-min;
}

printf ("%d\n",result);


}
return 0;
}

[iceb3rg]

I just submitted my beautiful code to this stupid problem by only changing int to long and got ACCPETED...my my.....what the Hell UVa????? :O :O :O ....so much pain.....useless PAIN !

[abid_iut]

I dont understand why it is showing TLE.... can anyone please help

here is my code:

Code: Select all

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

long n;
long counts[20];
char line[30];

int main(){
	long i,j,maxx,difference;
	long count;
	//freopen("414.txt","r",stdin);
	while(1){
		scanf("%ld",&n);
		if(n==0)break;
		//gets(line);
		for(i=0; i<n; i++){
			count=0;
			gets(line);
			for(j=0; j<25; j++){
				if(line[j]=='X')count++;
			}
			counts[i] = 25 - count;
		}
		maxx = 0;
		for(i=0; i<n; i++){
			if(counts[i]>=maxx)maxx = counts[i];
		}
		difference = 0;
		for(i=0; i<n; i++){
			difference = difference + (maxx - counts[i]);
		}
		printf("%ld\n",difference);
	}

	return 0;
}

[asif_iut]

//gets(line);

I think uncommenting this part should avoid TLE.....however there is still a mistake....according to the given code 'maxx' stores the maximum gap in a single string among all the given strings and for the given test case :

3
XXXXXXXXXXXX XXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXX
0

the output is 2 whereas the correct output is 1. maxx should store the minimum gap in a single string among the given strings...I think that should get AC..

[leandroprell]

Guys, im new into programming and Valladolid. I need some help understanding this 414 problem. The code is not the problem (yet..) but i just could not understand the problem. Basically is to count the number of spaces after both right and left surfaces are brought into contact, am i right?
But why for this input as shown in the problem input example
4
XXXXBBBBBBBBBBBBBBBBBXXXX
XXXBBBBBBBBBBBBBBBXXXXXXX
XXXXXBBBBBBBBBBBBBBBBXXXX
XXBBBBBBBBBBBBBBBBBXXXXXX
0

the output is 4??
Those surfaces are not even in contact? As the problem says: contact is when the rightmost X of the left surface is immediately to the left of the leftmost X of the right surface, considering each row. I mean, i am expecting a full X line to start counting the blank spaces.
So, in my understanding a perfect input to generate 4 as output is something like this:
2
XXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXBBBBXXXXXXXXXXXXX
0
Please guys, what am i misunderstanding?

Thanks for help.

[asif_iut]

you should keep on bringing the two surfaces closer as long as there is atleast 1 gap in each line.....when this can no longer be done count the remaining gaps in all the lines. Hope this helps.

[leandroprell]

you should keep on bringing the two surfaces closer as long as there is atleast 1 gap in each line.....when this can no longer be done count the remaining gaps in all the lines. Hope this helps.

Actually i still dont understand.. lol.. Sorry, it may seems like a dumb question.. but im not getting the logical behavior of this problem... im stucked on it..
When you say i should keep bringing the 2 surfaces closer, you mean i must simulate an horizontally move? But if i move the X blocks altogether by equal movement both sides the amount of blank space is still the same. And if i insert X in those blank spaces i will ended up with none or one blank space each line...
I know im not a very good programmer but i think the language here is the main problem, as my main language is not english.
So i would appreciate any help.

Thanks.

[asif_iut]

And if i insert X in those blank spaces i will ended up with none or one blank space each line...

consider the test case

XXXXXXXXXXXBXXXXXXXXXXXXX
XXXXXXXXXXBBBXXXXXXXXXXXX

if you want to insert an X then you have to do so in all the lines. In the above there is 1 gap in the first line and 3 gaps in the second line.. So, you can insert 1 X. After inserting 1 X in each line the result becomes...
XXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXBBXXXXXXXXXXXXX

Now, there is 0 gaps in line 1 and 2 gaps in line 2. the sum is 2.

Hope it helps now..

[leandroprell]

And if i insert X in those blank spaces i will ended up with none or one blank space each line...

consider the test case

XXXXXXXXXXXBXXXXXXXXXXXXX
XXXXXXXXXXBBBXXXXXXXXXXXX

if you want to insert an X then you have to do so in all the lines. In the above there is 1 gap in the first line and 3 gaps in the second line.. So, you can insert 1 X. After inserting 1 X in each line the result becomes...
XXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXBBXXXXXXXXXXXXX

Now, there is 0 gaps in line 1 and 2 gaps in line 2. the sum is 2.

Hope it helps now..

OK! now i got it. THe idea is to insert anx X in all the lines. Thanks man! I will work on the code now!
Really thanks!

[leandroprell]

And if i insert X in those blank spaces i will ended up with none or one blank space each line...

consider the test case

XXXXXXXXXXXBXXXXXXXXXXXXX
XXXXXXXXXXBBBXXXXXXXXXXXX

if you want to insert an X then you have to do so in all the lines. In the above there is 1 gap in the first line and 3 gaps in the second line.. So, you can insert 1 X. After inserting 1 X in each line the result becomes...
XXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXBBXXXXXXXXXXXXX

Now, there is 0 gaps in line 1 and 2 gaps in line 2. the sum is 2.

Hope it helps now..

THANKS for the help man! Got AC!

[No.47WK]

Code: Select all

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
int main()
{
    long int n,te,b[16],i,sum,min;
    char c[26],*tem,*temp;
    while(cin>>n)
    {
        min=25;
        i=0;
        sum=0;
        while(i<=n)
        {
            te=0;
            gets(c);            //(??gets????????n??????? 
            tem=strchr(c,' ');
            if(tem)
            {
                temp=strchr(tem,'X');
                *tem=0;
                te=25-strlen(c)-strlen(temp);
            }
            else
                te=0;
            if(min>te&&i!=0)
               min=te;
            b[i]=te;
            ++i;
        }
        for(i=1;i<=n;++i)
            sum+=(b[i]-min);
        cout<<sum<<endl;
    }
    return 0;
}
            
               
        

give me some I/O to help me get though this boring problem please.
I don't know which part of my code is wrong

[vpanait]

For some strange reason the input tests contain lines that are different from "XX..X X...X"
In order to count the spaces, just iterate all the line and count them, do not rely on the X character at all.

[uDebug]

Here are some test cases for #414

Input:

Code: Select all

4                         
XXXX                XXXXX               
XXX               XXXXXXX        
XXXXX                XXXX       
XX                 XXXXXX      
2      
XXXXXXXXXXXXXXXXXXXXXXXXX     
XXXXXXXXXXXXXXXXXXXXXXXXX     
1     
XXXXXXXXX              XX
5
XXXX                XXXXX               
XXX               XXXXXXX        
XXXXX                XXXX       
XX                 XXXXXX
X XXXXXXXXXXXXXXXXXXXXXXX 
5
XXXX                XXXXX               
XXX               XXXXXXX        
XXXXX                XXXX       
XX                 XXXXXX
XXXXXXXXXXXXXXXXXXX   XXX 
2
X                       X
X                       X
1
X                       X
2
X                      XX  
X                       X 
0   

AC Output:

Code: Select all

4
0
0
60
52
0
0
1

Also, at the time of posting this, UVA Toolkit

http://uvatoolkit.com/problemssolve.php

does not output the correct result for this problem.

[LuisLoo22]

Hi, well it is my first post here, in this problem "414 - Machined Surfaces" I don't know why I got Wrong Answer I tried to change "int" for "unsigned long long" in case of a big N. I tried the examples and it worked right, but don't know why It's wrong Can anyone help me, please?

My idea was to count all the blank spaces in a line an then add all the blank spaces and take off the minimum amoun of (blank spaces*N), someone like this example:

Code: Select all

4                        Blanks 
XXXX                XXXXX  16
XXX               XXXXXXX  15
XXXXX                XXXX  16
XX                 XXXXXX  17
                      SUM  64 
MIN BLANKS: 15
ANSWER: SUM - (MIN BLANKS*N) = 64 - 15*4 = 4

Code: Select all

#include <stdio.h>

unsigned long long calc_blankSpaces(char*s){
    unsigned long long i, countBlank;
    countBlank = 0;
    for (i=0;i<25;i++){
        if(s[i] == ' ')
            countBlank += 1;
    }
    if (countBlank>0)
        return countBlank;
    else
        return 0;
}

int main(){
    unsigned long long n,i,j,sumBlanks, menor, count;
    while(scanf("%lld", &n) && (n!=0)){
        unsigned long long blanks[n];
        fflush(stdin);
        for(i=0;i<n;i++){
            char s[26];
            gets(s);
            if (n==1)
                count = 0;
            else{
                blanks[i] = calc_blankSpaces(s);
            }
        }
        sumBlanks = 0;
        menor = blanks[0];
        for(j=0;j<n;j++){
            sumBlanks += blanks[j];
            if (menor >= blanks[j])
                menor = blanks[j];
        }
        count = sumBlanks - (menor*n);
        printf("%lld\n", count);
    }
    return 0;
}

[brianfry713]

Don't use fflush(stdin);