NOTE: You'll have to change the file I/O locations!
using System;
using System.Collections.Generic;
namespace BMilkshakes
{
class Program
{
///*
public class Flavor
{
public int flavor;
public bool malted;
public Flavor(int f, bool m)
{
flavor = f;
malted = m;
}
//for final list only
public bool required;
}
public class Customer
{
public Flavor[] flavorsLiked;
public bool hasMalted;
public int maltedIndex;
public Customer(int numFlavorsLiked)
{
flavorsLiked = new Flavor[numFlavorsLiked];
}
}
static void Main(string[] args)
{
System.IO.StreamReader file =
new System.IO.StreamReader("C:\\Users\\Aron\\Downloads\\B-large-practice.in");
System.IO.StreamWriter fileOut =
new System.IO.StreamWriter("C:\\Users\\Aron\\Desktop\\Google Output.txt");
int testCases = int.Parse(file.ReadLine());
for (int i = 0; i < testCases; i++)
{
int numFlavors = int.Parse(file.ReadLine());
int numCustomers = int.Parse(file.ReadLine());
Customer[] customers = new Customer[numCustomers];
Flavor[] flavors = new Flavor[numFlavors];
for (int iflavor = 0; iflavor < numFlavors; iflavor++)
{
flavors[iflavor] = new Flavor(iflavor + 1, false); //start off all unmalted
}
bool impossible = false;
//go through all customers
for (int ic = 0; ic < numCustomers; ic++)
{
string[] customerInfo = file.ReadLine().Split(' ');
if (impossible) continue;// if we know it's impossible, read data but don't process it
//store data in Customer
Customer c = new Customer(int.Parse(customerInfo[0]));
int cfCount = 0;
for (int ici = 1; ici < customerInfo.Length; ici += 2)
{
c.flavorsLiked[cfCount] = new Flavor(int.Parse(customerInfo[ici]), int.Parse(customerInfo[ici + 1]) == 1);
if(c.flavorsLiked[cfCount].malted)
{
c.hasMalted = true;
c.maltedIndex = cfCount;
}
cfCount++;
}
customers[ic] = c;
if(c.flavorsLiked.Length == 1)
{
Flavor cFlavor = c.flavorsLiked[0];
Flavor flavor = flavors[c.flavorsLiked[0].flavor - 1];
if (flavor.required)
{
if(flavor.malted != cFlavor.malted) impossible = true;
}
else
{
flavor.malted = cFlavor.malted;
flavor.required = true;
}
}
}
if(impossible)
{
fileOut.WriteLine("Case #{0}: IMPOSSIBLE", i + 1);
continue;
}
bool needsProcessing = true;
//repeatedly go through customers until we reach a solution
while (!impossible && needsProcessing)
{
needsProcessing = false; //will be flagged true if we need a rerun
//go through all customers
for (int ic = 0; ic < numCustomers; ic++)
{
Customer c = customers[ic]; //pull customer
//customer will be treated differently if they have a malted flavor
if (c.hasMalted)
{
bool satisfied = false;
//go through all flavors
for (int iflav = 0; iflav < c.flavorsLiked.Length; iflav++)
{
//pull flavor from main array (-1 due to index offset)
Flavor flavor = flavors[c.flavorsLiked[iflav].flavor - 1];
//if the flavor has the same malt, customer is satisfied
if (flavor.malted == c.flavorsLiked[iflav].malted)
{
satisfied = true;
break;
}
}
//if customer is unsatisfied
if (!satisfied)
{
//pull flavor, that customer needs malted, from main array (-1 for index offset)
Flavor flavor = flavors[c.flavorsLiked[c.maltedIndex].flavor - 1];
//if the flavor cannot be changed
if (flavor.required)
{
impossible = true; //we cannot satisfy this customer
break;
}
else //flavor can be changed
{
//change flavor to malted
flavor.malted = true;
//we can no longer alter this flavor
flavor.required = true;
//we will need to process customers again
needsProcessing = true;
break;
}
}
}
else //customer does not have a malted that they like
{
//we need see if one of our flavors match
bool satisfied = false;
for (int iflav = 0; iflav < c.flavorsLiked.Length; iflav++)
{
//pull flavor from main array (-1 for index offset)
Flavor flavor = flavors[c.flavorsLiked[iflav].flavor - 1];
//if the flavor is unmalted, customer is satisfied
if (!flavor.malted)
{
satisfied = true;
break;
}
}
//if customer is unsatisfied
if (!satisfied)
{
//all the malted flavors will be required
//so we cannot change them and it is impossible to satisfy
impossible = true;
break;
}
}
}
}
if (impossible)
{
fileOut.WriteLine("Case #{0}: IMPOSSIBLE", i + 1);
continue;
}
fileOut.WriteLine("Case #{0}: {1}", i + 1, string.Join(" ", Array.ConvertAll(flavors, x => (x.malted ? "1" : "0"))));
}
file.Close();
fileOut.Close();
}
//*/
}
}
