Topic link

Description

George took sticks of the same length and cut them randomly until all parts became at most 50 units long. Now he wants to return sticks to the original state, but he forgot how many sticks he had originally and how long they were originally. Please help him and design a program which computes the smallest possible original length of those sticks. All lengths expressed in units are integers greater than zero.

Input

The input contains blocks of 2 lines. The first line contains the number of sticks parts after cutting, there are at most 64 sticks. The second line contains the lengths of those parts separated by the space. The last line of the file contains zero.

Output

The output should contains the smallest possible length of original sticks, one per line.

Sample Input

9
5 2 1 5 2 1 5 2 1
4
1 2 3 4
0

Sample Output

6
5 The question : Yes n Duan stick , Request this n It's made of two sticks x A stick of the same length , Make the new stick as short as possible , Output min ? Ideas : Search for , The length of the new stick must be greater than or equal to the maximum of the original stick maxlen, Less than or equal to the total length of these sticks sum, So growing up (maxlen~sum) Traverse these values , If sum%i!=0 , You can't make a legal stick and jump over it ;
If sum%i==0, Then it's possible to satisfy , Search . search process : Deep search one by one , The record has been put together into several sticks at present , How long is it from the stick , Used sticks v[i] marked . The code is as follows :
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;
int start,sum;
int v[]; int check(int num,int rest,int pos)
{
if(num==sum/start) return ;
rest-=pos; v[pos]--;
if(rest==)
{
int i;
for(i=; i>=; i--) if(v[i]) break;
int flag=check(num+,start,i);
v[pos]++;
return flag;
}
for(int i=rest; i>=; i--)
{
if(!v[i]) continue;
int flag=check(num,rest,i);
if(flag) return ;
}
v[pos]++;
return ;
} int main()
{
int n;
while(scanf("%d",&n)&&n)
{
int maxn=-;
sum=;
memset(v,,sizeof(v));
for(int i=; i<=n; i++)
{
int x; scanf("%d",&x);
sum+=x;
v[x]++;
maxn=max(maxn,x);
}
for(start=maxn; start<=sum; start++)
{
if(sum%start!=) continue;
if(check(,start,maxn))
{
printf("%d\n",start);
break;
}
}
}
return ;
}
/**
9
21 16 33 36 19 1 35 6 47
ans=107 43
46 16 47 31 22 48 10 47 25 48 33 31 35 33 14 21 8 22 20 37 20 48 8 18 3 44 28 16 9 50 44 18 46 28 43 49 18 19 31 46 3 43 43
ans=141
*/ /**
20
4 2 1 6 6 5 6 9 1 0 6 9 0 4 8 3 2 1 1 6
20
6 8 9 4 5 10 6 5 8 5 5 7 9 6 3 10 3 1 9 9
*/

poj 1011--Sticks( Search for ) More articles about

  1. POJ 1011 sticks Search for

    Sticks Time Limit: 1000MS   Memory Limit: 10000K Total Submissions: 125918   Accepted: 29372 Descrip ...

  2. Search for + prune ——POJ 1011 Sticks

    Search for + prune --POJ 1011 Sticks Blog classification : Algorithm Very classic search topic , The first time I did it was during summer training , I turned it out the day before yesterday Originally, I wanted to feel something , I don't want to build on the original idea , I made it, and it's still 0 ...

  3. DFS( prune ) POJ 1011 Sticks

    Subject portal /* The question : Some sticks , It is made of several long sticks of the same length , Ask the length of the smallest original long stick : DFS prune : A good topic for pruning search !TLE Several times , Finally the pruning is complete ! Pruning is mainly in 4 and 5:4 Sticks of the same length are no longer searched ...

  4. POJ 1011 - Sticks DFS+ prune

    POJ 1011 - Sticks The question :    A piece of wood of equal length is cut randomly into n A little piece of wood     Given their respective lengths , What is the minimum possible length of these sections analysis :    1. The length must be divisible by the total length     ...

  5. OpenJudge 2817: stick / Poj 1011 Sticks

    1. Link address : http://bailian.openjudge.cn/practice/2817/ http://poj.org/problem?id=1011 2. subject : Total time limit : 1000m ...

  6. POJ 1011 Sticks 【DFS prune 】

    Topic link :http://poj.org/problem?id=1011 Sticks Time Limit: 1000MS   Memory Limit: 10000K Total Submissio ...

  7. POJ 1011 Sticks( Search for &amp;&amp; prune &amp;&amp; classic )

    The question :  Yes n A stick (n<=64), They're cut from sticks of the same length , Given this n The length of a stick , Find the minimum value that makes the original length possible . analysis : A classic deep search topic , We found that the answer could only be a factor of the sum of the lengths of all the sticks , ...

  8. poj 1011 Sticks (DFS+ prune )

    Sticks Time Limit: 1000MS   Memory Limit: 10000K Total Submissions: 127771   Accepted: 29926 Descrip ...

  9. POJ 1011 Sticks dfs, prune difficulty :2

    http://poj.org/problem?id=1011 To divide a given set into several sets , The sum of each set ans equal , And ans Minimum , Because this and ans Only in [1,64*50] Inside , So it can be used dfs One try First ...

  10. POJ 1011 Sticks(dfs+ prune )

    http://poj.org/problem?id=1011 The question : Several sticks of the same length are cut into sticks of different lengths , Find the original minimum possible length of each stick . Ideas : It's a classic search question . I started with all kinds of overtime , This problem needs a lot of pruning ...

Random recommendation

  1. ASP.NET about excel Data import into database

    //*******************************C#(UI Code )********************************/ Web Put one on the interface FileUpload The name is :F ...

  2. USACO Section 2.1: Hamming Codes

    It's a very simple question /* ID: yingzho1 LANG: C++ TASK: hamming */ #include <iostream> #include <fstream> ...

  3. iOS OpenCV The lack of 64 Bit solution

  4. Aurora push , Aurora IM Use guide (AndroidStudio)

    Go to the official website to create an application , Then download the above example program , Compare to the integration document , hold libs Inside jar and so Put the file into the libs below , Remember to jar want as a library, Then configure the manifest file , In contrast to Demo Come on , Well configured ...

  5. Remmarguts&#39; Date POJ - 2449 (A* Search for |k A short circuit )

    "Good man never makes girls wait or breaks an appointment!" said the mandarin duck father. ...

  6. Swift Type bridging

    Preface iOS Medium API Basically, it was many years ago OC written , Now by bridging in Swift Can be used in the , I can't see the difference , It's very natural . But some special types , Special attention should be paid when bridging two languages . 1.N ...

  7. POJ 2391 Ombrophobic Bovines (Floyd + Dinic + Two points )

    Ombrophobic Bovines Time Limit: 1000MS   Memory Limit: 65536K Total Submissions: 11651   Accepted: 2 ...

  8. oracle Create simple packages

    -- standard create or replace package test_pkg is --test_pkg For the package name procedure showMessage; -- Declare a process function my ...

  9. Use ZooKeeper Realization Java Span JVM Distributed locks for ( Read-write lock )

    One . Use ZooKeeper Realization Java Span JVM Distributed locks for Two . Use ZooKeeper Realization Java Span JVM Distributed locks for ( Optimize the idea ) 3、 ... and . Use ZooKeeper Realization Java Span JVM Distributed locks for ( Read-write lock ) Reading and writing ...

  10. Network connection and initial HTTP request

    The browser searches the web page , First from URL Start , Use DNS determine IP Address , And then based on TCP and HTTP Protocol to connect to the server , Request related content , Get the corresponding , The browser parses and presents it to the screen . After the server responds , Browser responses don't all arrive at the same time , It will come one after another ...