Databases
StackOverflow2013
Postsdbo
POSPOJ ANARC07G Let go to the movies approach
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POSPOJ ANARC07G Let go to the movies approach
    primarykey
    data
    text
    <p>In <a href="http://www.spoj.com/problems/ANARC07G/" rel="nofollow noreferrer">this</a> question we have to find the number of single and family tickets needed such that the price is minimum. If the price is same for many arrangements, then print the arrangement with minimum tickets.</p> <p><strong>Problem Statement</strong> Movie theaters in Acmestan have two types of tickets: A single ticket is for exactly one person while a family ticket allows a parent and their children to enter the theater. Needless to say, a family ticket is always priced higher than a single ticket, sometimes as high as five times the price of a single ticket. </p> <p>It is quite challenging for families to decide which ticket arrangement is most economical to buy. For example, the family depicted in the figure on the right has four ticket arrangements to choose from: Seven single tickets; Two family tickets; One family ticket (for adam, bob, cindy)plus four single tickets for the rest; Or, one family ticket (for bob and his four children) plus single tickets for the remaining two.</p> <p>Write a program to determine which ticket arrangement has the least price. If there are more than one such arrangement, print the arrangement that has the least number of tickets.</p> <p><img src="https://i.stack.imgur.com/4RXPW.jpg" alt="enter image description here"></p> <p>My DP approach is as follows:-</p> <ol> <li><p>Make the family tree.</p></li> <li><p>Each node should have fields min_tickets(i.e. minimum number of tickets) and min_price(i.e. minimum price). These fields denote the minimum amounts needed to take that person and his children out. Also, there are fields denoting the number of family tickets(fam_tickets) and number of single tickets(sin_tickets) involved in the process. </p></li> <li><p>Start from the leaf nodes. Initialise <code>min_tickets=1</code> and <code>min_price= S</code>(i.e. price of single ticket), <code>fam_tickets=0</code>, <code>sin_tickets= 1</code>.</p></li> <li><p>Now for other nodes take into consideration his children and grandchildren. F is the price of family ticket. For them:-</p> <blockquote> <p>min_price= min(F + min_price of all grandchildren summed , S + min_price of all children summed)</p> </blockquote> <p>If a grandchild is NULL, we take the <code>min_price=0 and min_tickets=0</code></p></li> <li><p>To find out min_tickets, we derive it from the formation giving us minimum price. If both formations come down to the same price, we do:-</p></li> </ol> <blockquote> <pre><code> if(1+ min_tickets of all grandchildren summed &gt; 1+ min_tickets of all children summed) min_tickets = 1+ min_tickets of all children summed; fam_tickets= fam_tickets of all children summed; sin_tickets= 1+ sin_tickets of all children summed; else min_tickets = 1+ min_tickets of all grandchildren summed; fam_tickets= 1+ fam_tickets of all grandchildren summed; sin_tickets= sin_tickets of all grandchildren summed; </code></pre> </blockquote> <p>Is this solution correct? Thanks in advance.</p>
    singulars
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. PTQuestion
    1. USMartijn Pieters
    1. USAvinash Kumar
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. PO
      singulars
      1. PTAnswer
    1. VO
      singulars
      1. POSPOJ ANARC07G Let go to the movies approach
      1. This table or related slice is empty.
      1. VTUpMod
    1. COLooks complicated (which is a bad sign), this problem seems very similar to minimum vertex cover problem. But DP is a correct choice I think.
      singulars
      1. POSPOJ ANARC07G Let go to the movies approach
      1. USPham Trung
    2. COI think your solution is correct. Are you facing any specific problem?
      singulars
      1. POSPOJ ANARC07G Let go to the movies approach
      1. USAbhishek Bansal
    3. CO@AbhishekBansal...no..just wanted to check
      singulars
      1. POSPOJ ANARC07G Let go to the movies approach
      1. USAvinash Kumar
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload