10401 - Injured Queen Problem

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

Moderator: Board moderators

User avatar
Ghost77 dimen
Learning poster
Posts: 67
Joined: Sun Sep 22, 2002 5:40 am
Location: Taiwan

10401

Post by Ghost77 dimen » Sat Nov 30, 2002 5:40 pm

My code: :P
[cpp]
#include<stdio.h>

..........................

..........................

long long int ans;

..........................

..........................

..........................

printf("%lld\n",ans);[/cpp]

Sample Input
??
?
1??
??2
??????????????A
??????????????F
??????????????1
Sample Output
0
1
1
0
1498872015836269
1613590825771003
1613590825771003
Online Judge--->Wrong Anser

User avatar
Ghost77 dimen
Learning poster
Posts: 67
Joined: Sun Sep 22, 2002 5:40 am
Location: Taiwan

Post by Ghost77 dimen » Sun Dec 01, 2002 6:54 am

My problem is :

1. the declaring and output format of "long long int" is correct or not

2. the range of long long int is -2^63~2^63-1 or not

3. the sample output is correct or not


8)

marian
New poster
Posts: 30
Joined: Sun Oct 27, 2002 4:01 pm
Contact:

Post by marian » Wed Dec 04, 2002 3:57 pm

1. yes
2. yes
3. yes

:wink:

lrem
New poster
Posts: 2
Joined: Sat Jan 04, 2003 3:08 pm
Location: Poland 3-city

Post by lrem » Mon Jan 06, 2003 9:46 pm

I read somewhere on this site that output format %lld is not really flawless
If I want culture I eat yogurt

dary
New poster
Posts: 2
Joined: Fri Jan 31, 2003 7:32 pm
Contact:

Post by dary » Fri Jan 31, 2003 7:34 pm

I had similar problems but when I changed from reading lines to read words, everything sorted out. Probably some trailing empty lines or another anomaly.

User avatar
Ghost77 dimen
Learning poster
Posts: 67
Joined: Sun Sep 22, 2002 5:40 am
Location: Taiwan

Post by Ghost77 dimen » Sun Feb 02, 2003 4:55 pm

I got it, thanks.

Andrey Grigorov
New poster
Posts: 8
Joined: Thu Jul 15, 2004 3:52 pm
Location: Russia, Cherepovets

10401 - Injured Queen Problem

Post by Andrey Grigorov » Thu Jul 15, 2004 6:01 pm

Hi! Please, help me. Is my input/output correct?

Input:
??????
???????????????
???8?????
43?????
?
??
???
????
?????
1????
2????
3????
4????
5????
??????????
??1?5?7A??
?1?2?3?4?5
135797531?
?4?3?F??A???6??

My output:
2642
22696209911206174
2098208
0
1
0
2
16
184
44
30
36
30
44
531713286
81225
12096
8
34657223040

jamu
New poster
Posts: 13
Joined: Wed Dec 03, 2003 11:15 am

Post by jamu » Fri Jul 16, 2004 1:37 am

My AC program's output is the same...

Zhou Yiyan@SHU
New poster
Posts: 12
Joined: Tue Jul 30, 2002 9:24 am
Location: SHU, Shanghai, China

Post by Zhou Yiyan@SHU » Wed Jul 21, 2004 12:59 pm

I can't make out a quick method to get the answer. Normal backtrack algorithm just got TLE all the time. Is there some restrict condition to make the search faster?

sidky
New poster
Posts: 50
Joined: Wed Nov 06, 2002 1:37 pm
Location: Planet Earth, Universe
Contact:

Post by sidky » Wed Jul 21, 2004 5:37 pm

Use memoization

Zhou Yiyan@SHU
New poster
Posts: 12
Joined: Tue Jul 30, 2002 9:24 am
Location: SHU, Shanghai, China

Post by Zhou Yiyan@SHU » Thu Jul 22, 2004 4:06 am

Thank you, sidky! I have make out the table and solve the problem. It seems that table memorization would be more preferable when solving counting problem rather than using traditional backtrack algorithm. :D

alexkro
New poster
Posts: 9
Joined: Sun Jan 12, 2003 12:18 pm

10401

Post by alexkro » Mon Sep 27, 2004 11:34 am

Could you help me with this problem? I receive SIGABRT. Obviously one of the asserts fires. If I remove all asserts I get SIGSEGV which is what I expect. But I can't see how any input can lead to SIGABRT. I tried different input parameters but I couldn't find any that can crash this program.

[cpp]
// valladolid problem #10401
// http://online-judge.uva.es/p/v104/10401.html

#include <iostream>
#include <vector>
#include <memory>
#include <functional>
#include <algorithm>
#include <string>
#include <exception>
#include <cassert>

using namespace std;


enum field_val
{
field_occupied = -1
, field_init = 1
};


class board
{
public:
board( int size )
: m_size( size )
, m_queens( size )
, m_board( size )
, m_good( true )
{
for ( int i = 0; i < m_size; ++i )
m_board[ i ].resize( m_size );
}

bool good() const
{
return m_good;
}

void set_queen( int file, int rank )
{
if ( ! good() )
return;

if ( m_board[ file ][ rank ] == field_occupied )
{
m_good = false;
return;
}

if ( rank >= m_size )
{
m_good = false;
return;
}

assert( file >= 0 && file < m_size );
assert( rank >= 0 );

m_queens[ file ] = true;
fill( file );
fill( file - 1, rank - 1, rank + 2 );
fill( file + 1, rank - 1, rank + 2 );
}

void set_initial_vals()
{
int file = find_unoccupied( m_size - 1 );
if ( file < 0 )
return;

for ( int rank = 0; rank < m_size; ++rank )
{
if ( m_board[ file ][ rank ] != field_occupied )
m_board[ file ][ rank ] = field_init;
}
}

long long compute_positions()
{
if ( ! good() )
return 0;

int file = find_unoccupied( m_size - 2 );
if ( file < 0 )
return 1; // if all files are occupied than
// there is only one valid position

int last_processed_file = -1;
for ( ; file >= 0; --file )
{
if ( ! m_queens[ file ] )
process_file( last_processed_file = file );
}

assert( last_processed_file != -1 );

long long positions = 0;
for ( int rank = 0; rank < m_size; ++rank )
{
if ( m_board[ last_processed_file ][ rank ] != field_occupied )
positions += m_board[ last_processed_file ][ rank ];
}

return positions;
}

private:
int find_unoccupied( int start_file )
{
int file = start_file;
while ( file >= 0 && m_queens[ file ] )
--file;
return file;
}

void process_file( int file )
{
assert( file < m_size - 1 );
assert( ! m_queens[ file ] );

#ifdef TRACE
cout << file << endl;
#endif

for ( int rank = 0; rank < m_size; ++rank )
{
if ( m_board[ file ][ rank ] == field_occupied )
continue;

int next_file = file + 1;
while ( m_queens[ next_file ] )
{
++next_file;
assert( next_file < m_size );
}

long long field_val = 0;
for ( int next_rank = 0; next_rank < m_size; ++next_rank )
{
if ( ( next_file > file + 1 || next_rank < rank - 1 || next_rank > rank + 1 )
&& m_board[ next_file ][ next_rank ] != field_occupied )
{
field_val += m_board[ next_file ][ next_rank ];
}
}

m_board[ file ][ rank ] = field_val;

#ifdef TRACE
cout << file << ':' << rank << "->" << field_val << ' '; #endif
}

#ifdef TRACE
cout << endl;
#endif
}

void fill( int file, int start_rank = 0 )
{
fill_with( field_occupied, file, start_rank );
}

void fill( int file, int start_rank, int end_rank )
{
fill_with( field_occupied, file, start_rank, end_rank );
}

void fill_with( long long val, int file, int start_rank = 0 )
{
if ( start_rank < 0 )
start_rank = 0;
fill_with( val, file, start_rank, m_size );
}

void fill_with( long long val, int file, int start_rank, int end_rank )
{
if ( file < 0 ) return;
if ( file >= m_size ) return;

if ( start_rank < 0 )
start_rank = 0;
if ( end_rank > m_size )
end_rank = m_size;

for ( int i = start_rank; i < end_rank; ++i )
m_board[ file ][ i ] = val;
}

private:
board( board const & ); // undefined
board & operator=( board const & ); // undefined

private:
int m_size;
vector< bool > m_queens;
vector< vector< long long > > m_board;
bool m_good;
};


struct initializer : unary_function< void, char > {
initializer( board & brd )
: m_board( brd )
, m_cur_file( 0 )
{}

void operator()( char ch )
{
if ( isdigit( ch ) )
m_board.set_queen( m_cur_file, ch - '1' );
else if ( ch >= 'A' && ch <= 'F' )
m_board.set_queen( m_cur_file, ch - 'A' + 10 );
else if ( ch >= 'a' && ch <= 'f' )
m_board.set_queen( m_cur_file, ch - 'a' + 10 );

++m_cur_file;
}

private:
board & m_board;
int m_cur_file;
};


auto_ptr< board > read_input()
{
string input;

while ( input.empty() )
cin >> input;

board * brd = new board( input.size() );
for_each( input.begin(), input.end(), initializer( *brd ) );

return auto_ptr< board >( brd );
}


int main()
{
cin.exceptions( ios::eofbit | ios::badbit | ios::failbit );
cout.exceptions( ios::eofbit | ios::badbit | ios::failbit );

try
{
for (;;)
{
auto_ptr< board > brd( read_input() );
brd->set_initial_vals();
cout << brd->compute_positions() << endl;
}
}
catch ( exception & e )
{
if ( ! cin.eof() )
{
cerr << "error: " << e.what() << endl;
return 1;
}
}
}
[/cpp]

alexkro
New poster
Posts: 9
Joined: Sun Jan 12, 2003 12:18 pm

Re: 10401

Post by alexkro » Mon Sep 27, 2004 10:29 pm

Never mind. I found it.

hoang
New poster
Posts: 4
Joined: Sat Jan 14, 2006 6:02 pm

Some body help me ?

Post by hoang » Mon Jan 23, 2006 6:07 pm

Can anyone give me some hints for this problem ?
i cant solve it for a month ? :cry:

helloneo
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea

Re: Some body help me ?

Post by helloneo » Tue Jan 24, 2006 5:00 am

hoang wrote:Can anyone give me some hints for this problem ?
i cant solve it for a month ? :cry:
make a table..
let's say dp[j] means the # of ways to put a queen on the position (i, j)
then you will see how to get dp[i+1][j] ..

Post Reply

Return to “Volume 104 (10400-10499)”