416 - LED Test

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

Moderator: Board moderators

Ivor
Experienced poster
Posts: 150
Joined: Wed Dec 26, 2001 2:00 am
Location: Tallinn, Estonia

416 - LED Test

Post by Ivor » Thu Aug 01, 2002 6:55 pm

Are there any tricky inputs or possible pitfalls?
I'm starting to become hopeless. :-?
I've solved it, resolved, revised, found some bugs but still can't get it accepted.

Any help is appreciated,
Ivor
There is a theory which states that if ever anyone discovers exactly what the Universe is for and why it is here, it will instantly disappear and be replaced by something even more bizarre and inexplicable.

sumrnot
New poster
Posts: 1
Joined: Fri Aug 09, 2002 8:37 am

Post by sumrnot » Fri Aug 09, 2002 8:47 am

Hmm... my first mistake was counting up, second was wrapping
No third :)
--
Geoff

Ivor
Experienced poster
Posts: 150
Joined: Wed Dec 26, 2001 2:00 am
Location: Tallinn, Estonia

Post by Ivor » Fri Aug 09, 2002 10:31 am

Thanks, I have already solved it. I just didn't mark the burned segments -- a problem with understanding.

Ivor
There is a theory which states that if ever anyone discovers exactly what the Universe is for and why it is here, it will instantly disappear and be replaced by something even more bizarre and inexplicable.

chuck
New poster
Posts: 1
Joined: Sun Feb 09, 2003 8:38 am

Post by chuck » Sun Feb 09, 2003 8:40 am

Is the "count down" sequence abled to be wrapping?
Like "1 0 9 8"

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:

Post by Dominik Michniewski » Mon Feb 10, 2003 9:35 am

I think no ....
But yoy must check this situation:
when you test i.e. 8 some segment was bad
and when you test 7 the same segment is good ... that's incorrect :)

Regards
Dominik

User avatar
Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria

Post by Sedefcho » Wed May 18, 2005 1:14 pm

Hi all,

I don't understand this problem. What do they actually
want us to check ? As this is the only thread dedicated to
problem 416, I am posting my question here.

Can someone explain with some plain words
the problem / not the solution :) just the problem /

One more thing. Currently I have a program which just
reads the input lines ( the 7-letter strings of Y/N symbols )
and then prints the numbers which they represent.
If some string represents no valid number I print "null".
The output for different datasets are separated by a line
containing the string "=================".

Using the sample input from the Problem Description I get
the following output.

Code: Select all

=================
9
=================
null null
=================
8 8
=================
6 5 4
=================
null null null
=================
null null null
=================
8 1 null null
=================
null null null
So ... Can someone explain or give some hint at least ?

Raiyan Kamal
Experienced poster
Posts: 106
Joined: Thu Jan 29, 2004 12:07 pm
Location: Bangladesh
Contact:

Post by Raiyan Kamal » Tue Jun 07, 2005 1:38 pm

I hope Sedefcho has already solved the problem.

As Sedefcho said, since "this is the only thread dedicated to problem 416", i am posting some explanation for the future sufferers.

The status of the 7 LEDs is given for some count down sequence and we have to determine if this is a valid countdown sequence or not. The confusing part is the 'burnig out' of LEDs. Say the first number of the sequece is 8, then the proper status of the LEDs should be YYYYYYY. However, if the last two LEDs are bunred out then we shall see YYYYYNN. So this is also valid if we consider the last two LEDs already damaged. The next number 7, should have been seen like this : YYYNNNN and this is what we are going to see even if the last two LEDs are damaged. The next number 6 should have been : YNYYYYY and this is what we see since the last two LEDs are damaged : YNYYYNN. Next number is 5 and should have been : YNYYNYY but since the last two LEDs are damaged, we shall see YNYYNNN. And so on upto 0. Now, according to the above discussion, if the input is :
YYYYYNN
YYYNNNN
YNYYYNN
YNYYNNN

then the output should be "MATHCH" since it represents a valid sequence starting at 8 and ending at 5 with two LEDs being damaged from the beginning.

LEDs could have been damaged in the middle of the sequence too. So you have to keep that in mind. Finally, no damaged LED will become well again, so once you assume a certain LED to be damaged and it gets Y somewhere in the sequence then a contradiction arises. Keep that in mind too.
Last edited by Raiyan Kamal on Thu Jul 28, 2005 5:08 am, edited 2 times in total.

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Wed Jul 27, 2005 2:28 am

Raiyan, My accepted code returns MISMATCH for the input

YYYYYNN
YYYNNNN
YYYYYNN
YNYYNNN

There is no wrapping around I think. :)
Ami ekhono shopno dekhi...
HomePage

Raiyan Kamal
Experienced poster
Posts: 106
Joined: Thu Jan 29, 2004 12:07 pm
Location: Bangladesh
Contact:

Post by Raiyan Kamal » Thu Jul 28, 2005 4:58 am

:oops:
My mistake!

I apologize. I have corrected the sample input in my previous post. Thanks to Jan for pointin out the error. I had to write 6 on the third line of input, but by mistake wrote something that looks like 1 in bangla !

Here are some more test cases.

INPUT :

Code: Select all

4
YYYYYNN
YYYNNNN
YNYYYNN
YNYYNNN
5
YYYYYYY
NNNNNNN
NNNNNNN
NNNNNNN
NNNNNNN
1
YYYYYYY
1
NNNNNNN
4
YYYYYNN
YYYNNNN
YYYYYNN
YNYYNNN
2
YYYYYYY
NNNNYYY
2
YYYNNNN
YYYNNNN
2
YNNYNNY
YNNYNNY
10
NNYNNNN
NNYNNNN
NNYNNNN
NNYNNNN
NNYNNNN
NNYNNNN
NNYNNNN
NNYNNNN
NNYNNNN
NNYNNNN
10
NNYNNNN
NNYNNNN
NNYNNNN
NNYNNNN
NNYNNNN
NNYNNNN
NNYNNNN
NNNNNNN
NNYNNNN
NNYNNNN
OUTPUT :

Code: Select all

MATCH
MATCH
MATCH
MATCH
MISMATCH
MISMATCH
MATCH
MATCH
MISMATCH
MATCH

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Thu Jul 28, 2005 9:39 am

Raiyan, I think you have made the problem so clear that there is no need of any more threads. You made it perfect. Thanks...

Good Luck! :D
NDC group 2...Finally we met. :wink:
Ami ekhono shopno dekhi...
HomePage

Raiyan Kamal
Experienced poster
Posts: 106
Joined: Thu Jan 29, 2004 12:07 pm
Location: Bangladesh
Contact:

Post by Raiyan Kamal » Sat Jul 30, 2005 12:06 pm

Thats one of the specialities of being a Notre Damian. Thanks again. Hope to meet you again soon.

KimKun
New poster
Posts: 1
Joined: Wed Aug 17, 2005 4:18 am
Location: KOREA. REPUBLIC OF

Please Help T.T 416 - LED TEST

Post by KimKun » Wed Aug 17, 2005 4:23 am

#include <fstream.h>
char led[10][8] = {
"YYYYYYN",
"NYYNNNN",
"YYNYYNY",
"YYYYNNY",
"NYYNNYY",
"YNYYNYY",
"YNYYYYY",
"YYYNNNN",
"YYYYYYY",
"YYYYNYY"};
char data[100][8];
int n;
int ous[4000000];
int BT(int bun){
int error[8];
int i,flag,j,k;
for (i=bun,k=0;k<n;i--,k++){
if (i==-1) i=9;
if (k==10) k=0;
for (j=flag=0;j<7;j++){
if (led[j] != data[k][j] && data[k][j] == 'Y'){
return 1;
}else if (led[j] != data[k][j] && data[k][j] == 'N'){
error[j]=1;
}else if (error[j] == 1 && data[k][j] =='Y'){
return 1;
}
}
}
return 0;
}
int main()
{
int i,j,k;
int flag;
int qflag,eflag;
for (k=0;;k++){
eflag=0;
cin >> n;
if (n==0) break;
for (i=0;i<n;i++){
cin >> data;
}
for (i=9;i>=0;i--){
for (j=flag=0;j<7;j++){
if (led[j] != data[0][j] && data[0][j] == 'Y'){
flag=1;
break;
}
}
if (flag==0){
qflag=BT(i);
if (qflag==0){
ous[k] = 1;
eflag=1;
break;
}
}
}
}
for (i=0;i<k;i++){
if (ous==0){
cout << "MISMATCH\n";
}else{
cout << "MATCH\n";
}
}
return 0;
}



what should I do ?.T.T
Help..

kenneth_cwc
New poster
Posts: 9
Joined: Sat Oct 18, 2003 2:08 pm

416 WA pls help

Post by kenneth_cwc » Sun Aug 28, 2005 2:50 pm

Anyone can help me? I tried to debug for long time :cry:

Code: Select all

#include<iostream>
using namespace std;

void check_and_store(char str[], int pos, int possible_no[]);

void main()
{
	int possible_no[10];
	int n;
	char tmp[8];
	int i, j;
	bool match;

	cin>>n;
	cin.getline(tmp, 8);
	while(n)
	{
		if(n==1)
		{
			cin.getline(tmp, 8);
			cout<<"MATCH\n";
		}
		else
		{
			for(i=0;i<n;i++)
			{
				cin.getline(tmp, 8);
				check_and_store(tmp, i, possible_no);
			}

			i=11-n;
			while(1)
			{
				match=1;

				i--;
				while(!(possible_no[n-1] & 1<<i) && i>=0)
					i--;

				if(i==-1)
				{
					match=0;
					break;
				}

				for(j=0;j<n-1;j++)
				{
					if((possible_no[n-2-j] & 1<<(i+j+1)) != 1<<(i+j+1))
						match=0;
				}

				if(match)
					break;
			}
			if(match)
				cout<<"MATCH\n";
			else
				cout<<"MISMATCH\n";
		}
		cin>>n;
		cin.getline(tmp, 8);
	}
}

void check_and_store(char str[], int pos, int possible_no[])
{
	//check 0~9:
	possible_no[pos]=1023;

	if(str[0]=='Y')
		possible_no[pos] &= ~(1<<1) & ~(1<<4);
	if(str[1]=='Y')
		possible_no[pos] &= ~(1<<5) & ~(1<<6);
	if(str[2]=='Y')
		possible_no[pos] &= ~(1<<2);
	if(str[3]=='Y')
		possible_no[pos] &= ~(1<<1) & ~(1<<4) & ~(1<<7);
	if(str[4]=='Y')
		possible_no[pos] &= ~(1<<1) & ~(1<<3) & ~(1<<4) & ~(1<<5) & ~(1<<7) & ~(1<<9);
	if(str[5]=='Y')
		possible_no[pos] &= ~(1<<1) & ~(1<<2) & ~(1<<3) & ~(1<<7);
	if(str[6]=='Y')
		possible_no[pos] &= ~(1<<0) & ~(1<<1) & ~(1<<7);

}

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Wed Aug 31, 2005 11:07 am

Sorry for posting wrong output. :-?
Last edited by Jan on Fri Jan 12, 2007 9:21 pm, edited 1 time in total.
Ami ekhono shopno dekhi...
HomePage

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Thu Sep 15, 2005 11:50 pm

You can find some test cases in the following forum. Use it.

http://online-judge.uva.es/board/viewto ... hlight=416

Hope it helps.
Ami ekhono shopno dekhi...
HomePage

Post Reply

Return to “Volume 4 (400-499)”