11292 - Dragon of Loowater
Moderator: Board moderators
11292 - Dragon of Loowater
hi. Has anyone(with an ac code) got any I/O they could post here so people can check to see if they are getting things right? (people = me)cheers. Scott
-
- New poster
- Posts: 37
- Joined: Wed Oct 03, 2007 10:42 am
Re: 11292 - Dragon of Loowater
Take this input and I think this will be helpful for u.
knight or dragon's diameter will be long so use data type long.
Input:
2 4
7
2
4
3
1
2
2 4
7
2
2
1
8
5
1 1
2
2
1 1
1
2
3 5
5
6
1
2
3
4
5
1
1 1
2
1
2 10
1234567
2345
12345610
1
123
23564
123456
123
2
3
2
1
0 0
output:
Loowater is doomed!
10
2
2
Loowater is doomed!
Loowater is doomed!
12369174
knight or dragon's diameter will be long so use data type long.
Input:
2 4
7
2
4
3
1
2
2 4
7
2
2
1
8
5
1 1
2
2
1 1
1
2
3 5
5
6
1
2
3
4
5
1
1 1
2
1
2 10
1234567
2345
12345610
1
123
23564
123456
123
2
3
2
1
0 0
output:
Loowater is doomed!
10
2
2
Loowater is doomed!
Loowater is doomed!
12369174
11292 - Dragon of Loowater TLE plz,help
#include<stdio.h>
long head[20009],knight[20009];
long sort(long a[],long n)
{
long i,j,k,b=0;
for(i=0;i<n-1;i++)
for(j=0;j<n-i-1;j++)
if(a[j]>a[j+1])
{
b++;
k=a[j];
a[j]=a[j+1];
a[j+1]=k;
}
}
int main()
{
long m,n,x,y,k,a,b,sum,cnt;
while(scanf("%ld %ld",&m,&n)==2)
{
if(m==0 && n==0)
break;
for(x=0;x<m;x++)
scanf("%ld",&head[x]);
for(y=0;y<n;y++)
scanf("%ld",&knight[y]);
sort(head,m);
sort(knight,n);
sum=0;
cnt=0;
for(a=0;a<m;a++)
{
for(b=0;b<n;b++)
{
if(head[a]<=knight)
{ cnt++;
sum=sum+knight;
b=n;
}
}
}
if(m>n || cnt<m)
{
printf("Loowater is doomed!\n");
}
else
printf("%ld\n",sum);
}return 0;
}
long head[20009],knight[20009];
long sort(long a[],long n)
{
long i,j,k,b=0;
for(i=0;i<n-1;i++)
for(j=0;j<n-i-1;j++)
if(a[j]>a[j+1])
{
b++;
k=a[j];
a[j]=a[j+1];
a[j+1]=k;
}
}
int main()
{
long m,n,x,y,k,a,b,sum,cnt;
while(scanf("%ld %ld",&m,&n)==2)
{
if(m==0 && n==0)
break;
for(x=0;x<m;x++)
scanf("%ld",&head[x]);
for(y=0;y<n;y++)
scanf("%ld",&knight[y]);
sort(head,m);
sort(knight,n);
sum=0;
cnt=0;
for(a=0;a<m;a++)
{
for(b=0;b<n;b++)
{
if(head[a]<=knight)
{ cnt++;
sum=sum+knight;
b=n;
}
}
}
if(m>n || cnt<m)
{
printf("Loowater is doomed!\n");
}
else
printf("%ld\n",sum);
}return 0;
}
-
- Experienced poster
- Posts: 147
- Joined: Mon Jun 07, 2010 11:43 am
- Location: University Of Dhaka,Bangladesh
- Contact:
Re: 11292 - Dragon of Loowater
Nice easy problem. Here's my algo:
1. sort the dragons and knights(ascending). stored the knight is stl list and dragons in simple array.
2. for each dragon ran a linear search through knights until a knight whose height is equal or greater than diameter of current knight is found.
3. remove the knight using built in erase function and added the height with sum
4. if suitable knight cant be found answer is doomed.
my code took .256 sec. you can use binary search for bettter performance.
1. sort the dragons and knights(ascending). stored the knight is stl list and dragons in simple array.
2. for each dragon ran a linear search through knights until a knight whose height is equal or greater than diameter of current knight is found.
3. remove the knight using built in erase function and added the height with sum
4. if suitable knight cant be found answer is doomed.
my code took .256 sec. you can use binary search for bettter performance.
UVa stats: http://felix-halim.net/uva/hunting.php?id=63448
My blog on programming: http://www.shafaetsplanet.com/planetcoding/
My blog on programming: http://www.shafaetsplanet.com/planetcoding/
Re: 11292 - Dragon of Loowater
Damn the input contains negative numbers...beware....I got 4 Wrong Answers because of this. Although I think this is very illogical as n = number of heads and m = number of knights so n and m can't be less than 0. Nevertheless, not all problems should seem to be logical I guess.
You tried your best and you failed miserably. The lesson is 'never try'. -Homer Simpson
Re: 11292 - Dragon of Loowater
@ scor_k I tried your solution and got TLE.
I've tried my own solution with integers, longs, checking for edge cases, but still get WA.
(It shouldn't even make a difference using longs or ints, because with most compilers int has the same size and representation as a long.)
The sample test case and the test case posted in this thread work fine .
I've tried my own solution with integers, longs, checking for edge cases, but still get WA.
(It shouldn't even make a difference using longs or ints, because with most compilers int has the same size and representation as a long.)
The sample test case and the test case posted in this thread work fine .
Code: Select all
/**
* 11292 - Dragon of Loowater
* author: Dennis Ideler
* category: greedy
*/
#include <algorithm>
#include <iostream>
using namespace std;
int main()
{
// knight height >= head diameter
// wage = height
// minimize expenses (i.e. choose shortest knights possible)
long n, m; // n = dragon heads, m = knights
while (cin >> n >> m)
{
if (n == 0 && m == 0) break;
long dd[n]; // dragon diameter
for (long i = 0; i < n; i++) // read diameter of each dragon head
cin >> dd[i];
long kh[m]; // knight height
for (long i = 0; i < m; i++) // read height of each knight
cin >> kh[i];
if (n <= 0)
{
cout << "0" << endl;
}
if (n > m || m <= 0)
{
cout << "Loowater is doomed!" << endl;
continue;
}
// find minimum number of gold coins needed for the job
sort(dd, dd + n);
sort(kh, kh + m); // sorted data makes comparison easier
long gold = 0;
long j = 0;
bool doom = false;
for (long i = 0; i < n; ++i) // for each dragon head
{
for (; j < m; ++j) // for each knight
{
if (dd[i] <= kh[j]) // knight is capable
{
gold += kh[j]; // assign knight
break; // go to next dragon head
}
if (j == m-1) // no knight capable
{
doom = true;
cout << "Loowater is doomed!" << endl;
}
}
}
if (!doom) // if all dragon heads slain
cout << gold << endl;
}
return 0;
}
-
- New poster
- Posts: 31
- Joined: Thu Nov 24, 2011 12:08 am
Re: 11292 - Dragon of Loowater
this problem can be solved easily with the complexity of only sorting. after sorting knight and dragon array, try to find the dragon that can be slain by minimum height knight.
if all dragon can not be slain with the provided knights, loowater is doomed!
if all dragon can not be slain with the provided knights, loowater is doomed!
11292 Dragon of Waterloo
This code is giving me a wrong answer verdict, can somebody help me, I'm just new at programming and learning here will help a lot. Thanks in advance.
Code: Select all
#include <stdio.h>
#include <stdlib.h>
#define max 20000
int compare(const void * a, const void * b)
{
return(*(int*)a - *(int*)b);
}
int main(){
int diameter[max];
int height[max];
int drHead = 0;
int knight = 0;
int i,j;
int sum = 0;
int killed=0;
while(scanf("%d %d", &drHead, &knight), drHead, knight){
for(i=0; i<drHead; i++)
scanf("%d", &diameter[i]);
for(i=0; i<knight; i++)
scanf("%d", &height[i]);
qsort(diameter, drHead, sizeof(int), compare);
qsort(height, knight, sizeof(int), compare);
for(i=0; i<knight; i++)
for(j=0; j<drHead; j++)
{
if (height[i] >= diameter[i])
diameter[i] = 0;
}
for(i=0; i< drHead; i++)
sum = sum + diameter[i];
if(sum == 0)
killed = 1;
else
killed = 0;
if(knight < drHead || killed == 0)
printf("Loowater is doomed!\n");
else
{
for(i=0;i<drHead;i++)
sum = sum + height[i];
printf("%d\n", sum);
}
}
return 0;
}
-
- Guru
- Posts: 5947
- Joined: Thu Sep 01, 2011 9:09 am
- Location: San Jose, CA, USA
Re: 11292 Dragon of Waterloo
Check input and AC output for thousands of problems on uDebug!
-
- New poster
- Posts: 3
- Joined: Fri Oct 02, 2015 8:15 am
Re: 11292 - Dragon of Loowater
Testcase-wise, using uDebug's Random Input, my code outputted the correct answer. But the OJ stated it as Wrong Answer. What could be wrong here?
Code: Select all
#include <iostream>
#include <algorithm>
using namespace std;
int main () {
int n, m;
long hd[20000], kh[20000];
while ( cin >> n >> m && n != 0 && m != 0 ) {
long pay = 0;
for ( int i = 0; i < n; i++ ) {
cin >> hd[i];
}
sort( hd, hd + n );
for ( int i = 0; i < m; i++ ) {
cin >> kh[i];
}
sort ( kh, kh + m );
if ( n > m ) {
cout << "Loowater is doomed!" << endl;
continue;
}
int flag = 0, headcount = n;
for ( int i = 0; i < n; i++ ) {
for ( int j = flag; j < m; j++ ) {
if ( kh[j] >= hd[i] ) {
flag = j;
pay += kh[j];
headcount--;
break;
}
}
}
if ( headcount > 0 ) {
cout << "Loowater is doomed!" << endl;
}
else {
cout << pay << endl;
}
}
return 0;
}