BG Development


  Reply to this topicStart new topicStart Poll

> 
Sharpirate
: 17-06-2018, 18:40
Quote Post



:
:
:

: 2
: 17.06.18



!
. , . :
QUOTE
A jeweler is given an order to make a crown. He is given a set of n precious stones of sizes s1, ..., sn. The size of each stone is proportional to its value.

To make the crown perfect, he has decided to attach two rows of stones of equal length to the front of the crown. All the stones in a row must be of the same size, and the jeweler can't have any leftovers, so he must use all available stones of that size.

In order to make the crown as valuable as possible, the jeweler would like to use the maximum total number of stones. If there are multiple choices for maximizing the number of stones, he should choose the one that has the larger maximum size of stone.

You need to help the jeweler choose the stones for the two rows. Return the largest stone size that would be attached to the most valuable possible crown, or -1 if it is impossible to design the crown with the given set of stones.

Example

For stones = [1, 1, 1, 2, 2, 2, 3, 3, 4, 4, 6, 6, 5], the output should be stonesForCrown(stones) = 2.

There are 4 possibilities for the sets of stones the jeweler could use: (2, 2, 2, 1, 1, 1), (4, 4, 3, 3), (6, 6, 4, 4) and (6, 6, 3, 3). Although (6, 6, 4, 4) would have the largest stones, (2, 2, 2, 1, 1, 1) has the most stones, so the answer is 2.

For stones = [1, 1, 2, 2, 3, 3, 7], the output should be stonesForCrown(stones) = 3.

There are 3 possible crowns that could be made from these stones: (2, 2, 1, 1), (3, 3, 1, 1), and (3, 3, 2, 2). All of these contain the same number of stones, and the largest size is 3, so the answer is 3.

For stones = [1, 2, 2, 7, 7, 7], the output should be stonesForCrown(stones) = -1.

It's not possible for the jeweler to make 2 rows of equal length from these stones (remember: he must use all the stones of each chosen size).

Input/Output

[execution time limit] 3 seconds (java)

[input] array.integer stones

An array of integers representing the sizes of each of the stones.

Guaranteed constraints:
1 ≤ stones.length ≤ 105,
1 ≤ stones[i] ≤ 103.

[output] integer

The largest stone size that would be attached to the most valuable possible crown, or -1 if it is impossible to design a crown with the given set of stones.


, . ( , 100 000 ):
QUOTE
[1, 1, 1, 2, 2, 3, 3, 3, 3, 4 ...]


LinkedHashMap<Integer, Integer> , . Linked ( , ):
QUOTE
1 : 5
2 : 4
3 : 8...


. HashMap- -, - -. . , . icon_smile.gif

PMEmail Poster
Top
dvader
: 17-06-2018, 23:26
Quote Post


Group Icon
:
: VIP
:

: 4066
: 12.07.05



- - "" .


--------------------
I find your lack of faith disturbing
PM
Top
alphasoftwarebg
: 17-06-2018, 23:31
Quote Post



:
:
:

: 523
: 23.12.12



Java ZZZServer. Java icon_smile.gif

CODE
package bg.zzz;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.net.Socket;

public class Main {

static String stonesProgram =
"#[.=; stones ;[" +
"{ \"stones\":%s }" +
"]]" +
""+
"#[.=; add size ;[" +
"#[ add the path. ;/sizes/{size}/;[" +
"#[ change ;#[+;1;#[ get ];0]]" +
"]]" +
"]]" +
"#[=.; add size ;{size}]" +
"" +
"#[ base ;temp_stones.zzz]" + // temp_
"" +
"#[ remove the base ]" +
"#[ open the base for writing. ;[" +
"#[ JSON2ZZZ ;/input/;##[ stones ]]" +
"" +
"#[ move to the path. ;/input/stones/;[" +
"#[{ .? };[" +
"#[.=;_index_;#[ get ]]" +
"#[ subset ]" +
"#[ add size ;#[ get ]]" +
"#[ move to the path ;/input/stones/##[_index_]]" +
"];[" +
"#[ next? ]" +
"]]" +
"]]" +
"" +
"#[ move to the path. ;/sizes/;[" +
"#[{ .? };[" +
"#[.=;_size_;#[ get ]]" +
"#[ subset ]" +
"#[ add the path ;/counts/#[ get ]/##[_size_]]" +
"#[ move to the path ;/sizes/##[_size_]]" +
"];[" +
"#[ next? ]" +
"]]" +
"]]" +
"" +
"#[.=;_result_;-1]" +
"#[ move to the path. ;/counts/;[" +
"#[ last. ;[" +
"#[{ .? };[" +
"#[>=n;#[ elements count ];2;[" +
"#[.=;_ok_]" +
"#[ subset. ;[" +
"#[ last. ;[" +
"#[=;_result_;#[ get ]]" +
"]]" +
"]]" +
"];[" +
"#[.=;_ok_;#[ previous? ]]" +
"]]" +
"];[" +
"##[_ok_]" +
"]]" +
"]]" +
"]]" +
"#[out;##[_result_]]" +
"]]";

public static String ZZZProgram(String serverHost, int serverPort, String program) {
String result = "";

try {
if(serverHost.equals("localhost"))
serverHost = "127.0.0.1";
Socket socket = new Socket(serverHost, serverPort);
PrintWriter out = new PrintWriter(new OutputStreamWriter(socket.getOutputStream(), "UTF-8"), true);
BufferedReader in = new BufferedReader(new InputStreamReader(socket.getInputStream(), "UTF-8"));

out.print(program + '\0');
out.flush();

StringBuilder sb = new StringBuilder();
int DEFAULT_BUFFER_SIZE = 1000;
char buf[] = new char[DEFAULT_BUFFER_SIZE];
int n;
while ((n = in.read(buf)) > 0) {
sb.append(buf, 0, n);
}
result = sb.toString();

out.close();
in.close();
socket.close();
} catch(Exception e) {
e.printStackTrace();
}
return result;
}

public static void main(String[] args) {
long startTime = System.currentTimeMillis();

String program = String.format(stonesProgram, "[1, 1, 1, 2, 2, 2, 3, 3, 4, 4, 6, 6, 5]");
//String program = String.format(stonesProgram, "[1, 1, 2, 2, 3, 3, 7]");
//String program = String.format(stonesProgram, " [1, 2, 2, 7, 7, 7]");
System.out.println(ZZZProgram("demo.zzz.bg", 80, program));

long stopTime = System.currentTimeMillis();
long elapsedTime = stopTime - startTime;
System.out.println(elapsedTime + " milliseconds");
}
}


alphasoftwarebg 17-06-2018, 23:56

( : 7 )
  stones.ttm


--------------------
zzz.bg - NoSQL ZZZ Base...
PMEmail PosterUsers Website
Top
Sharpirate
: 18-06-2018, 16:08
Quote Post



:
:
:

: 2
: 17.06.18



QUOTE (dvader @ 17-06-2018, 23:26)
- - "" .

. .
PMEmail Poster
Top
wqw
: 21-06-2018, 12:03
Quote Post


Group Icon
:
: VIP
:

: 5752
: 10.06.04



QUOTE (Sharpirate @ 17-06-2018, 18:40)
LinkedHashMap<Integer, Integer> , .

int ?

( ) size . `stoneCountBySize[size]++`

stoneCountBySize .

: count stoneCountBySize `setsByStoneCount[count]++`

- setsByStoneCount, setsByStoneCount[result] >= 2, result -1

result

cheers,
</wqw>


--------------------
PMEmail PosterUsers Website
Top
1 (1 , 0 )
, :
« | Java | »

Topic Options Reply to this topicStart new topicStart Poll

 


Copyright © 2003-2018 | BG Development | All Rights Reserved
RSS 2.0