Question

Suppose that you have just bought a new computer and you want to install soft- ware on that. Specifically, two companies, which you can think of like Microsoft and Apple, are trying to sell their own copy of n different products, like Opera- tion System. Spread Sheet, Web Browser. For each product i, i c {1,2,...,n}, we have • the price pi > 0 that Microsoft charges and the price p > 0 that Apple charges. • the quality li > 0 of Microsoft version and the quality d > 0 of Apple version For example, Apple may provide a better Web Browser Safari, but Microsoft a better Word Processor. You want to assemble your favorite computer by installing exactly one copy of each of the n products, e.g. you want to buy one operating system, one Web Browser, one Word Processor, etc. However, you don't want to spend too much money on that. Therefore, your goal is to maximize the quality minus total price. However, as you may know, the products of different companies may not be compatible. More concretely, for each product pair (i, j), we will suffer a penalty Tij > 0 if we install product i of Microsoft and product of Apple. Note that Tij may not be equal to Tji just because Apple's Safari does not work well on Microsoft Windows doesn't mean that Microsoft's Edge does not work well in Mac-OS. We assume that products are always compatible internally, which means that there is no penalty for installing two products from the same company. All pairwise penalties will be subtracted from the total quality of the system. Your task is then to give a polynomial-time algorithm for computing which product i to purchase from which of the two companies (Apple and Microsoft) for all i E {1,2,...,n}, to maximize the total system quality (including the penalties) minus the total price. Prove the correctness of your algorithm. (Hint: You may model this problem as a max-flow/min-cut problem by constructing your graph appropriately.)

Answer 1

#importing the time module

import time

#welcoming the user

name = raw_input("What is your name? ")

print "Hello, " + name, "Time to play hangman!"

print "

"

#wait for 1 second

time.sleep(1)

print "Start guessing..."

time.sleep(0.5)

#here we set the secret

word = "secret"

#creates an variable with an empty value

guesses = ''

#determine the number of turns

turns = 10

# Create a while loop

#check if the turns are more than zero

while turns > 0:

# make a counter that starts with zero

failed = 0

# for every character in secret_word

for char in word:

# see if the character is in the players guess

if char in guesses:

# print then out the character

print char,

else:

# if not found, print a dash

print "_",

# and increase the failed counter with one

failed += 1

# if failed is equal to zero

# print You Won

if failed == 0:

print "

You won"

# exit the script

break

print

# ask the user go guess a character

guess = raw_input("guess a character:")

# set the players guess to guesses

guesses += guess

# if the guess is not found in the secret word

if guess not in word:

# turns counter decreases with 1 (now 9)

turns -= 1

# print wrong

print "Wrong

"

# how many turns are left

print "You have", + turns, 'more guesses'

# if the turns are equal to zero

if turns == 0:

# print "You Lose"

print "You Lose

"