[usaco]罗马数字

Preface Numbering

A certain book’s prefaces are numbered in upper case Roman numerals. Traditional Roman numeral values use a single letter to represent a certain subset of decimal numbers. Here is the standard set:

        I   1     L   50    M  1000
        V   5     C  100
        X  10     D  500

As many as three of the same marks that represent 10n may be placed consecutively to form other numbers:

III is 3
CCC is 300
Marks that have the value 5x10n are never used consecutively.

Generally (with the exception of the next rule), marks are connected together and written in descending order to form even more numbers:

CCLXVIII = 100+100+50+10+5+1+1+1 = 268
Sometimes, a mark that represents 10^n is placed before a mark of one of the two next higher values (I before V or X; X before L or C; etc.). In this case, the value of the smaller mark is SUBTRACTED from the mark it precedes:

IV = 4
IX = 9
XL = 40
This compound mark forms a unit and may not be combined to make another compound mark (e.g., IXL is wrong for 39; XXXIX is correct).

Compound marks like XD, IC, and XM are not legal, since the smaller mark is too much smaller than the larger one. For XD (wrong for 490), one would use CDXC; for IC (wrong for 99), one would use XCIX; for XM (wrong for 990), one would use CMXC. 90 is expressed
XC and not LXL, since L followed by X connotes that successive marks are X or smaller (probably, anyway).

Given N (1 <= N < 3,500), the number of pages in the preface of a book, calculate and print the number of I’s, V’s, etc. (in order from lowest to highest) required to typeset all the page numbers (in Roman numerals) from 1 through N. Do not print letters
that do not appear in the page numbers specified.

If N = 5, then the page numbers are: I, II, III, IV, V. The total number of I’s is 7 and the total number of V’s is 2.

PROGRAM NAME: preface
INPUT FORMAT
A single line containing the integer N.
SAMPLE INPUT (file preface.in)
5

OUTPUT FORMAT
The output lines specify, in ascending order of Roman numeral letters, the letter, a single space, and the number of times that letter appears on preface page numbers. Stop printing letter totals after printing the highest value letter used to form preface
numbers in the specified set.
SAMPLE OUTPUT (file preface.out)
I 7
V 2

 

————————————————————————————————————————
题目给出一个整数N,要求求出1-》N的所有的罗马数表示法,然后统计各个字母的数量。

由罗马数的表示法,可以看出,每一位上的表示是基本相同的,
比如1->9
I II III IV V VI VII VIII IX
10 ->90
X XX XXX XL L LX LXX LXXX XC

从上边可以看出一些规律。
因此每一位数字需要3个字母即可表示出来。
我们定义以下二维数组:
char index1[4][3]={
 {‘I’,’V’,’X’},
 {‘X’,’L’,’C’},
 {‘C’,’D’,’M’},
 {‘M’}
};
因此可以用这个数组表示一位数:
10^r->9*10^r:
index1[r][0]   index1[r][0]index1[r][0]   index1[r][0]index1[r][0]index1[r][0] index1[r][0]index1[r][1] index1[r][1]
index1[r][1]index1[r][0] index1[r][1]index1[r][0]index1[r][1] index1[r][1]index1[r][0]index1[r][1]index1[r][0]index1[r][0]index1[r][0] index1[r][0]index1[r][2]
因此我的解法是:
—————————————————————————————————————————
 

/*
ID: yunleis2
PROG: preface
LANG: C++
*/
#include<fstream>
#include<iostream> 
using namespace std;
int result[7]={0};
char str[7]={'I','V',
'X','L',
'C','D','M'};
void getNum1(int r,int c);
int getindex11(char c);
char index1[4][3]={
	{'I','V','X'},
	{'X','L','C'},
	{'C','D','M'},
	{'M'}
};
int main()
{
	fstream fin("preface.in",ios::in);
	int N;
	fin>>N;
	for(int i=1;i<=N;i++)
	{
		int r=0;
		int t=i;
		while(t!=0)
		{
			getNum1(r,t%10);
			r++;
			t=t/10;
		}
	}
	fstream fout("preface.out",ios::out);
	for(int i=0;i<7;i++)
	{
		if(result[i]!=0)
		{
			fout<<str[i]<<" "<<result[i]<<endl;
		}
	} 
}
void getNum1(int r,int c)
{
	 
	if(c==1)
	{
		result[getindex11(index1[r][0])]++;
	}
	if(c==2)
	{
		result[getindex11(index1[r][0])]+=2;
	}
 
	if(c==3)
	{
		result[getindex11(index1[r][0])]+=3;
	}
	if(c==4)
	{
		result[getindex11(index1[r][0])]++;
		result[getindex11(index1[r][1])]++;
	}
	if(c==5)
	{
		result[getindex11(index1[r][1])]++;
	}
	if(c==6)
	{
		result[getindex11(index1[r][1])]++;
		result[getindex11(index1[r][0])]++;
	}
	if(c==7)
	{
		result[getindex11(index1[r][1])]++;
		result[getindex11(index1[r][0])]++;
		result[getindex11(index1[r][0])]++;
	}
	if(c==8)
	{
		result[getindex11(index1[r][1])]++;
		result[getindex11(index1[r][0])]++;
		result[getindex11(index1[r][0])]++;
		result[getindex11(index1[r][0])]++;
	}
	if(c==9)
	{
		result[getindex11(index1[r][0])]++;
		result[getindex11(index1[r][2])]++;
	}
}
int getindex11(char c)
{
	if(c=='I')
		return 0;
	if(c=='V')
		return 1;
	if(c=='X')
		return 2;
	if(c=='L')
		return 3;
	if(c=='C')
		return 4;
	if(c=='D')
		return 5;
	if(c=='M')
		return 6;
}

 

Hadoop的环境搭建,和编写一个简单的hadoop job

hadoop 入门:

0hadoop的简要介绍
google之所以能够成功,一个重要的技术就是map-reduce。map-reduce是google为大规模的、分布式数据进行处理的一种编程模式。
而本文介绍的hadoop是apache的开源map-reduce实现。本文不过多的介绍map-reduce,主要精力放在hadoop的配置和编写一个简单的haoop程序上
对map-recude感兴趣的朋友可以进一步阅读参考文献。
1 hadoop服务器的安装:
hadoop是一个分布式的处理框架,本文先介绍的是一个简单的伪分布式hadoop(安装在一个linux机器上)

配置环境是ubuntu
创建一个新文件/etc/sources.list.d/cloudera.list
把下边的内容复制到新文件:
 
deb http://archive.cloudera.com/debian intrepid-cdh3 contrib
deb-src http://archive.cloudera.com/debian intrepid-cdh3 contrib
 
 然后打开teminal输入下边的命令:
$ curl -s http://archive.cloudera.com/debian/archive.key | \
sudo apt-key add – sudo apt-get update

然后,安装采用伪分布式配置的 Hadoop(所有 Hadoop 守护进程在同一个主机上运行):

$ sudo apt-get install hadoop-0.20-conf-pseudo
 

 确保系统已经安装了sshd(如果没有,请先安装)。
 设置不需要密码的ssh:
     
$ sudo su –
# ssh-keygen -t dsa -P ” -f ~/.ssh/id_dsa
# cat ~/.ssh/id_dsa.pub >> ~/.ssh/authorized_keys

启动hadoop:
首先对namenode进行格式化:
# hadoop-0.20 namenode -format

Hadoop 提供一些简化启动的辅助工具。这些工具分为启动(比如 start-dfs)和停止(比如 stop-dfs)两类。下面的简单脚本说明如何启动 Hadoop 节点:

# /usr/lib/hadoop-0.20/bin/start-dfs.sh
# /usr/lib/hadoop-0.20/bin/start-mapred.sh
#
 
输入命令jps可以查看守护进程是否正在运行;

编写一个hadoop程序:
作为联系,我们从网上下载一个cvs格式的数据文件:
http://earthquake.usgs.gov/research/data/pager/EXPO_CAT_2007_12.csv
cvs是以逗号进行列分割的数据文件。
使用opencvs可以很方便的处理cvs格式的数据。
opencvs可以从sourceforge上下载。
opencvs可以把一个string以逗号进行分割成一个string数组
只扩展 Hadoop 的 Mapper 类。然后我可以使用泛型来为传出键和值指定显式类。类型子句也指定了传入键和值,这对于读取文件分别是字节数和文本行数。

EarthQuakesPerDateMapper 类扩展了 Hadoop 的 Mapper 对象。它显式地将其输出键指定为一个 Text 对象,将其值指定为一个 IntWritable,这是一个 Hadoop 特定类,实质上是一个整数。还要注意,class 子句的前两个类型是 LongWritable 和 Text,分别是字节数和文本行数。

由于类定义中的类型子句,我将传入 map 方法的参数类型设置为在 context.write 子句内带有该方法的输出。如果我想指定其他内容,将会出现一个编译器问题,或 Hadoop 将输出一个错误消息,描述类型不匹配的消息。

一个mapper的实现:

public class EarthQuakesPerDateMapper extends
  Mapper<LongWritable, Text, Text, IntWritable> {
 @Override
 protected void map(LongWritable key, Text value, Context context)
   throws IOException, InterruptedException {

  if (key.get() > 0) {
   try {
    CSVParser parser = new CSVParser();
    String[] lines = parser.parseLine(value.toString());
    lines = new CSVParser().parseLine(lines[0]);
    SimpleDateFormat formatter = new SimpleDateFormat(“yyyyMMddHHmm”);
    Date dt = formatter.parse(lines[0]);
    formatter.applyPattern(“dd-MM-yyyy”);

    String dtstr = formatter.format(dt);
    context.write(new Text(dtstr), new IntWritable(1));
   } catch (java.text.ParseException e) {
    // TODO Auto-generated catch block
    //e.printStackTrace();
   }
  }
 }
}
reduce 实现如下 所示。与 Hadoop 的 Mapper 一样,Reducer 被参数化了:前两个参数是传入的键类型(Text)和值类型(IntWritable),后两个参数是输出类型:键和值,这在本例中是相同的。

public class EarthQuakesPerDateReducer extends
  Reducer<Text, IntWritable, Text, IntWritable> {
 @Override
 protected void reduce(Text key, Iterable<IntWritable> values,
   Context context) throws IOException, InterruptedException {
  int count = 0;
  for (IntWritable value : values) {
   count++;
  }
  context.write(key, new IntWritable(count));
 }
}

写好mapper和reducer之后,就可以定义一个hadoop job了。

public class EarthQuakesPerDayJob {
 public static void main(String[] args) throws Throwable {
  Job job = new Job();
  job.setJarByClass(EarthQuakesPerDayJob.class);
  FileInputFormat.addInputPath(job, new Path(args[0]));
  FileOutputFormat.setOutputPath(job, new Path(args[1]));

  job.setMapperClass(EarthQuakesPerDateMapper.class);
  job.setReducerClass(EarthQuakesPerDateReducer.class);
  job.setOutputKeyClass(Text.class);
  job.setOutputValueClass(IntWritable.class);

  System.exit(job.waitForCompletion(true) ? 0 : 1);
 }
}

在linux上执行hadoop:
$> export HADOOP_CLASSPATH=lib/opencsv-2.3.jar
$> hadoop jar hadoop.jar in out
在程序所在目录定义一个子目录in,把刚才所下载的cvs文件放到in目录下。
in就是程序数据的输入目录,out是输出目录,注意这个out文件夹是程序建立的,不可以手动建立。
运行是会看到:
11/09/05 08:47:26 INFO jvm.JvmMetrics: Initializing JVM Metrics with processName=JobTracker, sessionId=
11/09/05 08:47:26 WARN mapred.JobClient: Use GenericOptionsParser for parsing the arguments. Applications should implement Tool for the same.
11/09/05 08:47:26 INFO input.FileInputFormat: Total input paths to process : 1
11/09/05 08:47:26 INFO mapred.JobClient: Running job: job_local_0001
11/09/05 08:47:26 INFO input.FileInputFormat: Total input paths to process : 1
11/09/05 08:47:26 INFO mapred.MapTask: io.sort.mb = 100
11/09/05 08:47:27 INFO mapred.MapTask: data buffer = 79691776/99614720
11/09/05 08:47:27 INFO mapred.MapTask: record buffer = 262144/327680
11/09/05 08:47:27 INFO mapred.JobClient:  map 0% reduce 0%
11/09/05 08:47:28 INFO mapred.MapTask: Starting flush of map output
11/09/05 08:47:28 INFO mapred.MapTask: Finished spill 0
11/09/05 08:47:28 INFO mapred.TaskRunner: Task:attempt_local_0001_m_000000_0 is done. And is in the process of commiting
11/09/05 08:47:28 INFO mapred.LocalJobRunner:
11/09/05 08:47:28 INFO mapred.TaskRunner: Task ‘attempt_local_0001_m_000000_0’ done.
11/09/05 08:47:29 INFO mapred.LocalJobRunner:
11/09/05 08:47:29 INFO mapred.Merger: Merging 1 sorted segments
11/09/05 08:47:29 INFO mapred.Merger: Down to the last merge-pass, with 1 segments left of total size: 97887 bytes
11/09/05 08:47:29 INFO mapred.LocalJobRunner:
11/09/05 08:47:29 INFO mapred.TaskRunner: Task:attempt_local_0001_r_000000_0 is done. And is in the process of commiting
11/09/05 08:47:29 INFO mapred.LocalJobRunner:
11/09/05 08:47:29 INFO mapred.TaskRunner: Task attempt_local_0001_r_000000_0 is allowed to commit now
11/09/05 08:47:29 INFO output.FileOutputCommitter: Saved output of task ‘attempt_local_0001_r_000000_0’ to out1
11/09/05 08:47:29 INFO mapred.LocalJobRunner: reduce > reduce
11/09/05 08:47:29 INFO mapred.TaskRunner: Task ‘attempt_local_0001_r_000000_0’ done.
11/09/05 08:47:29 INFO mapred.JobClient:  map 100% reduce 100%
11/09/05 08:47:29 INFO mapred.JobClient: Job complete: job_local_0001
11/09/05 08:47:29 INFO mapred.JobClient: Counters: 12
11/09/05 08:47:29 INFO mapred.JobClient:   FileSystemCounters
11/09/05 08:47:29 INFO mapred.JobClient:     FILE_BYTES_READ=11961631
11/09/05 08:47:29 INFO mapred.JobClient:     FILE_BYTES_WRITTEN=9370383
11/09/05 08:47:29 INFO mapred.JobClient:   Map-Reduce Framework
11/09/05 08:47:29 INFO mapred.JobClient:     Reduce input groups=142
11/09/05 08:47:29 INFO mapred.JobClient:     Combine output records=0
11/09/05 08:47:29 INFO mapred.JobClient:     Map input records=5639
11/09/05 08:47:29 INFO mapred.JobClient:     Reduce shuffle bytes=0
11/09/05 08:47:29 INFO mapred.JobClient:     Reduce output records=142
11/09/05 08:47:29 INFO mapred.JobClient:     Spilled Records=11274
11/09/05 08:47:29 INFO mapred.JobClient:     Map output bytes=86611
11/09/05 08:47:29 INFO mapred.JobClient:     Combine input records=0
11/09/05 08:47:29 INFO mapred.JobClient:     Map output records=5637
11/09/05 08:47:29 INFO mapred.JobClient:     Reduce input records=5637

运行完成后:
cd到out目录下,会看到一个part-r-00000文件。
输入命令:cat part-r-00000
可以看到hadoopjob的运行结果。

参考资料:
Java 开发 2.0: 用 Hadoop MapReduce 进行大数据分析

用 Hadoop 进行分布式数据处理,第 1 部分: 入门

MapReduce 编程模型在日志分析方面的应用

 

[usaco]5.3.2 Milk Measuring 动态规划

 
Milk Measuring
Hal Burch
Farmer John must measure Q (1 <= Q <= 20,000) quarts of his finest milk and deliver it in one big bottle to a customer. He fills that bottle with exactly the number of quarts that the customer orders.

Farmer John has always been frugal. He is at the cow hardware store where he must purchase a set of pails with which to measure out Q quarts of milk from his giant milk tank. Since the pails each cost the same amount, your task is to figure out a minimal
set of pails Farmer John can purchase in order to fill a bottle with exactly Q quarts of milk. Additionally, since Farmer John has to carry the pails home, given two minimal sets of pails he should choose the “smaller” one as follows: Sort the sets in ascending
order. Compare the first pail in each set and choose the set with the smallest pail. If the first pails match, compare the second pails and choose from among those, else continue until the two sets differ. Thus the set {3, 5, 7, 100} should be chosen over
{3, 6, 7, 8}.

To measure out milk, FJ may completely fill a pail from the tank and pour it into the bottle. He can never remove milk from the bottle or pour milk anywhere except into the bottle. With a one-quart pail, FJ would need only one pail to create any number of
quarts in a bottle. Other pail combinations are not so convenient.

Determine the optimally small number of pails to purchase, given the guarantee that at least one solution is possible for all contest input data.

PROGRAM NAME: milk4
INPUT FORMAT
Line 1: The single integer Q 
Line 2: A single integer P (1 <= P <= 100) which is the number of pails in the store 

Lines 3..P+2: Each line contains a single integer pail_value (1 <= pail_value <= 10000), the number of quarts a pail holds 

SAMPLE INPUT (file milk4.in)
16
3
3
5
7

OUTPUT FORMAT
The output is a single line of space separated integers that contains:

the minimum number of pails required to measure out the desired number of quarts, followed by:

a sorted list (from smallest to largest) of the capacity of each of the required pails

SAMPLE OUTPUT (file milk4.out)
2 3 5

 

——————————————————————————–
典型的动态规划,但是这里有两个条件:桶最少;相同数目的桶,取比较小的那些。
不过,当这两个条件相互冲突时,应该如何取舍?
使用动态规划的基本思路是:
如果能够满足q量的牛奶,那么这q+任一个桶的量所得的数目也一定能够满足。

   Test 1: TEST OK [0.000 secs, 5080 KB]
   Test 2: TEST OK [0.000 secs, 5080 KB]
   Test 3: TEST OK [0.000 secs, 5080 KB]
   Test 4: TEST OK [0.000 secs, 5080 KB]
   Test 5: TEST OK [0.000 secs, 5080 KB]
   Test 6: TEST OK [0.000 secs, 5080 KB]
   Test 7: TEST OK [0.027 secs, 5080 KB]
   Test 8: TEST OK [0.135 secs, 5080 KB]
   Test 9: TEST OK [0.054 secs, 5080 KB]
   Test 10: TEST OK [0.135 secs, 5080 KB]
我在网上找这个的测试用例的时候,没法先哪个人上传过的,因此特地把测试用例作为附件上传。

/*
ID:yunleis3
PROG:milk4
LANG:C++
*/


#include <fstream>
#include<iostream>

using namespace std;
const int maxq=20001;
const int maxp=101;
bool metri[maxq][maxp];
int pailnum[maxq];
int q,p;
//#define  DEBUG
int pail[maxp];
 
void quicksort(int * a,int p,int r);
int middleq;
int main()
{
	ifstream fin("milk4.in");
	fin>>q>>p;
	for(int i=0;i<p;++i){
		fin>>pail[i];
		metri[pail[i]][i]=true;
		pailnum[pail[i]]=1;
	}
	//quicksort(pail,0,p-1);
	 solve1();
 
	int *result1=new int[pailnum[q]];
	int ptr1=0;
	for(int i=0;i<p;++i){
		if(metri[q][i])
			result1[ptr1++]=pail[i]; 
	}
	quicksort(result1,0,ptr1-1);
	for(int i=0;i<q;++i){
		for(int j=0;j<p;++j)
			metri[i][j]=false;
		pailnum[i]=0;	
	}
	for(int i=0;i<p;++i){ 
		metri[pail[i]][i]=true;
		pailnum[pail[i]]=1;
	}
	 nochange=true;
	for(int i=1;i<=q&&nochange;++i){
		nochange=false;
		for(int j=0;j<p;++j){
			if(i+pail[j]>q)
				continue;
			nochange=true; 
			int num=metri[i][j]?0:1;
			bool flag=false;
			if(pailnum[i]==0)
				flag=false;
		//	else if(pailnum[i+pail[j]]==0||(num+pailnum[i])<pailnum[i+pail[j]]){
			//	flag=true;
			//}
			else {
				bool metritmp=metri[i][j];
				metri[i][j]=true;
				for(int ss=0;ss<=p;++ss){
					if(metri[i][ss]&&!metri[i+pail[j]][ss]){
						flag=true;
						break;
					}
					else if(!metri[i][ss]&&metri[i+pail[j]][ss])
						break;
				}
				metri[i][j]=metritmp;
			}
			if(flag){
				for(int ss=0;ss<p;++ss){					 
					metri[i+pail[j]][ss]=metri[i][ss];					 
				}
				metri[i+pail[j]][j]=true;
				pailnum[i+pail[j]]=(num+pailnum[i]);
 
			}
		}
	}
	ofstream fout("milk4.out");
	

	 
	int *result=new int[pailnum[q]];
	int ptr=0;
	for(int i=0;i<p;++i){
		if(metri[q][i])
			result[ptr++]=pail[i];//fout<<" "<<pail[i];
	}
	p=ptr;	
	for(int i=0;i<q;++i){
		for(int j=0;j<p;++j)
			metri[i][j]=false;
		pailnum[i]=0;	
	}
	for(int i=0;i<p;++i){
		pail[i]=result[i];
		metri[pail[i]][i]=true;
		pailnum[pail[i]]=1;
	}
	solve1();
	
	ptr=0;
	for(int i=0;i<p;++i){
		if(metri[q][i])
			result[ptr++]=pail[i];//fout<<" "<<pail[i];
	}
	if(ptr1<ptr)
	{
		int * resulttmp=result1;
		result1=result;
		result=resulttmp;
		ptr=ptr1;
	}
	else if(ptr1==ptr){

	}
 	fout<<ptr;
	quicksort(result,0,ptr-1);
	for(int i=0;i<ptr;++i)		 
		fout<<" "<<result[i];
	fout<<endl;
	delete [] result;
	delete [] result1;
	//system("pause");
}
 void solve1()
 {
	bool  nochange=true;
	 for(int i=1;i<=q&&nochange;++i){
		 nochange=false;
		 for(int j=0;j<p;++j){
			 if(i+pail[j]>q)
				 continue;
			 nochange=true; 
			 int num=metri[i][j]?0:1;
			 bool flag=false;
			 if(pailnum[i]==0)
				 flag=false;
			 else if(pailnum[i+pail[j]]==0||(num+pailnum[i])<pailnum[i+pail[j]]){
				 flag=true;
			 }
			 else if((num+pailnum[i])==pailnum[i+pail[j]]){
				 bool metritmp=metri[i][j];
				 metri[i][j]=true;
				 for(int ss=0;ss<=p;++ss){
					 if(metri[i][ss]&&!metri[i+pail[j]][ss]){
						 flag=true;
						 break;
					 }
					 else if(!metri[i][ss]&&metri[i+pail[j]][ss])
						 break;
				 }
				 metri[i][j]=metritmp;
			 }
			 if(flag){
				 for(int ss=0;ss<p;++ss){					 
					 metri[i+pail[j]][ss]=metri[i][ss];					 
				 }
				 metri[i+pail[j]][j]=true;
				 pailnum[i+pail[j]]=(num+pailnum[i]);

			 }
		 }
	 }

 }
void swap(int * a,int * b){
	int t=*a;
	*a=*b;
	*b=t;
}
int partion(int * a,int p,int r){
	int x=a[r];
	int i=p-1;
	for(int j=p;j<r;++j){
		if(a[j]<x){
			i++;
			swap(a+i,a+j);
		}
	}
	i++;
	swap(a+r,a+i);
	return i;
}
void quicksort(int * a,int p,int r){
	if(p<r){
		int q=partion(a,p,r);
		quicksort(a,p,q-1);
		quicksort(a,q+1,r);
	}
}

————————————–

Here are the test data inputs:

——- test 1 —-
16
3
3
5
7
——- test 2 —-
20
3
1
2
4
——- test 3 —-
59
3
7
11
13
——- test 4 —-
8722
2
89
97
——- test 5 —-
323
5
97
101
103
107
119
——- test 6 —-
20000
3
233
151
413
——- test 7 —-
5334
100
1009
1013
1019
1021
1031
1033
1039
1049
1051
1061
1063
1069
1087
1091
1093
1097
1103
1109
1117
1123
1129
1151
1153
1163
1171
1181
1187
1193
1201
1213
1217
1223
1229
1231
1237
1249
1259
1277
1279
1283
1289
1291
1297
1301
1303
1307
1319
1321
1327
1361
1367
1373
1381
1399
1409
1423
1427
1429
1433
1439
1447
1451
1453
1459
1471
1481
1483
1487
1489
1493
1499
1511
1523
1531
1543
1549
1553
1559
1567
1571
1579
1583
1597
1601
1607
1609
1613
1619
1621
1627
1637
1657
1663
1667
1669
1693
1697
1699
1709
1721
——- test 8 —-
15383
100
997
998
1000
1003
1007
1012
1018
1025
1033
1042
1052
1063
1075
1088
1102
1117
1133
1150
1168
1187
1207
1228
1250
1273
1297
1322
1348
1375
1403
1432
1462
1493
1525
1558
1592
1627
1663
1700
1738
1777
1817
1858
1900
1943
1987
2032
2078
2125
2173
2222
2272
2323
2375
2428
2482
2537
2593
2650
2708
2767
2827
2888
2950
3013
3077
3142
3208
3275
3343
3412
3482
3553
3625
3698
3772
3847
3923
4000
4078
4157
4237
4318
4400
4483
4567
4652
4738
4825
4913
5002
5092
5183
5275
5368
5462
5557
5653
5750
5848
5947
——- test 9 —-
19829
20
708
727
764
825
916
1043
1212
1429
1700
2031
2428
2897
3444
4075
4796
5613
6532
7559
8700
9961
——- test 10 —-
16737
94
904
909
916
925
936
949
964
981
1000
1021
1044
1069
1096
1125
1156
1189
1224
1261
1300
1341
1384
1429
1476
1525
1576
1629
1684
1741
1800
1861
1924
1989
2056
2125
2196
2269
2344
2421
2500
2581
2664
2749
2836
2925
3016
3109
3204
3301
3400
3501
3604
3709
3816
3925
4036
4149
4264
4381
4500
4621
4744
4869
4996
5125
5256
5389
5524
5661
5800
5941
6084
6229
6376
6525
6676
6829
6984
7141
7300
7461
7624
7789
7956
8125
8296
8469
8644
8821
9000
9181
9364
9549
9736
9925

 

 

 

[usaco]3.1.5 stamps

Stamps

Given a set of N stamp values (e.g., {1 cent, 3 cents}) and an upper limit K to the number of stamps that can fit on an envelope, calculate the largest unbroken list of postages from 1 cent to M cents that can be created.

For example, consider stamps whose values are limited to 1 cent and 3 cents; you can use at most 5 stamps. It’s easy to see how to assemble postage of 1 through 5 cents (just use that many 1 cent stamps), and successive values aren’t much harder:

6 = 3 + 3
7 = 3 + 3 + 1
8 = 3 + 3 + 1 + 1
9 = 3 + 3 + 3
10 = 3 + 3 + 3 + 1
11 = 3 + 3 + 3 + 1 + 1
12 = 3 + 3 + 3 + 3
13 = 3 + 3 + 3 + 3 + 1.
However, there is no way to make 14 cents of postage with 5 or fewer stamps of value 1 and 3 cents. Thus, for this set of two stamp values and a limit of K=5, the answer is M=13.

The most difficult test case for this problem has a time limit of 3 seconds.

PROGRAM NAME: stamps
INPUT FORMAT
Line 1:  Two integers K and N. K (1 <= K <= 200) is the total number of stamps that can be used. N (1 <= N <= 50) is the number of stamp values. 
Lines 2..end: N integers, 15 per line, listing all of the N stamp values, each of which will be at most 10000. 

SAMPLE INPUT (file stamps.in)
5 2
1 3

OUTPUT FORMAT
Line 1: One integer, the number of contiguous postage values starting at 1 cent that can be formed using no more than K stamps from the set.

SAMPLE OUTPUT (file stamps.out)
13

—————————
这个题的要点是使用索引,因为最终的结果值可能非常大,如果使用空间不善的话,会超出系统给出的值。
通过动态规划,计算某个值要使用的最少的stamp数目,来自于i-value[x]的的stamp数目。
关键点在这里:
for(int i=0;;i++)
 {
  if(results[INDEX(i)]>k)
  {
   ptr=i;
   break;
  }
  for(int j=0;j<n;j++)
  {
   if(results[INDEX(i+values[j])]==-1||((results[INDEX(i+values[j])])>(results[INDEX(i)]+1)))
    results[INDEX(i+values[j])]=results[INDEX(i)]+1;
  }
  results[INDEX(i)]=-1;
 }
这道题目我提交了6次,就是因为刚开始估计使用空间时失误,没想到结果会那么大。后来只好采用索引了。
采用索引之后使用的空间可能会很小,但也不好说每一个周期需要多少,只好采用一个很大的值。
我的程序最终结果,最复杂的一个结果使用的时间才0.6s,远远小于系统提供的最大时间3s:
USER: Ma yunlei [yunleis2]
TASK: stamps
LANG: C++

Compiling…
Compile: OK

Executing…
   Test 1: TEST OK [0.000 secs, 3412 KB]
   Test 2: TEST OK [0.000 secs, 3412 KB]
   Test 3: TEST OK [0.000 secs, 3412 KB]
   Test 4: TEST OK [0.000 secs, 3412 KB]
   Test 5: TEST OK [0.000 secs, 3412 KB]
   Test 6: TEST OK [0.000 secs, 3412 KB]
   Test 7: TEST OK [0.000 secs, 3412 KB]
   Test 8: TEST OK [0.000 secs, 3412 KB]
   Test 9: TEST OK [0.000 secs, 3412 KB]
   Test 10: TEST OK [0.081 secs, 3412 KB]
   Test 11: TEST OK [0.648 secs, 3412 KB]
   Test 12: TEST OK [0.135 secs, 3412 KB]
   Test 13: TEST OK [0.000 secs, 3412 KB]

All tests OK.
Your program (‘stamps’) produced all correct answers!  This is your
submission #6 for this problem.  Congratulations!

Here are the test data inputs:

——- test 1 —-
5 2
1 3
——- test 2 —-
1 4
1 2 3 5
——- test 3 —-
2 4
1 2 4 8
——- test 4 —-
4 4
1 2 4 8
——- test 5 —-
20 1
1
——- test 6 —-
40 3
5 1 2
——- test 7 —-
3 10
29 50 36 43 1 2 4 8 15 22
——- test 8 —-
6 10
1 2 9 31 255 480 4 15 63 127
——- test 9 —-
8 12
1 2 4 15 9 31 63 127 255 511 1000 1999
——- test 10 —-
200 14
1 2 4 15 9 31 63 2100 3500 127 255 511 1000 1999
——- test 11 —-
200 50
1 37 87 14 137 4016 157 5383 7318 8662 7074 2821 5250 9704 8986
1375 6587 5962 7190 339 1981 9719 7012 385 7926 5159 3259 5144 7846 8854
3249 3198 8408 2784 6249 4648 6799 2757 31 4116 7771 3456 3288 3020 3159
8625 747 9745 938 10000
——- test 12 —-
200 15
1 3 14 59 265 358 979 323 846 26 433 832 7950 28 841
——- test 13 —-
200 15
1 1 1 1 1 10 10 10 10 10 100 100 100 100 100

Keep up the good work!

Thanks for your submission!
的:
———————————————————– 

 

/*
ID:yunleis2
PROG:stamps
LANG:C++
*/
#include<iostream>
#include<fstream>
using namespace std;
int values[50];
const unsigned int maxnum=100000;
int results[maxnum];
#define INDEX(x) ((x)%maxnum)
int main()
{
	int k,n;
	fstream fin("stamps.in",ios::in);
	fin>>k>>n;
	for(int i=0;i<n;i++)
		fin>>values[i];
	for(int i=0;i<maxnum;i++)
		results[INDEX(i)]=-1;
	results[INDEX(0)]=0;
	int ptr=-1;
	for(int i=0;;i++)
	{
		if(results[INDEX(i)]>k)
		{
			ptr=i;
			break;
		}
		for(int j=0;j<n;j++)
		{
			if(results[INDEX(i+values[j])]==-1||((results[INDEX(i+values[j])])>(results[INDEX(i)]+1)))
				results[INDEX(i+values[j])]=results[INDEX(i)]+1;
		}
		results[INDEX(i)]=-1;
	}
	if(ptr==-1)
		cout<<"error"<<endl;
	fstream fout("stamps.out",ios::out);
	for(int i=ptr;i>=0;i--)
	{
		if(results[INDEX(i)]<k)
		{
			ptr=i+1;
			break;
		}
	}
	for(int i=ptr;;i++)
	{
		if(results[INDEX(i)]==-1||results[INDEX(i)]>k)
		{	
			ptr=i-1;
			break;
		}
	}
	fout<<ptr<<endl;
//	int i=0;
//	for(i=ptr;i<maxnum&&results[INDEX(i]<=k;i++)
//		cout<<"("<<i<<","<<results[INDEX(i]<<")"<<"\t";
	//i--;
	//fout<<i<<endl;
	// system("pause");
}

 

[usaco][舞会灯] party lamps

这是我做过的题目中用时间最长的一个
题目原文:
——————————————–
Party Lamps
IOI 98
To brighten up the gala dinner of the IOI’98 we have a set of N (10 <= N <= 100) colored lamps numbered from 1 to N.

The lamps are connected to four buttons:

Button 1: When this button is pressed, all the lamps change their state: those that are ON are turned OFF and those that are OFF are turned ON.

Button 2: Changes the state of all the odd numbered lamps.
Button 3: Changes the state of all the even numbered lamps.
Button 4: Changes the state of the lamps whose number is of the form 3xK+1 (with K>=0), i.e., 1,4,7,…

A counter C records the total number of button presses.

When the party starts, all the lamps are ON and the counter C is set to zero.

You are given the value of counter C (0 <= C <= 10000) and the final state of some of the lamps after some operations have been executed. Write a program to determine all the possible final configurations of the N lamps that are consistent with the given
information, without repetitions.

PROGRAM NAME: lamps
INPUT FORMAT
Line 1:  N 
Line 2:  Final value of C 
Line 3:  Some lamp numbers ON in the final configuration, separated by one space and terminated by the integer -1. 

Line 4:  Some lamp numbers OFF in the final configuration, separated by one space and terminated by the integer -1. 

No lamp will be listed twice in the input. 

SAMPLE INPUT (file lamps.in)
10
1
-1
7 -1

In this case, there are 10 lamps and only one button has been pressed. Lamp 7 is OFF in the final configuration.

OUTPUT FORMAT
Lines with all the possible final configurations (without repetitions) of all the lamps. Each line has N characters, where the first character represents the state of lamp 1 and the last character represents the state of lamp N. A 0 (zero) stands for a lamp
that is OFF, and a 1 (one) stands for a lamp that is ON. The lines must be ordered from least to largest (as binary numbers).

If there are no possible configurations, output a single line with the single word `IMPOSSIBLE’

SAMPLE OUTPUT (file lamps.out)
0000000000
0101010101
0110110110

In this case, there are three possible final configurations:
All lamps are OFF
Lamps 1, 4, 7, 10 are OFF and lamps 2, 3, 5, 6, 8, 9 are ON.
Lamps 1, 3, 5, 7, 9 are OFF and lamps 2, 4, 6, 8, 10 are ON.
—————————————————————————
刚开始我真的用了bfs,因为没有发现规律。
深探C步,当C比较小的时候还可以忍受,但C大了的时候,就会出现stack overflow,即使不出现这个,还有时间的问题。
要遍历4^N,指数级的。

后来发现了规律:
1:对于每一个button,如果按下两次,就相当于什么也没发生。
2:对于所有的等,相当于6盏灯。

利用第一个条件,递归的深度最多只需要4;大大的节省了空间和时间
利用第二个条件,储存时节省了空间
我的解法:
—————————————————————————–

/*
ID:yunleis2
PROG:lamps
LANG:C++
*/
#include<iostream>
#include<fstream>
#include<vector>
using namespace std;
int N;
int C;
int *final_on;
int *final_off;
void search(int depth,bool * state0);
vector<bool *> result;
void quicksort(bool ** a,int p,int r);
int compare(bool * b1,bool *b2);
void button1(int num,bool *state0);
void button2(int num,bool *state0);
void button3(int num,bool *state0);
void button4(int num,bool *state0);
void check(int num,bool *state0);
int main()
{
	fstream fin("lamps.in",ios::in);
	fin>>N;
	int old_n=N;
	N--;
	N=N%6+6;
	N++;
	fin>>C;
	int t;
	final_on=new int[N+1];
	final_off=new int[N+1];
	bool * init_s=new bool[N];
	for(int i=0;i<N;i++)
		init_s[i]=true;
	int ptr=0;
	do{
		fin>>t;
		final_on[ptr++]=t-1;
	}while(t!=-1);
	ptr=0;
	do{
		fin>>t;
		final_off[ptr++]=t-1;
	}while(t!=-1);
	//search(C,init_s);
	button1(0,init_s);

	bool **result1 =new bool*[result.size()];
	int size=result.size();
	for(int i=0;i<result.size();i++)
	{
		result1[i]=result.at(i);
	}
	for(int i=0;i<size;i++)
	{
		for(int j=0;j<N;j++)
			cout<<result[i][j];
		cout<<endl;
	
	}
	quicksort(result1,0,result.size()-1);
	fstream fout("lamps.out",ios::out);
	if(size==0)
		fout<<"IMPOSSIBLE"<<endl;
	cout<<endl;
	for(int i=0;i<size;i++)
	{
		if(i!=0&&compare(result1[i],result1[i-1])==0)
		{ 
			continue;
		}
		for(int j=0;j<old_n;j++)
			fout<<result1[i][j%6];
		fout<<endl;
		 
	}
	for(int i=0;i<size;i++)
		delete [] result1[i];
	
	 
 
} 
int compare(bool * b1,bool *b2)
{
 #if 0

 	cout<<"compare"<<endl;
 	for(int j=0;j<N;j++)
 		cout<<b1[j];
 	cout<<endl;
 	for(int j=0;j<N;j++)
 		cout<<b2[j];
 	cout<<endl; 
#endif
 
	for(int i=0;i<N;i++)
	{
		int a=b1[i];
		int b=b2[i];
		if(a<b)
			return -1;
		if(a>b)
			return 1;
	}
	return 0;
}
int partition(bool ** a,int p,int r)
{
	bool * x=a[r];
	int i=p-1;
	for(int j=p;j<r;j++)
	{
		if(compare(a[j],x)<=0)
		{
			i++;
			bool * temp=a[i];
			a[i]=a[j];
			a[j]=temp;
		}
	}
	bool * temp=a[i+1];
	a[i+1]=a[r];
	a[r]=temp;
	return i+1;
}
void quicksort(bool ** a,int p,int r)
{
	if(p<r)
	{
		int i=partition(a,p,r);
		quicksort(a,p,i-1);
		quicksort(a,i+1,r);
	}
}

void button1(int num,bool *state0)
{
	if(num>C)
		return;
	bool * state1;
	state1=new bool[N];
	for(int i=0;i<N;i++)
	{
		state1[i]=state0[i];
	}
	//no change
	button2(num,state1);
	for(int i=0;i<N;i++)
		state1[i]=!state1[i];
	button2(num+1,state1);
	delete []state1;
}
void button2(int num,bool *state0)
{
	if(num>C)
		return;
	bool * state1;
	state1=new bool[N];
	for(int i=0;i<N;i++)
	{
		state1[i]=state0[i];
	}
	//no change
	button3(num,state1);
	for(int i=0;i<N;i+=2)
		state1[i]=!state1[i];
	button3(num+1,state1);
	delete [] state1;
}

void button3(int num,bool *state0)
{
	if(num>C)
		return;
	bool * state1;
	state1=new bool[N];
	for(int i=0;i<N;i++)
	{
		state1[i]=state0[i];
	}
	//no change
	button4(num,state1);
	for(int i=1;i<N;i+=2)
		state1[i]=!state1[i];
	button4(num+1,state1);
	delete [] state1;
}
void button4(int num,bool *state0)
{
	if(num>C)
		return;
	bool * state1;
	state1=new bool[N];
	for(int i=0;i<N;i++)
	{
		state1[i]=state0[i];
	}
	//no change
	check(num,state1);
	for(int i=0;i<N;i+=3)
		state1[i]=!state1[i];
	check(num+1,state1);
	 delete [] state1;
}
void check(int num ,bool *state0)
{
	if(num>C)
		return;
	if((num%2)!=C%2)
		return;
	for(int i=0;i<N&&final_on[i]!=-2;i++)
	{
		if(!state0[final_on[i]%6])
		{ 
			 
			return ;
		}
	}
	for(int i=0;i<N&&final_off[i]!=-2;i++)
	{
		if(state0[final_off[i]%6])
		{ 
			
			return ;
		}
	}
	bool *res=new bool[N];
	for(int i=0;i<N;i++)
		res[i]=state0[i];
	result.push_back(res);
 
}