Algorithm
Problem link- https://www.spoj.com/problems/DOTAA/
DOTAA - DOTA HEROES
Defence Of The Ancients (DOTA) is one of the most addictive online multiplayer games. There are n heroes in our team and our motto is to conquer the opponent’s empire. To safeguard their empire, the opponents had constructed m towers on the path. If one or more heroes get into the sight of a tower, then the tower does D amount of damage to one of those heroes at that instant (i.e. one of the heroes’ health decreases by D). Any hero will die if his health H <= 0. Once a tower attacks one of the heroes, all the heroes in the sight of that tower at that instant get out of its sight. Find whether all of the heroes in our team can reach the opponent’s empire alive.
Input
The first line consists of one integer t representing the number of test cases. For each test case, the first line consists of three integers n, m and D, the number of heroes, number of towers and the amount of Damage respectively. The next n lines consist of an integer representing the health of respective hero.
Output
Just a word “YES” if we can reach the opponent’s empire alive, else “NO”.
Constraints
1 <= t <= 500
1 <= n <= 500
1 <= m <= n
1 <= D, H <= 20000
Example
Input: 3 6 3 400 500 500 500 500 500 500 6 5 400 800 800 801 200 200 200 6 3 400 401 401 400 200 400 200 Output: YES NO NO
Explanation of test case 1:
One of the possible solutions is: First, three of the heroes can goes together. One of them receives 400 damage from the first tower and all of them cross it. Then while crossing the next tower, one of the heroes who is at 500 health gets 400 damage and all of them cross it. Then the third hero receives the damage when crossing the last tower. Similarly the other 3 heroes can reach the opponent’s base together without dying.
Code Examples
#1 Code Example with C++ Programming
Code -
C++ Programming
#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <sstream>
#include <map>
using namespace std;
int main(){
int t,n,m,d;
scanf("%d",&t);
while(t--){
scanf("%d%d%d",&n,&m,&d);
int health[n];
int temp=0;
while(n--){
scanf("%d",&health[n]);
temp+=(health[n]-1)/d;
}
if(temp>=m)
printf("YES\n");
else
printf("NO\n");
}
return 0;
}Input
6 3 400
500
500
500
500
500
500
6 5 400
800
800
801
200
200
200
6 3 400
401
401
400
200
400
200
Output
NO
NO
#2 Code Example with Java Programming
Code -
Java Programming
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;
public class DOTAA {
public static void main(String[] arguments) throws Exception
{
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
PrintWriter out = new PrintWriter(System.out);
int numTestCases = Integer.parseInt(reader.readLine());
for(int i = 0; i < numTestCases; i++)
{
String[] data = reader.readLine().split(" ");
int numHeroes = Integer.parseInt(data[0]);
int numTowers = Integer.parseInt(data[1]);
int tDamage = Integer.parseInt(data[2]);
boolean reach = false;
for(int j = 0; j < numHeroes; j++)
{
int heroPower = Integer.parseInt(reader.readLine());
if(heroPower > tDamage)
{
double sustain = (double)heroPower/(double)tDamage;
if(isWhole(sustain))
{
sustain = sustain - 1;
}
else
{
sustain = Math.floor(sustain);
}
numTowers = (int) (numTowers - sustain);
}
if(numTowers <= 0)
{
reach = true;
}
}
if(reach)
{
out.println("YES");
}
else
{
out.println("NO");
}
out.flush();
}
}
private static boolean isWhole(double value) {
return Math.floor(value) == value;
}
}Input
6 3 400
500
500
500
500
500
500
6 5 400
800
800
801
200
200
200
6 3 400
401
401
400
200
400
200
Output
NO
NO
#3 Code Example with C Programming
Code -
C Programming
#include <stdio.h>
int main()
{
int T,n,i,m,d,h[500],cnt=0;
scanf("%d",&T);
while(T--)
{
scanf("%d %d %d",&n,&m,&d);
cnt=0;
for(i=0;i<n;i++)
{
scanf("%d",&h[i]);
while((h[i]-=d)>0) {
cnt++;
}
}
if(cnt>=m) printf("YES\n");
else printf("NO\n");
}
return 0;
}Input
6 3 400
500
500
500
500
500
500
6 5 400
800
800
801
200
200
200
6 3 400
401
401
400
200
400
200
Output
NO
NO
Demonstration
SPOJ Solution-DOTAA DOTA HEROES-Solution in C, C++, Java, Python