Concluído

C++ project

This problem is based on the classic puzzle of how you can measure out a specific amount of water using buckets of different sizes and a hose. Initially, all of the buckets are empty, and at each point, the only legal moves are: filling up a bucket, dumping out a bucket, or transferring the water in one bucket into another. Note that a transfer will either empty out the bucket it is pouring from or fill up the bucket it is pouring into, whichever happens first.

For example, suppose you want to measure out 4 gallons of water using a 3-gallon bucket and a 5-gallon bucket. You might fill up the 5-gallon bucket (5 gal, 0 gal), transfer the 3 gallons to the 3-gallon bucket (2 gal, 3 gal), dump the 3-gallon bucket (2 gal, 0 gal), transfer 2 gallons to the 3-gallon bucket (0 gal, 2 gal), fill the 5-gallon bucket again (5 gal, 2 gal), transfer 1 gallon to the 3-gallon bucket (4 gal, 3 gal), and finally dump the 3-gallon bucket (4 gal, 0 gal). This is the most efficient solution, which takes 7 moves.

This program is a twist on the original problem. Instead of describing how to make a given amount of water, your problem is to identify the amount of water that takes the most moves to make. The amount of water in a given set of buckets is the sum of the water in all buckets. In the previous example, the two buckets can have from 0 up to 8 gallons of water between them, and 4 gallons takes the greatest number of moves to make.

Input:

The program should read its input from the file [login to view URL], in the following format. The first line of the input has one positive integer, n, representing the number of buckets. The next linecontains n positive integers, representing the size of each bucket. The bucket sizes will be given indecreasing order.

The number and size of the buckets will be such that your graph will never have more than 1 million vertices or 10 million edges

Output:

The program should write its output to the file [login to view URL], in the following format. You should write one line with 4 positive integers, separated by spaces.

The first two integers will be the number of vertices and the number of edges in the graph,respectively. Note: these numbers should be the number of vertices and edges in the entire graph.

The third and fourth integers should be the most difficult amount of water to make and the number of moves that amount takes, respectively. If there is a tie for the amount that takes the greatest number of moves, output the smallest amount of water that takes this many moves.

Deliverables

input sample:

2

5 3

output sample:

24 106 4 7

input sample:

2

999 998

output sample:

999000 5986006 499 1995

input sample:

4

43 19 7 3

output sample:

28160 465696 2 7

Habilidades: Algoritmo, Programação C++

Veja mais: c++ projects for resume, c++ projects source code, c++ project ideas list, c++ projects github, advanced c++ project ideas, c++ projects for class 12, c++ projects ideas, c++ projects for engineering

Acerca do Empregador:
( 8 comentários ) Hyderabad, India

ID do Projeto: #19323088

Concedido a:

marianakuzmich

Hi, I have rich experience of C++ programming. I have done job as same as your requirement before. I checked your requirement. I'm sure that I can easily do this project. I will do my best for you. best regards.

₹7000 INR em 2 dias
(19 Comentários)
4.6

4 freelancers estão ofertando em média ₹3088 para esse trabalho

YanLee911

Dear sir. Thank you for giving me this opportunity to bid on your project. I read your job requirement and wish I can work on your project. I've a rich experience in the developments with c, c++ and c# and you can Mais

₹3500 INR em 1 dia
(4 Comentários)
3.6
Isfaaq

Complete solution with an efficient algorithm so that it passes large test cases. Comments will be included if required

₹1250 INR in 2 dias
(1 Comentário)
0.5
ducdac

I am now reading your project detail. But I have no problem with Algorithm. I have worked for over ten years studying algorithm. I'm sure I can solve your project. Hope to see in a chatting room.

₹600 INR em 1 dia
(0 Comentários)
0.0