Sword Art Online:
SNU CodeChef Chapter Inaugration
Author: Jackson Jose
Testers: Nishank Suresh, Kabir Kanha, Vaibhav Gautam, Illisha Singh
Editorialist: Jackson Jose
DIFFICULTY:
Easy-Medium
PREREQUISITES:
Brute force
PROBLEM:
You are playing an RPG and initially, you have 1000 health points and 1000 attack points. You are required to break into a fortress with n guards, and each guard has an attack and health stat. You have grinded 5,000 XP from previous levels. An XP can be used to either raise your health or attack by a unit. You must spend all your XP before starting this challenge.
You fight with the guards one by one, and with each guard, you trade blows simultaneously, i.e., you lose health points equal to the opponent’s attack, and the opponent would lose health equal to your attack points. The person whose health becomes \leq 0 first loses the fight. In case it happens simultaneously for both, you win.
When a guard of the fortress is defeated you move on to the fight the next guard, but you do not recover the lost XP or health points.
QUICK EXPLANATION:
The constraints are low enough for a brute force approach, so iterate over every possible distribution and simulate the trades. If the player is able to beat the fortress in any distribution the print “YES”, else “NO”.
EXPLANATION:
Number of layers is atmost 10, and the number of distinct distributions that is possible is 5000. Simulation for each layer requires 5 operations at max (max layer health = 5000, minimum attack of player is 1000, so 5000/1000 = 5). So the total operations is at most 1050005 = 250,000, which can comfortably pass the 2 second time limit.
We let i be the XP points we are going to devote to health, and 5000-i be the XP points we are going to devote to attack.
Iterate over i from 0 to 5000, and simulate the game with the new health and attack. If the player manages to defeat all the guards then stop the program and print YES, else if no distribution wins, then print NO.
SOLUTIONS:
Setter's Solution
#include <bits/stdc++.h>
using namespace std;
// This function simulates the game, i.e. the attacks between the player and the guards
bool canDefeat(int health, int attack, vector<vector<int>> fort, int n) {
//iterate over the layers
for (int i = 0; i < n; i++) {
//simulate trades till either layer's or player's health goes less zero
while (health > 0 && fort[i][0] > 0) {
health -= fort[i][1];
fort[i][0] -= attack;
}
//if player's health drops below zero or equal to zero before reaching last layer
if (health <= 0 && i != n - 1) {
return false;
}
}
//if last layer's health is less than 0 you win, it doesnt matter what your health is
return fort[n - 1][0] <= 0;
}
void SAO() {
int n;
cin >> n;
// Just a 2d vector
vector<vector<int>> fort(n, vector<int>(2));
for (int i = 0; i < n; i++) {
cin >> fort[i][0] >> fort[i][1];
}
// Iterate over every possible distribution, if any works print the answer.
int points = 5000;
int health = 1000, attack = 1000;
for(int i = 0; i <= 5000; i++) {
// i points go to health, 5000 - i points go to attack
int newHealth = i + health;
int newAttack = (5000 - i) + attack;
if (canDefeat(newHealth, newAttack, fort, n)) {
cout << "YES\n";
return;
}
}
cout << "NO\n";
}
int main() {
int test;
cin >> test;
while (test-- > 0) {
SAO();
}
return 0;
}
Tester's Solution (Kabir Kanha) in java
public class Main {
public static void main(String[] args) {
// Initial values
int XP = 5000;
int initialHealth = 1000;
int initialAttack = 1000;
// Input
Scanner scanner = new Scanner(System.in);
int t = scanner.nextInt();
while (t-- > 0) {
int n = scanner.nextInt();
int[] guardHealth = new int[n];
int[] guardAttack = new int[n];
for (int i = 0; i < n; ++i) {
guardHealth[i] = scanner.nextInt();
guardAttack[i] = scanner.nextInt();
}
boolean flag = false; // To check if a valid distribution was found.
// Brute force all possible distributions.
for (int addToAttack = 0; addToAttack <= 5000; ++addToAttack) {
boolean doable = true; // To check if this distribution works.
int attack = initialAttack + addToAttack;
int health = initialHealth + (XP - addToAttack);
for (int i = 0; i < n; ++i) {
int gHealth = guardHealth[i];
while (health > 0 && gHealth > 0) {
// Fight going on here...
health -= guardAttack[i];
gHealth -= attack;
}
if ((health <= 0 && i != n - 1) || gHealth > 0) {
doable = false;
break;
// This distribution doesn't work, move to next.
}
}
if (doable) {
// Found a working distribution, break from loop.
flag = true;
break;
}
}
if (flag)
System.out.println("YES");
else
System.out.println("NO");
}
}
}
Tester's Solution (Vaibhav Gautam) in python
import math
T = int(input())
while T > 0:
n = int(input())
health = 1000
attack = 1000
poss = False
fort = []
for i in range(0, n):
x, y = map(int, input().split())
fort.append((x, y))
for i in range(1, 5001):
health = 1000 + i
attack = 1000 + 5000 - i
XY = []
for a in fort:
XY.append(a)
for j in range(0, n):
while health > 0 and XY[j][0] > 0:
health -= XY[j][1]
XY[j] = (XY[j][0] - attack, XY[j][1])
if health <= 0 and i != (n - 1):
poss = False
if XY[n - 1][0] <= 0:
poss = True
if poss:
# print("i=",i)
break
if poss:
print("YES")
else:
print("NO")
T -= 1